A Novel Approach for Two-Stage Stochastic Linear Programming with Recourse

摘要

We present a new algorithm for the two-stage stochastic linear programming problem with complete recourse. This cross-decomposition algorithm employs the Benders (primal) subproblems as in the so-called "L-shaped" method but eliminates the Benders master problem for generating the next trial first-stage solution, relying instead upon Lagrangian (dual) subproblems. (The Lagrangian multipliers used in defining the dual subproblems are in turn obtained from the primal subproblems.) The primal subproblem separates into subproblems, one for each scenario, each containing only the second-stage variables. The dual subproblem also separates into subproblems, one for each scenario which contains both first- and second-stage variables, and additionally a subproblem containing only the first-stage variables. We then show that the substantial computational savings may be obtained by solving at most iterations only the dual subproblem with the first-stage variables and bypassing the termination test.