Geospatial optimization problems

There are numerous applications which require the ability to take certain actions (e.g. distribute money, medicines, people etc.) over a geographic region in order to optimize an objective (e.g, minimize expected number of people with a disease). We introduce “geospatial optimization problems” (GOPs) where an agent has limited resources and budget to take actions in a geographic area. The actions result in one or more properties changing for one or more locations. There are also certain constraints on the combinations of actions that can be taken. We study two types of GOPs - goal-based and benefit-maximizing (GBGOP and BMGOP respectively). A GBGOP ensures that certain properties must be true at specified locations after the actions are taken while a BMGOP optimizes a linear benefit function. We present several approaches to these problems using various integer programs as well as a multiplicative update based approximation.