On \(BFC-MSMIP\) strategies for scenario cluster partitioning, and twin node family branching selection and bounding for multistage stochastic mixed integer programming. (English) Zbl 1176.90422
Summary: In the branch-and-fix coordination \((BFC-MSMIP)\) algorithm for solving large-scale multistage stochastic mixed integer programming problems, we find it crucial to decide the stages where the nonanticipativity constraints are explicitly considered in the model. This information is materialized when the full model is broken down into a scenario cluster partition with smaller subproblems. In this paper we present a scheme for obtaining strong bounds and branching strategies for the Twin Node Families to increase the efficiency of the procedure \(BFC-MSMIP\), based on the information provided by the nonanticipativity constraints that are explicitly considered in the problem. Some computational experience is reported to support the efficiency of the new scheme.
MSC:
| 90C11 | Mixed integer programming |
| 90C15 | Stochastic programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
multistage stochastic mixed 0-1 programming; branch-and-fix coordination; nonanticipativity constraints; twin node family; scenario cluster partitioningReferences:
| [1] | Alonso-Ayuso, A.; Escudero, L. F.; Garín, 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 |
| [2] | Alonso-Ayuso A, Escudero LF, Guignard M, Quinteros M, Weintraub A. Forestry management under uncertainty. Annals of Operations Research 2009, doi:10.1007/s10479-009-0561-0; Alonso-Ayuso A, Escudero LF, Guignard M, Quinteros M, Weintraub A. Forestry management under uncertainty. Annals of Operations Research 2009, doi:10.1007/s10479-009-0561-0 · Zbl 1233.90225 |
| [3] | Alonso-Ayuso, A.; Escudero, L. F.; Ortuño, M. T., A stochastic 0-1 program based approach for air traffic management, European Journal of Operational Research, 120, 47-62 (2000) · Zbl 0979.90067 |
| [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.; Ortuño, M. T.; Pizarro, C., On a stochastic sequencing and scheduling problem, Computers & Operations Research, 34, 2604-2624 (2007) · Zbl 1141.90436 |
| [6] | Birge, J.; Louveaux, F., Introduction to stochastic programming (1997), Springer: Springer Berlin · Zbl 0892.90142 |
| [7] | Cristóbal, M. P.; Escudero, L. F.; Monge, J., On stochastic dynamic programming for solving large-scale planning problems under uncertainty, Computers & Operations Research, 36, 2418-2428 (2009) · Zbl 1179.90243 |
| [8] | Dert, C., A dynamic model for asset liability management for defined benefit pension funds, (Ziemba, W.; Mulvey, J., Worldwide asset and liability modeling (1998), Cambridge University Press: Cambridge University Press Cambridge), 501-536 · Zbl 0927.91008 |
| [9] | Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Mathematical Programming Series A, 91, 201-213 (2002) · Zbl 1049.90004 |
| [10] | Escudero, L. F., On a mixture of fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming, TOP, 17, 1, 5-29 (2009) · Zbl 1170.90445 |
| [11] | Escudero, L. F.; Garín, A.; Merino, M.; Pérez, G., A two-stage stochastic integer programming approach as a mixture of branch-and-fix coordination and benders decomposition schemes, Annals of Operations Research, 152, 395-420 (2007) · Zbl 1144.90454 |
| [12] | Escudero LF, Garín A, Merino M, Pérez G. A general algorithm for solving two-stage stochastic mixed 0-1 first-stage problems. Computers & Operations Research 2009;36:2590-2600.; Escudero LF, Garín A, Merino M, Pérez G. A general algorithm for solving two-stage stochastic mixed 0-1 first-stage problems. Computers & Operations Research 2009;36:2590-2600. · Zbl 1179.90245 |
| [13] | Escudero, L. F.; Garín, A.; Merino, M.; Pérez, G., BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0-1 problems, TOP, 17, 1, 96-122 (2009) · Zbl 1170.90447 |
| [14] | Escudero LF, Garín A, Merino M, Pérez G. On multistage stochastic integer programming model and algorithm for incorporating logical constraints in assets and liabilities management under uncertainty. Computational Management Science 2009, doi:10.1007/s10287-006-0035-7; Escudero LF, Garín A, Merino M, Pérez G. On multistage stochastic integer programming model and algorithm for incorporating logical constraints in assets and liabilities management under uncertainty. Computational Management Science 2009, doi:10.1007/s10287-006-0035-7 |
| [15] | Higle, J.; Sen, S., Stochastic decomposition (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0874.90145 |
| [16] | Kall, P.; Wallace, S., Stochastic programming (1994), Wiley: Wiley New York · Zbl 0812.90122 |
| [17] | Lulli, G.; Sen, S., A heuristic procedure for stochastic integer programming with complete recourse, Management Science, 171, 879-890 (2006) · Zbl 1116.90082 |
| [18] | Ntaimo, L.; Sen, S., The million variable “march” for stochastic combinatorial optimization, Journal of Global Optimization, 32, 385-400 (2005) · Zbl 1098.90045 |
| [19] | Ogryczak, W.; Ruszczynski, A., From stochastic dominance to mean-risk models: semi-deviations as risk measures, European Journal of Operational Research, 116, 33-50 (1999) · Zbl 1007.91513 |
| [20] | Prekopa, A., Stochastic programming (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0834.90098 |
| [21] | Rockafellar, R.; Uryasev, S., Optimization of conditional value-at-risk, Journal of Risk, 2, 21-41 (2000) |
| [22] | Rockafellar, R.; Wets, R. J.B., Scenario and policy aggregation in optimisation under uncertainty, Mathematics of Operations Research, 16, 119-147 (1991) · Zbl 0729.90067 |
| [23] | Schultz, R.; Tiedemann, S., Risk aversion via excess probabilities in stochastic programs with mixed-integer recourse, SIAM Journal on Optimization, 14, 115-138 (2003) · Zbl 1043.90059 |
| [24] | Schultz, R.; Tiedemann, S., Conditional value-at-risk in stochastic programs with mixed integer recourse, Mathematical Programming Series B, 105, 365-386 (2006) · Zbl 1085.90042 |
| [25] | Uryasev S, Pardalos P, editors. Stochastic optimization: algorithms and applications. Dordrecht: Kluwer Academic Publishers; 2001.; Uryasev S, Pardalos P, editors. Stochastic optimization: algorithms and applications. Dordrecht: Kluwer Academic Publishers; 2001. · Zbl 0964.00055 |
| [26] | Valente P. Software tools for the investigation of stochastic programming problems. PhD thesis, Department of Mathematics and Computation, Brunel University, UK; 2002.; Valente P. Software tools for the investigation of stochastic programming problems. PhD thesis, Department of Mathematics and Computation, Brunel University, UK; 2002. |
| [27] | Wallace S, Ziemba W, editors. Applications of stochastic programming. MPS-SIAM-Series in optimization, 2005.; Wallace S, Ziemba W, editors. Applications of stochastic programming. MPS-SIAM-Series in optimization, 2005. · Zbl 1105.90050 |
| [28] | Wets, R., Programming under uncertainty: the equivalent convex program, SIAM Journal on Applied Mathematics, 14, 89-105 (1966) · Zbl 0139.13303 |
| [29] | Wolsey, L. A., Integer programming (1998), Wiley-Interscience: Wiley-Interscience New York · Zbl 0299.90012 |
| [30] | Ziemba W, Mulvey J, editors. Worldwide asset and liability modeling. Cambridge: Cambridge University Press; 1998.; Ziemba W, Mulvey J, editors. Worldwide asset and liability modeling. Cambridge: Cambridge University Press; 1998. · Zbl 0903.00105 |
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.
