A general algorithm for solving two-stage stochastic mixed \(0-1\) first-stage problems. (English) Zbl 1179.90245
Summary: We present an algorithmic approach for solving large-scale two-stage stochastic problems having mixed \(0-1\) first stage variables. The constraints in the first stage of the deterministic equivalent model have \(0-1\) variables and continuous variables, while the constraints in the second stage have only continuous. The approach uses the twin node family concept within the algorithmic framework, the so-called branch-and-fix coordination, in order to satisfy the nonanticipativity constraints. At the same time we consider a scenario cluster Benders decomposition scheme for solving large-scale \(LP\) submodels given at each \(TNF\) integer set. Some computational results are presented to demonstrate the efficiency of the proposed approach.
Keywords:
two-stage stochastic integer programming; Benders decomposition; nonanticipativity constraints; splitting variables; twin node family; branch-and-fix coordinationReferences:
| [1] | Wets, R. J.-B., Programming under uncertainty: the equivalent convex program, SIAM Journal on Applied Mathematics, 14, 89-105 (1966) · Zbl 0139.13303 |
| [2] | Laporte, G.; Louveaux, F., An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands, Operations Research, 50, 415-423 (2002) · Zbl 1163.90773 |
| [3] | Benders, J., Partitioning procedures for solving mixed variables programming problems, Numerische Mathematik, 4, 238-252 (1962) · Zbl 0109.38302 |
| [4] | Alonso-Ayuso, A.; Escudero, L. F.; Ortuño, M. T., BFC, a branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs, European Journal of Operational Research, 151, 503-519 (2003) · Zbl 1053.90101 |
| [5] | Alonso-Ayuso, A.; Escudero, L. F.; Garín, M. A.; Ortuño, M. T.; Pérez, G., An approach for strategic supply chain planning based on stochastic 0-1 programming, Journal of Global Optimization, 26, 97-124 (2003) · Zbl 1116.90383 |
| [6] | Alonso-Ayuso, A.; Escudero, L. F.; Garín, M. A.; Ortuño, M. T.; Pérez, G., On the product selection and plant dimensioning problem under uncertainty, Omega—International Journal of Management Science, 33, 307-318 (2005) |
| [7] | Ahmed, S.; Tawarmalani, M.; Sahinidis, N. V., A multi-stage stochastic integer programming approach for capacity expansion under uncertainty, Mathematical Programming, 100, 355-377 (2004) · Zbl 1068.90084 |
| [8] | Carøe, C.; Tind, J., L-shaped decomposition of two-stage stochastic programs with integer recourse, Mathematical Programming, 83, 451-464 (1998) · Zbl 0920.90107 |
| [9] | Sherali, H. D.; Fraticelli, B. M.P., A modification of Benders’ decomposition algorithm for discrete subproblems: an approach for stochastic programs with integer recourse, Journal of Global Optimization, 22, 319-342 (2002) · Zbl 1045.90040 |
| [10] | Sen, S. S.; Higle, J. L., The \(c^3\) theorem and the \(d^2\) algorithm for large scale stochastic mixed-integer programming: set convexification, Mathematical Programming, 104, 1-20 (2005) · Zbl 1159.90464 |
| [11] | Ntaimo, L.; Sen, S., The million variable ‘march’ for stochastic combinatorial optimization, Journal of Global Optimization, 32, 385-400 (2005) · Zbl 1098.90045 |
| [12] | Sen, S.; Sherali, H., Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Mathematical Programming Series A, 105, 203-223 (2006) · Zbl 1134.90449 |
| [13] | Sherali, H.; Zhu, X., On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables, Mathematical Programming Series B, 108, 597-611 (2006) · Zbl 1138.90436 |
| [14] | Carøe, C.; Schultz, R., Dual decomposition in stochastic integer programming, Operations Research Letters, 24, 37-45 (1999) · Zbl 1063.90037 |
| [15] | Hemmecke, R.; Schultz, R., Decomposition methods for two-stage stochastic integer programs, (Grotschel, M.; Krumke, S. O.; Rambau, J., Online optimization of large scale systems (2001), Springer: Springer Berlin), 601-622 · Zbl 1016.90030 |
| [16] | Takriti, S.; Birge, J., Lagrangean solution techniques and bounds for loosely coupled mixed-integer stochastic programs, Operations Research, 48, 91-98 (2000) · Zbl 1106.90363 |
| [17] | Rockafellar, R. T.; Wets, R. J.-B., Scenario and policy aggregation in optimisation under uncertainty, Mathematics of Operations Research, 16, 119-147 (1991) · Zbl 0729.90067 |
| [18] | Klein Haneveld, W.; van der Vlerk Kang, M., Stochastic integer programming: general models and algorithms, Annals of Operations Research, 85, 39-57 (1999) · Zbl 0920.90110 |
| [19] | Nowak M, Schultz R, Westphalen W. Optimization of simultaneous power production and trading by stochastic integer programming. Technical report, Stochastic programming e-print series \(\langle;\) http://dochost.rz.hu-berlin.de/speps \(\rangle;\); Nowak M, Schultz R, Westphalen W. Optimization of simultaneous power production and trading by stochastic integer programming. Technical report, Stochastic programming e-print series \(\langle;\) http://dochost.rz.hu-berlin.de/speps \(\rangle;\) |
| [20] | Romisch, W.; Schultz, R., Multi-stage stochastic integer programs: an introduction, (Grotschel, M.; Krumke, S. O.; Rambau, J., Online optimization of large scale systems (2001), Springer: Springer Berlin), 581-600 · Zbl 1016.90029 |
| [21] | Schultz, R., Stochastic programming with integer variables, Mathematical Programming Series B, 97, 285-309 (2003) · Zbl 1035.90053 |
| [22] | Escudero LF, Garín MA, Merino M, Pérez G. A multistage stochastic integer programming model and algorithm for incorporating logical constraints in assets and liabilities under uncertainty. Computational Management Science, 2007, in press, doi:10.2007/s10287-006-0035-7; Escudero LF, Garín MA, Merino M, Pérez G. A multistage stochastic integer programming model and algorithm for incorporating logical constraints in assets and liabilities under uncertainty. Computational Management Science, 2007, in press, doi:10.2007/s10287-006-0035-7 |
| [23] | Birge, J.; Louveaux, F., Introduction to stochastic programming (1997), Springer: Springer Berlin · Zbl 0892.90142 |
| [24] | Van Slyke, R.; Wets, R. J.-B., L-shaped linear programs with application to optimal control and stochastic programming, SIAM Journal on Applied Mathematics, 17, 638-663 (1969) · Zbl 0197.45602 |
| [25] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming Series A, 91, 201-213 (2002) · Zbl 1049.90004 |
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.
