Monte Carlo Rollout method for optimization under uncertainty

To optimize a combinatorial problem one can use complex algorithms, e.g. branchand- bound algorithms. However, these are time consuming for extensive problems. By the need of real-time decisions in industrial applications, complex algorithms are inapplicable. Additionally, as a consequence of changes, solutions have to be calculated very often to adapt plans to the changes. Another aspect that makes a fast solution necessary. The Monte Carlo rollout method (MCR) is a novel approach for the approximate solution of combinatorial optimization problems. The MCR approach combines ideas from rollout algorithms for combinatorial optimization and the Monte Carlo tree search in game theory. In this paper the results of an investigation of applying the MCR to a repairing bin packing problem and a scheduling problem are shown. Influences of the model parameters, search depth and search width, are examined as well as the influence of process parameters. It also deals with the quest ion as to whether the Lookahead Pathology occurs as identified in game theory.