Jim Luedtke, University of Wisconsin, Madison

Abstract

We present a new progressive hedging/ADMM type algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. This dual is widely used in decomposition methods for the solution of SMIPs. A direct application of progressive hedging to this problem class is difficult because it requires solving a quadratic program over the convex hull of integer solutions, which is not given explicitly. We thus propose a variation that alternates between optimizing a linear objective over the true set of integer solutions and optimizing a quadratic objective over the convex hull of solutions collected to that point in the algorithm.  We demonstrate that the method converges to the optimal Lagrangian dual value. Numerical results demonstrate that our new algorithm empirically outperforms a previous implementation of progressive hedging for obtaining bounds in SMIP.

This is joint work with: Natashia Boland, Jeffrey Christiansen, Brian Dandurand, Andrew Eberhard, Jeff Linderoth, and Fabricio Oliveira

Slides     Video