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.
Type de document :
Communication dans un congrès
Nicosia, Giuseppe and Pardalos, Panos. LION7 - Learning and Intelligent OptimizatioN Conference, Jan 2013, Catania, Italy. Springer Verlag, 7997, pp.315-320, 2013, LNCS
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00863453
Contributeur : Manuel Loth <>
Soumis le : mercredi 18 septembre 2013 - 21:51:22
Dernière modification le : jeudi 10 mai 2018 - 02:06:23
Document(s) archivé(s) le : vendredi 20 décembre 2013 - 15:04:43

Fichier

Paper_67_camera_ready.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Nicosia, Giuseppe and Pardalos, Panos. LION7 - Learning and Intelligent OptimizatioN Conference, Jan 2013, Catania, Italy. Springer Verlag, 7997, pp.315-320, 2013, LNCS. 〈hal-00863453〉

Partager

Métriques

Consultations de la notice

799

Téléchargements de fichiers

334