Rollout Algorithms for Combinatorial Optimization

Dimitri P. Bertsekas, John N. Tsitsiklis, Cynara Wu

Research output: Contribution to journalArticlepeer-review

187 Scopus citations


We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential application. In particular, we embed the problem within a dynamic programming framework, and we introduce several types of rollout algorithms, which are related to notions of policy iteration. We provide conditions guaranteeing that the rollout algorithm improves the performance of the original heuristic algorithm. The method is illustrated in the context of a machine maintenance and repair problem.

Original languageEnglish (US)
Pages (from-to)245-262
Number of pages18
JournalJournal of Heuristics
Issue number3
StatePublished - 1997
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'Rollout Algorithms for Combinatorial Optimization'. Together they form a unique fingerprint.

Cite this