Abstract: 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.

This seminar will be streamed.