Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop problem
Manuel Loth, Michèle Sébag, Youssef Hamadi, Marc Schoenauer, Christian Schulte, Université Paris-sud · 2013
Abstract. 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 subtrees, and gradually biases the exploration toward the most promising subtrees. 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. 1