Prioritization via Stochastic Optimization

University Of Texas At Austin, Austin TX

Investigators

Abstract

This grant provides funding for the development of models, and associated solution methods, for forming optimal priority lists. These models have application to problems in combinatorial optimization in which binary activity-selection decisions are constrained by one or more limited resources, such as a budget. Currently, such problems are addressed by optimization models, which yield an optimal portfolio of activities. However, such a portfolio can be fragile if: (i) the budget shrinks for exogenous reasons or due to cost overruns on higher priority activities; or, (ii) unexpected funds are added to the budget. In these cases, activities may be forced out of, or may be added to, the portfolio. A prioritization model applies when the portfolio cannot be reconfigured from scratch once the budget is specified. The approach does not rely on simple ranking schemes. Instead, it recognizes that the selected activities will act as a portfolio and forms a priority list that hedges against contingencies like (i) and (ii). An optimal priority list is built by solving a two-stage stochastic combinatorial optimization model in which the first stage decisions form the priority list. Then, when the budget is revealed the second stage variables effectively go down the priority list, carrying out the rank-ordered activities, until the budget is exhausted. A proposed column-generation scheme exploits special structures to solve these stochastic integer programs. If successful, this research will improve the ability of industry and government to prioritize, e.g., in a capital-budgeting process. Furthermore, the research aims to bring clarity to the issue of when an optimal portfolio should be constructed versus when an optimal priority list should be formed. The proposed research builds on existing work in computational optimization as the subproblems that arise in the column-generation scheme correspond to the underlying non-prioritized optimization model.