Skip to Main content Skip to Navigation
Conference papers

Bandit-based Search for Constraint Programming

Manuel Loth 1 Michèle Sebag 2 Youssef Hamadi 1, 3, 4 Marc Schoenauer 2, 5
5 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Constraint Programming (CP) solvers classically explore the solution space using tree-search based heuristics. Monte-Carlo Tree-Search (MCTS) is a method aimed at optimal sequential decision making under uncertainty. It simultaneously estimates node values (with respect to some reward function) by Monte-Carlo trials and uses them to bias the exploration towards the most promising regions of the tree, borrowing the multi-armed-bandit decision rule. At the crossroads of CP and MCTS, this paper presents the Bandit Search for Constraint Programming (BASCOP) algorithm, adapting MCTS to the specifics of CP search trees. These adaptations concern i) the design of a generic reward function suited for CP problems; ii) the replacement of Monte-Carlo trials by iterations of a complete depth-first-search procedure; iii) the ability to take into account an existing value-ordering heuristics; iv) the aggregation of statistics in order to handle multiple restarts. BASCOP, using Gecode as the underlying constraint solver, shows significant improvements over the depth-first-search baseline on some CP benchmark suites, demonstrating its potential as a generic yet robust search method for CP.
Document type :
Conference papers
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download
Contributor : Manuel Loth Connect in order to contact the contributor
Submitted on : Wednesday, September 18, 2013 - 9:43:32 PM
Last modification on : Thursday, July 8, 2021 - 3:48:11 AM
Long-term archiving on: : Friday, December 20, 2013 - 3:04:35 PM


Publisher files allowed on an open archive


  • HAL Id : hal-00863451, version 1



Manuel Loth, Michèle Sebag, Youssef Hamadi, Marc Schoenauer. Bandit-based Search for Constraint Programming. International Conference on Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. pp.464-480. ⟨hal-00863451⟩



Record views


Files downloads