June 11, 2018, 4:10 PM - 4:40 PM
96 Frelinghuysen Road
Piscataway, NJ 08854
Click here for map.
Jim Luedtke, University of Wisconsin, Madison
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