Lagrangian decomposition for large-scale two-stage stochastic mixed 0-1 problems. (English) Zbl 1257.90062
Summary: We study solution methods for solving the dual problem corresponding to the Lagrangian Decomposition of two-stage stochastic mixed 0-1 models. We represent the two-stage stochastic mixed 0-1 problem by a splitting variable representation of the deterministic equivalent model, where 0-1 and continuous variables appear at any stage. Lagrangian Decomposition (LD) is proposed for satisfying both the integrality constraints for the 0-1 variables and the non-anticipativity constraints. We compare the performance of four iterative algorithms based on dual Lagrangian Decomposition schemes: the subgradient method, the volume algorithm, the progressive hedging algorithm, and the Dynamic Constrained Cutting Plane scheme. We test the tightness of the LD bounds in a testbed of medium- and large-scale stochastic instances.
MSC:
| 90C15 | Stochastic programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
| 90C06 | Large-scale problems in mathematical programming |
| 90C11 | Mixed integer programming |
Keywords:
two-stage stochastic integer programming; Lagrangian decomposition; subgradient method; volume algorithm; progressive hedging algorithm; Dynamic Constrained Cutting Plane schemeSoftware:
COIN-ORReferences:
| [1] | Alonso-Ayuso A, Escudero LF, Garín A, Ortuño MT, Pérez G (2003a) An approach for strategic supply chain planning based on stochastic 0–1 programming. J Glob Optim 26:97–124 · Zbl 1116.90383 · doi:10.1023/A:1023071216923 |
| [2] | Alonso-Ayuso A, Escudero LF, Ortuño MT (2003b) BFC a Branch-and-Fix Coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs. Eur J Oper Res 151:503–519 · Zbl 1053.90101 · doi:10.1016/S0377-2217(02)00628-8 |
| [3] | Barahona F, Anbil R (2000) The Volume algorithm: producing primal solutions with a subgradient method. Math Program 87:385–399 · Zbl 0961.90058 · doi:10.1007/s101070050002 |
| [4] | Bertsekas DP (1982) Constrained optimization and Lagrange multiplier methods. Academic Press, San Diego · Zbl 0572.90067 |
| [5] | Birge JR, Louveaux FV (1997) Introduction to stochastic programming. Springer, Berlin |
| [6] | Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper Res Lett 24:37–45 · Zbl 1063.90037 · doi:10.1016/S0167-6377(98)00050-9 |
| [7] | Carøe CC, Tind J (1998) L-shaped decomposition of two-stage stochastic programs with integer recourse. Math Program 83:451–464 · Zbl 0920.90107 · doi:10.1007/BF02680570 |
| [8] | Engell S, Märkert A, Sand G, Schultz R (2004) Aggregated scheduling of a multiproduct batch plant by two-stage stochastic integer programming. Optim Eng 5:335–359 · Zbl 1151.90547 · doi:10.1023/B:OPTE.0000038890.51798.5a |
| [9] | Escudero LF (2009) On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming. Top 17:5–29 · Zbl 1170.90445 · doi:10.1007/s11750-009-0090-7 |
| [10] | Escudero LF, Garín A, Merino M, Pérez G (2009) A general algorithm for solving two-stage stochastic mixed 0-1 first stage problems. Comput Oper Res 36:2590–2600 · Zbl 1179.90245 · doi:10.1016/j.cor.2008.11.011 |
| [11] | Escudero LF, Garín A, Merino M, Pérez G (2010a) On BFC-MSMIP strategies for scenario cluster partitioning, Twin Node Family branching selection and bounding for multistage stochastic mixed integer programming. Comput Oper Res 37:738–753 · Zbl 1176.90422 · doi:10.1016/j.cor.2009.06.023 |
| [12] | Escudero LF, Garín A, Merino M, Pérez G (2010b) An exact algorithm for solving large-scale two-stage stochastic mixed integer problems: some theoretical and experimental aspects. Eur J Oper Res 204:105–116 · Zbl 1178.90255 · doi:10.1016/j.ejor.2009.09.027 |
| [13] | Geoffrion AM (1974) Lagrangian relaxation for integer programming. Math Program Stud 2:82–114 · doi:10.1007/BFb0120690 |
| [14] | Guignard M (2003) Lagrangian relaxation. Top 11:151–228 · Zbl 1079.90087 · doi:10.1007/BF02579036 |
| [15] | Guignard M, Kim S (1987) Lagrangian decomposition. A model yielding stronger Lagrangian bounds. Math Program 39:215–228 · Zbl 0638.90074 · doi:10.1007/BF02592954 |
| [16] | Held M, Karp RM (1971) The traveling salesman problem and minimum spanning trees: part II. Math Program 1:6–25 · Zbl 0232.90038 · doi:10.1007/BF01584070 |
| [17] | Held M, Wolfe P, Crowder H (1974) Validation of subgradient optimization. Math Program 6:62–88 · Zbl 0284.90057 · doi:10.1007/BF01580223 |
| [18] | Helmberg C, Kiwiel KC (2002) A spectral bundle method with bounds. Math Program 93:173–194 · Zbl 1065.90059 · doi:10.1007/s101070100270 |
| [19] | Hemmecke R, Schultz R (2001) Decomposition methods for two-stage stochastic Integer Programs. In: Grötschel M, Krumke SO, Rambau J (eds) Online optimization of large scale systems, pp 601–622. Springer, Berlin · Zbl 1016.90030 |
| [20] | INFORMS. COIN-OR (2008) COmputational INfrastructure for Operations Research. www.coin-or.org |
| [21] | Jimenez RN, Conejo AJ (1997) Short-term hydro-thermal coordination by Lagrangian relaxation: solution of the dual problem. IEEE Trans Power Syst 14:89–95 |
| [22] | Kiwiel KC (1990) Proximity control in bundle methods for convex nondifferentiable minimization. Math Program 46:15–122 · Zbl 0697.90060 |
| [23] | Klein Haneveld W, van der Vlerk Kang M (1999) Stochastic integer programming: general models and algorithms. Ann Oper Res 85:39–57 · Zbl 0920.90110 · doi:10.1023/A:1018930113099 |
| [24] | Laporte G, Louveaux FV (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper Res 50:415–423 · Zbl 1163.90773 · doi:10.1287/opre.50.3.415.7751 |
| [25] | Li D, Sun X (2006) Nonlinear integer programming. Springer, Berlin · Zbl 1140.90042 |
| [26] | Ntaimo L, Sen S (2005) The million variable ’march’ for stochastic combinatorial optimization. J Glob Optim 32:385–400 · Zbl 1098.90045 · doi:10.1007/s10898-004-5910-6 |
| [27] | Polyak BT (1987) Introduction to optimization software |
| [28] | Rockafellar RT, Wets RJ-B (1991) Scenario and policy aggregation in optimisation under uncertainty. Math Oper Res 16:119–147 · Zbl 0729.90067 · doi:10.1287/moor.16.1.119 |
| [29] | Schultz R (2003) Stochastic programming with integer variables. Math Program, Ser B 97:285–309 · Zbl 1035.90053 |
| [30] | Sen S, Higle JL (2005) The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: set convexification. Math Program, Ser A 104:1–20 · Zbl 1159.90464 · doi:10.1007/s10107-004-0566-z |
| [31] | Sen S, Sherali HD (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math Program, Ser A 106:203–223 · Zbl 1134.90449 · doi:10.1007/s10107-005-0592-5 |
| [32] | Sherali HD, Smith JC (2009) Two-stage hierarchical multiple risk problems: models and algorithms. Math Program, Ser A 120:403–427 · Zbl 1180.90204 · doi:10.1007/s10107-008-0220-2 |
| [33] | Sherali HD, Zhu X (2006) On solving discrete two stage stochastic programs having mixed-integer first and second stage variables. Math Program, Ser A 108:597–611 · Zbl 1138.90436 · doi:10.1007/s10107-006-0724-6 |
| [34] | Takriti S, Birge JR (2000) Lagrangian solution techniques and bounds for loosely coupled mixed-integer stochastic programs. Oper Res 48:91–98 · Zbl 1106.90363 · doi:10.1287/opre.48.1.91.12450 |
| [35] | Till J, Sand G, Urselmann M, Engell S (2007) A hybrid evolutionary algorithm for solving two-stage stochastic integer programs in chemical batch scheduling. Comput Chem Eng 31:630–647 · doi:10.1016/j.compchemeng.2006.09.003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
