Prioritization via Parametric Optimization

We propose a new approach to prioritize activities in a resource constrained environment, where the resource budget may change across time. This problem arises frequently in project finance budgeting, and also in spatial conservation planning, where greedy techniques are often used to develop a priority ranking of all the zones in the conservation site, without considering resource available for execution. We address this gap and provide a systematic approach in this paper to synthesize the impact of resource uncertainty on the optimal prioritization strategy.We highlight a connection between prioritization and the well established parametric optimization literature. The connection allows us to show many prioritization problems with submodular cost structures are polynomially solvable, and the optimality gap between optimal prioritization strategy and the scenario-wise optimal solution is essentially zero. We also leverage the connection to simplify decision space for prioritization without the submodular cost structure. This approach transforms the infinite dimensional solution space in the parametric optimization problem into a finite dimensional static optimization model, enhancing our insights into the structure of the optimal prioritization solution. We illustrate the novelty of our framework on the following applications: (i) obnoxious facility location with choice model, showing that prioritization for this class of problem is polynomial time solvable and the prioritization solution is nested; (ii) project prioritization problem with uncertain budget, showing that a relaxation of the reformulated model can be used to construct good priority list for project management problems; and (iii) prioritization in conservation planning, a problem in biodiversity protection worldwide. We use a well known real life case study in this field to show how our approach can produce a more resilient plan to cushion the impact of budget changes, in realistic size instances with thousands over zones. More interestingly, the prioritization approach generally produces solution that performs close to the scenario-wise optimal solution at each time period, demonstrating a desirable feature of our approach in practice