Combining penalty-based and Gauss-Seidel methods for solving stochastic mixed-integer problems

Event Sponsor: 
Mathematics and Computer Science Division Seminar - LANS
Start Date: 
Aug 14 2019 - 10:30am
Building/Room: 
Building 240/Room 1404-1405
Location: 
Argonne National Laboratory
Speaker(s): 
Brian Dandurand
Speaker(s) Title: 
Postdoctoral Appointee, MCS

In this work, we combine recent ideas in mixed-integer augmented Lagrangian duality and older ideas in block Gauss–Seidel approaches, and provide an analysis and an implementation of a penalty-based Gauss-Seidel (PBGS) method, which we apply to stochastic mixed‐integer programming (SMIP) problems. The PBGS method is developed such that the inherent decomposable structure that SMIP problems present can be exploited in a computationally efficient manner. The performance of the proposed method is compared with the progressive hedging (PH) method, which also can be viewed as a Lagrangian‐based method for obtaining solutions for SMIP problems. From both the analysis and the numerical experiments, it is clear that PBGS applied to SMIPs is a heuristic (as are the applications of feasibility pumps or of ADMM to SMIPs). Numerical experiments performed using instances from the literature illustrate the effectiveness of the proposed method as a heuristic in terms of computational performance and solution quality, and its potential for improvement.

Miscellaneous Information: 

This seminar will be streamed. https://anlpress.cels.anl.gov/cels-seminars/