Decomposition Algorithms for Very Large Scale Stochastic Mixed-Integer Programs; Final rept. 1 Jul-30 Nov 2007

摘要

The objectives of this project were to explore decomposition algorithms that solve optimization models under uncertainty. In order to accommodate a variety of future scenarios, our algorithms are designed to address large scale models. The main accomplishments of the project can be summarized as follows; (1) design and evaluate decomposition methods for stochastic mixed-integer programming (SMIP) problems (Yuan and Sen 2008); (2) accelerate stochastic decomposition (SD) as a prelude to using SD for SMIP as well as a multi-stage version of SD (Sen et al 2007), (Zhou and Sen 2008); (3) develop a theory for parametric analysis of mixed-integer programs, and provide economically justifiable estimates of shadow prices from mixed-integer linear programming models (Sen and Genc 2008). The first two relate to stochastic programming, whereas the last addresses one of the long-standing open questions in discrete optimization, namely, parametric analysis in MILP models. This paper (listed as 1) is likely to have a long term impact on a variety of fields including discrete optimization, operations research, and computational economics.