Beam search heuristic to solve stochastic integer problems under probabilistic constraints

Patrizia Beraldi, Andrzej Ruszczyński

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)35-47
Number of pages13
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - Nov 16 2005

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Beam search heuristic
  • Combinatorial optimization
  • Stochastic programming


Dive into the research topics of 'Beam search heuristic to solve stochastic integer problems under probabilistic constraints'. Together they form a unique fingerprint.

Cite this