New Theory and Methods in Stochastic Mixed Integer Programming.

摘要

The proposed project was aimed at exploring various theoretical and algorithmic issues at the intersection of three optimization areas, namely, parametric, stochastic and bilevel integer programming, as well as related applications. The main contribution of the project is development of novel algorithmic methodologies (along with the necessary theoretical foundations) for solving stochastic and bilevel integer programs built upon exploiting equivalent value function reformulations. While computational limitations exist for the proposed approaches, the preliminary results of our experiments are extremely encouraging as for several broad classes of stochastic and bilevel integer optimization problems we are able to solve instances that are among the largest instances solved in the literature. Additionally, we explore several interesting related applications including those arising in wireless sensor networks (and, possibly, other networked systems). For the considered applications we derive structural properties of the optimal policies and exploit them to develop exact solution techniques. Finally, we provide theoretical investigation of randomized restart algorithms in the context of algorithm portfolios (i.e., set of algorithms run in parallel). In particular, we provide the theoretical upper bound on the computational value of mixing randomized restart algorithms with different properties. Furthermore, the constructive proof of the main result allows us to characterize restart algorithms that are capable of forming an effective mixed algorithm portfolio.