Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop problem

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 sub-trees, and gradually biases the exploration toward the most promising regions. 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 the CP setting is proposed. Secondly, a biased MCTS node-selection rule based on this reward is proposed, that is suitable in a multiple-restarts context. Its integration within the Gecode constraint solver is shown to compete with JSP-specific CP approaches on difficult JSP instances.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00863453
Contributor : Manuel Loth <>
Submitted on : Wednesday, September 18, 2013 - 9:51:22 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on : Friday, December 20, 2013 - 3:04:43 PM

File

Paper_67_camera_ready.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00863453, version 1

Collections

Citation

Manuel Loth, Michèle Sebag, Youssef Hamadi, Marc Schoenauer, Christian Schulte. Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop problem. LION7 - Learning and Intelligent OptimizatioN Conference, Jan 2013, Catania, Italy. pp.315-320. ⟨hal-00863453⟩

Share

Metrics

Record views

1003

Files downloads

436