Rollout Algorithms for Combinatorial Optimization Problems

Rollout algorithms are new computational approaches used to determine near-optimal solutions for deterministic and stochastic combinatorial optimization problems. They are built on a generic base heuristic with the aim to construct another hopefully improved heuristic. However, rollout algorithms can be very expensive from the computational point of view, so their use for practical applications can be limited. In this article, we propose modified version of the rollout algorithms to solve deterministic optimization problems, defined in such a way to limit the computational cost, without worsening the quality of the final approximate solution obtained.