On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming. (English) Zbl 1170.90445
Summary: We present a framework for solving large-scale multistage mixed 0-1 optimization problems under uncertainty in the coefficients of the objective function, the right-hand side vector, and the constraint matrix. A scenario tree-based scheme is used to represent the Deterministic Equivalent Model of the stochastic mixed 0-1 program with complete recourse. The constraints are modeled by a splitting variable representation via scenarios. So, a mixed 0-1 model for each scenario cluster is considered, plus the nonanticipativity constraints that equate the 0-1 and continuous so-called common variables from the same group of scenarios in each stage. Given the high dimensions of the stochastic instances in the real world, it is not realistic to obtain the optimal solution for the problem. Instead we use the so-called Fix-and-Relax Coordination (FRC) algorithm to exploit the characteristics of the nonanticipativity constraints of the stochastic model. A mixture of the FRC approach and the Lagrangian Substitution and Decomposition schemes is proposed for satisfying, both, the integrality constraints for the 0-1 variables and the nonanticipativity constraints.
Keywords:
multistage stochastic integer programming; mean-risk measures; branch-and-fix coordination; Lagrangian substitution and decompositionReferences:
| [1] | Ahmed S (2004) Mean-risk objectives in stochastic programming. Stochastic programming e-print series, http://dochost.rz.hu-berlin.de/speps |
| [2] | Ahmed S, King AJ, Parija G (2003) A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J Glob Optim 26:3–24 · Zbl 1116.90382 · doi:10.1023/A:1023062915106 |
| [3] | 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 |
| [4] | 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 |
| [5] | Alonso-Ayuso A, Escudero LF, Garín A, Ortuño MT, Pérez G (2005a) On the product selection and plant dimensioning problem under uncertainty. Omega 33:307–318 · doi:10.1016/j.omega.2004.05.001 |
| [6] | Alonso-Ayuso A, Escudero LF, Ortuño MT (2005b) Modeling production planning and scheduling under uncertainty. In: Wallace SW, Ziemba WT (eds) Applications of stochastic programming. MPS-SIAM-series in optimization, pp 217–252 · Zbl 1105.90315 |
| [7] | Alonso-Ayuso A, Escudero LF, Pizarrro C, Romeijn HE, Romero Morales D (2006) On solving the multi-period single-sourcing problem under uncertainty. Comput Manag Sci 3:29–53 · Zbl 1203.90116 · doi:10.1007/s10287-005-0043-z |
| [8] | Alonso-Ayuso A, Escudero LF, Ortuño MT, Pizarro C (2007) On a stochastic sequencing and scheduling problem. Comput Oper Res 34:2604–2624 · Zbl 1141.90436 · doi:10.1016/j.cor.2005.10.007 |
| [9] | Alonso-Ayuso A, Escudero LF, Guignard M, Quinteros M, Weintraub A (2009) Forestry management under uncertainty. Ann Oper Res (accepted for publication) · Zbl 1233.90225 |
| [10] | Andrade R, Lisser A, Maculan N, Plateau G (2006) Enhancing a branch-and-bound algorithm for two-stage stochastic integer network design-based models. Manag Sci 52:1450–1455 · Zbl 1232.90312 · doi:10.1287/mnsc.1060.0536 |
| [11] | 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 |
| [12] | Benders JF (1962) Partitioning procedures for solving mixed variables programming problems. Numer Math 4:238–252 · Zbl 0109.38302 · doi:10.1007/BF01386316 |
| [13] | Bertsekas DP (1982) Constrained optimization and Lagrange multiplier methods. Academic Press, San Diego · Zbl 0572.90067 |
| [14] | Bertsekas DP (1995) Nonlinear programming. Athena Scientific, pp 487–532 |
| [15] | Birge JR, Louveaux FV (1997) Introduction to stochastic programming. Springer, Berlin |
| [16] | 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 |
| [17] | 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 |
| [18] | Escudero LF, de la Fuente JL, Garcia C, Prieto FJ (1999) A parallel computation approach for solving multistage stochastic network problems. Ann Oper Res 90:131–160 · Zbl 0937.90111 · doi:10.1023/A:1018904513466 |
| [19] | Escudero LF, Garín A, Merino M, Pérez G (2006) A multistage stochastic integer programming model and algorithm for incorporating logical constraints in assets and liabilities management under uncertainty. Comput Manag Sci. doi: 10.1007/s10287-006-0035-7 |
| [20] | Escudero LF, Garín A, Merino M, Pérez G (2007) A two-stage stochastic integer programming approach as a mixture of branch-and-fix coordination and benders decomposition schemes. Ann Oper Res 152:395–420 · Zbl 1144.90454 · doi:10.1007/s10479-006-0138-0 |
| [21] | Escudero LF, Garín A, Merino M, Pérez G (2009a) 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 |
| [22] | Escudero LF, Garín A, Merino M, Pérez G (2009b) BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0–1 problems. TOP (this volume) · Zbl 1170.90447 |
| [23] | Gendreau M, Laporte G, Séguin R (1996) Stochastic vehicle routing. Eur J Oper Res 88:3–12 · Zbl 0913.90094 · doi:10.1016/0377-2217(95)00050-X |
| [24] | Groewe-Kuska N, Kiwiel K, Nowak MP, Römisch W, Wegner I (2001) Power management in a hydro-thermal system under uncertainty by Lagrangian relaxation. In: Greengard C, Ruszczynski A (eds) Decision making under uncertainty: energy and power, pp 39–70 · Zbl 1079.90550 |
| [25] | Guignard M (2003a) Lagrangean decomposition and Lagrangean substitution for stochastic integer programming. Technical note. OPIM Dept., Wharton School, University of Pennsylvania, Philadelphia, USA · Zbl 1079.90087 |
| [26] | Guignard M (2003b) Lagrangean relaxation. TOP 11:151–228 · Zbl 1079.90087 · doi:10.1007/BF02579036 |
| [27] | Held M, Karp RM (1970) The traveling salesman problem and the minimum spanning trees. Oper Res 18:1138–1162 · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138 |
| [28] | 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. Springer, Berlin, pp 601–622 · Zbl 1016.90030 |
| [29] | Hernández P, Alonso-Ayuso A, Escudero LF, Guignard M, Marianov V, Weintraub A (2009) Prison facility site selection under uncertainty. Eur J Oper Res (referring process, in 2nd revision) |
| [30] | Jimenez Redondo N, Conejo AJ (1997) Short-term hydro-thermal coordination by Lagrangian relaxation: solution of the dual problem. IEEE Trans Power Syst 14:89–95 · doi:10.1109/59.744490 |
| [31] | Klein Haneveld WK, van der Vlerk MH (2001) Optimizing electricity distribution using integer recourse models. In: Uryasev S, Pardalos PM (eds) Stochastic optimization: algorithms and applications. Kluwer Academic, Berlin, pp 137–154 · Zbl 0984.90026 |
| [32] | Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper Res Lett 13:133–142 · Zbl 0793.90043 · doi:10.1016/0167-6377(93)90002-X |
| [33] | 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 |
| [34] | Lulli G, Sen S (2002) Stochastic batch-sizing problems: models and algorithms. In: Woodruff DF (ed) Stochastic integer programming and network interdiction models. Kluwer Academic, Dordrecht · Zbl 1051.90016 |
| [35] | Lulli G, Sen S (2004) A branch-and-price algorithm for multi-stage stochastic integer programming with application to stochastic batch-sizing problems. Manag Sci 50:786–796 · Zbl 1232.90314 · doi:10.1287/mnsc.1030.0164 |
| [36] | Lulli G, Sen S (2006) A heuristic procedure for stochastic integer programs with complete recourse. Eur J Oper Res 171:879–890 · Zbl 1116.90082 · doi:10.1016/j.ejor.2004.09.012 |
| [37] | MirHassani SA, Lucas C, Mitra G, Poojari CA (2000) Computational solution of a capacity planning model under uncertainty. Parallel Comput J 26:511–538 · Zbl 0942.90030 · doi:10.1016/S0167-8191(99)00118-0 |
| [38] | Mulvey JM, Ruszczynski A (1992) A diagonal quadratic approximation method for large-scale linear programs. Oper Res Lett 12:205–221 · Zbl 0767.90047 · doi:10.1016/0167-6377(92)90046-6 |
| [39] | 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 |
| [40] | Nürnberg R, Römisch W (2002) A two-stage planning model for power scheduling in a hydro-thermal system under uncertainty. Optim Eng 3:355–378 · Zbl 1079.90540 · doi:10.1023/A:1021531823935 |
| [41] | Ogryczak W, Ruszczynski A (1999) From stochastic dominance to mean-risk models: semi-deviations as risk measures. Eur J Oper Res 116:33–50 · Zbl 1007.91513 · doi:10.1016/S0377-2217(98)00167-2 |
| [42] | Polyak BT (1987) Introduction to optimization software. Inc. Publications Division, NY |
| [43] | Rockafellar RT, Uryasev S (2000) Optimization of conditional value-at-risk. J Risk 2:21–41 |
| [44] | 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 |
| [45] | Römisch W, Schultz R (2001) Multi-stage stochastic integer programs: an introduction. In: Grötschel M, Krumke SO, Rambau J (eds) Online optimization of large scale systems. Springer, Berlin, pp 581–600 · Zbl 1016.90029 |
| [46] | Ruszczynski A (1989) An augmented Lagrangian decomposition for block diagonal programming problems. Oper Res Lett 8:287–294 · doi:10.1016/0167-6377(89)90055-2 |
| [47] | Santoso T, Ahmed S, Goetschalckx M, Shapiro A (2005) A stochastic programming approach for supply network design under uncertainty. Eur J Oper Res 167:96–115 · Zbl 1075.90010 · doi:10.1016/j.ejor.2004.01.046 |
| [48] | Schultz R (2003) Stochastic programming with integer variables. Math Program, Ser B 97:285–309 · Zbl 1035.90053 |
| [49] | Schultz R, Tiedemann S (2004) Risk aversion via excess probabilities in stochastic programs with mixed-integer recourse. SIAM J Optim 14:115–138 · Zbl 1043.90059 · doi:10.1137/S1052623402410855 |
| [50] | Schultz R, Tiedemann S (2006) Conditional value-at-risk in stochastic programs with mixed integer recourse. Math Program, Ser B 105:365–386 · Zbl 1085.90042 · doi:10.1007/s10107-005-0658-4 |
| [51] | Schultz R, Nowak M, Westphalen M (2005) A stochastic integer programming model for incorporating day-ahead trading of electricity into hydro-thermal unit commitment. Optim Eng 6:163–176 · Zbl 1093.90032 · doi:10.1007/s11081-005-6794-0 |
| [52] | 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 |
| [53] | 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 |
| [54] | 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 |
| [55] | Takriti S, Birge JR (2000) Lagrangean 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 |
| [56] | Triki Ch, Beraldi P, Gross G (2005) Optimal capacity allocation in multi-auction electricity markets under uncertainty. Comput Oper Res 32:201–217 · Zbl 1073.91046 |
| [57] | Tsiakis P, Shah N, Pantelides CC (2001) Design of a multiechelon supply chain network under demand uncertainty. Ind Eng Chem Res 40:3585–3604 · doi:10.1021/ie0100030 |
| [58] | Uryasev S, Pardalos PM (eds) (2001) Stochastic optimization: algorithms and applications. Kluwer Academic, Dordrecht |
| [59] | van der Vlerk MH (2003) Integrated chance constraints in an ALM model for pension funds. Stochastic programming e-print series, http://dochost.rz.hu-berlin.de/speps |
| [60] | Wallace SW, Ziemba WT (eds) (2005) Applications of stochastic programming. MPS-SIAM series in optimization |
| [61] | Wolsey LA (1998) Integer programming. Wiley, New York · Zbl 0930.90072 |
| [62] | Ziemba WT, Mulvey JM (eds) (1998) Worldwide asset and liability modeling. Cambridge University Press, Cambridge |
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.
