IoT for Defense and National Security

3IoBT Resource Allocation via Mixed Discrete and Continuous Optimization

Jonathan Bunton and Paulo Tabuada

Department of Electrical and Computer Engineering, University of California, Los Angeles, CA, USA

Abstract

The fast‐paced dynamics of the battlefield require constantly monitoring existing resources and reallocating them in response to adversarial actions. Many of these resource allocation problems consist of two coupled decisions: which resources to use and how to best use them. While the former is naturally formulated as a discrete optimization problem (e.g. should we use assets from class A or class B, should we deploy them to site C or site D), the latter is naturally formulated as a continuous optimization problem (e.g. which fraction of existing resources should we deploy to which site). An effective and optimal allocation of resources necessarily has to consider both aspects in its optimization: the discrete and the continuous. Although mixed discrete and continuous optimization problems are non‐deterministic polynomial‐time hard (NP‐Hard) in general, in this chapter we show how to leverage submodularity and convexity to identify problem instances that can be solved exactly in polynomial time.

3.1 Introduction

When distributing available assets to a set of tasks, we naturally want to do so in the most effective and cost‐efficient way possible. Resource allocation problems confront precisely this issue by describing an optimal way to divide a fixed budget of resources ...