A branch and bound method for stochastic integer problems under probabilistic constraints. (English) Zbl 1064.90030
Summary: Stochastic integer programming problems under probabilistic constraints are considered. Deterministic equivalent formulations of the original problem are obtained by using \(p\)-efficient points of the distribution function of the right hand side vector. A branch and bound solution method is proposed based on a partial enumeration of the set of these points. The numerical experience with the probabilistic lot-sizing problem shows the potential of the solution approach and the efficiency of the algorithms implemented.
MSC:
| 90C15 | Stochastic programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C05 | Linear programming |
References:
| [1] | Ahmed S., A. Multi-stage Integer Programming Approach for Capacity Expansion under Uncertainty, Working paper (2000) |
| [2] | Barany I., Mathematical Programming Study 22 pp 32– (1984) · Zbl 0551.90068 · doi:10.1007/BFb0121006 |
| [3] | Beraldi P., The probabilistic set covering problem · Zbl 1163.90655 · doi:10.1287/opre.50.6.956.345 |
| [4] | Belvaux G., LOTSIZELIB: A Library of Models and Matrices for Lot-Sizing Problems, Internal Report (1999) |
| [5] | DOI: 10.1287/mnsc.34.9.1096 · Zbl 0649.90039 · doi:10.1287/mnsc.34.9.1096 |
| [6] | DOI: 10.1287/mnsc.5.1.44 · Zbl 0995.90543 · doi:10.1287/mnsc.5.1.44 |
| [7] | DOI: 10.1287/mnsc.4.3.235 · doi:10.1287/mnsc.4.3.235 |
| [8] | DOI: 10.1287/opre.31.5.803 · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [9] | DOI: 10.1007/PL00011393 · doi:10.1007/PL00011393 |
| [10] | Holmes D., Technical Report 94-11, in: A collection of stochastic programming problems (1994) |
| [11] | Klein Haneveld W.K., Technical Report 276, in: A stochastic programming approach to multiperiod production planning (1988) |
| [12] | DOI: 10.1287/opre.35.6.820 · Zbl 0638.90076 · doi:10.1287/opre.35.6.820 |
| [13] | DOI: 10.1287/opre.13.6.930 · Zbl 0132.40102 · doi:10.1287/opre.13.6.930 |
| [14] | Nemhauser G.L., Integer and Combinatorial Optimization (1988) · Zbl 0652.90067 · doi:10.1002/9781118627372 |
| [15] | DOI: 10.1111/j.1467-9574.1977.tb00758.x · Zbl 0362.90048 · doi:10.1111/j.1467-9574.1977.tb00758.x |
| [16] | DOI: 10.1007/BF01580738 · Zbl 0663.90038 · doi:10.1007/BF01580738 |
| [17] | Porteus E.L., Handbooks in Operations Research and Management Science 2 pp 605– (1990) |
| [18] | Prékopa, A. On probabilistic constrained programming. Proceedings of the Princeton Symposium on Mathematical Programming. pp.113–138. New Jersey, USA: Princeton University Press. |
| [19] | DOI: 10.1007/BF01584661 · Zbl 0273.90045 · doi:10.1007/BF01584661 |
| [20] | Prékopa A., Zeitschrift fur Operations Research 34 pp 441– (1990) |
| [21] | Prékopa A., Stochastic Programming (1995) · doi:10.1007/978-94-017-3087-7 |
| [22] | Prékopa A., New Trends in Mathematical Programming pp 235– (1998) · doi:10.1007/978-1-4757-2878-1_18 |
| [23] | DOI: 10.1016/0167-6377(92)90037-4 · Zbl 0765.90071 · doi:10.1016/0167-6377(92)90037-4 |
| [24] | Sox C.R., Annals of Operations Research 20 pp 155– (1997) |
| [25] | DOI: 10.1287/mnsc.5.1.89 · Zbl 0977.90500 · doi:10.1287/mnsc.5.1.89 |
| [26] | DOI: 10.1287/opre.40.1.S145 · Zbl 0771.90031 · doi:10.1287/opre.40.1.S145 |
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.
