Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop problem
Manuel Loth, Michèle Sebag, Youssef Hamadi, Marc Schoenauer, Christian Schulte.
Constraint Programming (CP) solvers classically explore the solution space using tree search-based heuristics. Monte-Carlo Tree-Search (MCTS), a tree search-based method aimed at sequential decision making under uncertainty, simultaneously estimates the reward associated to the sub-trees, and gradually biases the exploration toward the most promising sub-trees. This paper examines the tight combination of MCTS and CP on the job shop problem (JSP). The contribution is twofold. Firstly, a reward function compliant with a multiple restart policy is proposed. Secondly, a biased MCTS node selection rule based on this reward is proposed. Its integration within the Gecode constraint solver is shown to compete with JSP-specific CP approaches on difficult JSP instances.
In: Giuseppe Nicosia, Panos Pardalos, editors, Learning and Intelligent OptimizatioN Conference (Lion 7), Catania, Italy. January, 2013.