Joint work with: N. Boland, J, Christiansen, B. Dandurand, J. Linderoth, J. Luedtke, F. Oliveira
The solution of stochastic optimisation problem in their deterministic equivalent form is intractable, for moderate sized problems, due to the exponential increase in size of the problem with scenarios and with stage number. This has led the wide use of Lagrangian relaxation in order to exploit the decomposability of the resultant problem. When a Gauss-Seidel approach is combined with this relaxation the resultant algorithm is known as Progressive Hedging (PH). This approach is well developed and under stood for problems that do not involve integer variables but when integer variable are introduced the class of Stochastic Mixed Integer Programs (SMIP) are not covered by current theory.
This is mainly to the fact that SMIP typically lacks convexity due to the assumed integrality restrictions. Since PH is a specialization of the alternating direction method of multipliers (ADMM), the application of PH to the SMIP is not theoretically supported due to this lack of convexity. Thus, PH applied to the SMIP is understood as a heuristic approach without convergence guarantees, where either cycling or suboptimal convergence is possible. We discuss some new primal-dual decomposition methods, based on an integration of the Progressive Hedging approach with the Frank-Wolfe (FW) method and some bundle methods ideas. These new algorithms can be shown to be both theoretically supported and are practically implementable. Numerical experiments demonstrate the improvements over the PH method for computing high-quality bounds for SMIP.