A Cross-decomposition Scheme with Integrated Primal-dual Multi-cuts for Two-stage Stochastic Programming Investment Planning Problems

摘要

WedescribeadecompositionalgorithmthatcombinesBendersandscenario- based Lagrangean decomposition for two-stage stochastic programming investment planningproblemswithcompleterecourse,wherethefirst-stagevariablesaremixed- integer and the second-stage variables are continuous. The algorithm is based on the cross-decomposition scheme and fully integrates primal and dual information in terms of primal-dual multi-cuts added to the Benders and the Lagrangean mas- ter problems for each scenario. The potential benefits of the cross-decomposition scheme are demonstrated with an illustrative case study for a facility location prob- lemunderdisruptions,wheretheunderlyingLPrelaxationisweak,andhence,multi- cut Benders decomposition converges only slowly. If the LP relaxation is improved by adding a tightening constraint, the performance of multi-cut Benders decomposi- tionimprovesbutthecross-decompositionschemestayscompetitiveandoutperforms Benders for the largest problem instance.