Beraldi, Patrizia; Ruszczyński, Andrzej Beam search heuristic to solve stochastic integer problems under probabilistic constraints. (English) Zbl 1074.90031 Eur. J. Oper. Res. 167, No. 1, 35-47 (2005). Summary: This paper proposes a Beam Search heuristic strategy to solve stochastic integer programming problems under probabilistic constraints. Beam search is an adaptation of the classical branch and bound method in which at any level of the search tree only the most promising nodes are kept for further exploration, whereas the remaining are pruned out permanently. The proposed algorithm has been compared with the branch and bound method. The numerical results collected on the probabilistic set covering problem show that the beam search technique is very efficient and appears to be a promising tool to solve difficult stochastic integer problems under probabilistic constraints. Cited in 7 Documents MSC: 90C15 Stochastic programming 90C10 Integer programming 90C59 Approximation methods and heuristics in mathematical programming Keywords:Stochastic programming; Combinatorial optimization; Beam search heuristic Software:CPLEX; OR-Library PDFBibTeX XMLCite \textit{P. Beraldi} and \textit{A. Ruszczyński}, Eur. J. Oper. Res. 167, No. 1, 35--47 (2005; Zbl 1074.90031) Full Text: DOI References: [1] Beasley, J. E., OR-library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990) [2] Beraldi, P.; Ruszczyński, A., The probabilistic set covering problem, Operations Research, 50, 956-967 (2002) · Zbl 1163.90655 [3] Beraldi, P.; Ruszczyński, A., A Branch and Bound method for stochastic integer problems under probabilistic constraints, Optimization Methods and Software, 17, 359-382 (2002) · Zbl 1064.90030 [4] Charnes, A.; Cooper, W. W., Chance-constrained programming, Management Science, 5, 73-79 (1958) · Zbl 0995.90600 [5] Charnes, A.; Cooper, W. W.; Symonds, G. H., Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil, Management Science, 4, 235-263 (1958) [6] CPLEX, ILOG CPLEX 6.5: User’s Manual, CPLEX Optimization, Inc., Incline Village, NV, 1999; CPLEX, ILOG CPLEX 6.5: User’s Manual, CPLEX Optimization, Inc., Incline Village, NV, 1999 [7] Dentcheva, D.; Prékopa, A.; Ruszczyński, A., Bounds for probabilistic integer programming problems, Discrete Applied Mathematics, 124, 55-65 (2002) · Zbl 1173.90488 [8] Dentcheva, D.; Prékopa, A.; Ruszczyński, A., Concavity and efficient points of discrete distributions in probabilistic programming, Mathematical Programming, 89, 217-232 (2001) [9] Gendreau, M.; Laporte, G.; Séguin, R., Stochastic vehicle routing, European Journal of Operational Research, 88, 3-12 (1996) · Zbl 0913.90094 [10] B.T. Lowerre, The HARPY speech recognition system, Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA; B.T. Lowerre, The HARPY speech recognition system, Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA [11] Miller, L. B.; Wagner, H., Change-constrained programming with joint constraints, Operations Research, 13, 930-945 (1965) · Zbl 0132.40102 [12] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), John Wiley & Sons: John Wiley & Sons New York · Zbl 0469.90052 [13] Owen, S. H.; Daskin, M. S., Strategic facility location: A review, European Journal of Operational Research, 111, 423-447 (1998) · Zbl 0938.90048 [14] A. Prékopa, On probabilistic constrained programming, in: Proceedings of the Princeton Symposium on Mathematical Programming, Princeton University Press, 1970, pp. 113-138; A. Prékopa, On probabilistic constrained programming, in: Proceedings of the Princeton Symposium on Mathematical Programming, Princeton University Press, 1970, pp. 113-138 [15] Prékopa, A., Contributions to the theory of stochastic programming, Mathematical Programming, 4, 202-221 (1973) · Zbl 0273.90045 [16] Prékopa, A., Dual method for solution of one-stage stochastic programming with random RHS obeying a discrete probability distribution, Zeitschrift für Operations Research, 34, 441-461 (1990) · Zbl 0724.90048 [17] Prékopa, A., Stochastic Programming (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0834.90098 [18] Prékopa, A.; Vizvári, D.; Badics, T., Programming under probabilistic constraint with discrete random variable, (Giannesi, F., New Trends in Mathematical Programming (1998), Kluwer Academic Publishers), 235-255 · Zbl 0907.90215 [19] Sabuncuoglu, I.; Bayiz, M., Job shop scheduling with beam search, European Journal of Operational Research, 118, 390-412 (1999) · Zbl 0940.90037 [20] Sen, S., Relaxations for the probabilistically constrained programs with discrete random variables, Operations Research Letters, 11, 81-86 (1992) · Zbl 0765.90071 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.