Decomposition Methods for Two-Stage Stochastic Mixed-Integer Programming: Algorithms, Applications, and Computations

Event Sponsor: 
Mathematics and Computer Science Division Seminar
Start Date: 
May 15 2009 - 1:30pm to 2:30pm
Building/Room: 
Building 221 Conference Room A216
Location: 
Argonne National Laboratory
Speaker(s): 
Yang Yuan
Speaker(s) Title: 
The Ohio State University
Host: 
Mihai Anitescu

Stochastic mixed integer program (SMIP) is considered as one of the most important and challenging problems in operations research and computer science. Such models require strategic discrete decisions to be made without full knowledge of the future, followed by tactical actions after information regarding the future is revealed. This is a natural setting for decision-making under uncertainty with applications arising from telecommunication network design, finance, homeland security, energy systems and many more.

In this research, we establish and enhance the scalability of stochastic mixed integer programming by first discussing several enhanced cut-generation methods to accelerate the computational performance of the decomposition-based branch-and-cut (D2-BAC) algorithm to tackle very large-scale SMIPs. We also explore the advantages of parallelism over serial processing in solving SMIPs by constructing portable parallel implementations. Moreover, we develop a coupled branch-and-bound algorithm to accommodate a broader class of SMIPs with continuous first-stage variables, and prove its finite convergence. Finally, in collaboration with AT&T, we propose a stochastic programming model to deliver a robust network design for the next-generation IP-over-Optical networks, as part of the DARPA CORONET project. Customized L-Shaped methods are developed for solving some large-scale practical network instances.

Miscellaneous Information: