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 metadatas

Cited literature [39 references]  Display  Hide  Download

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

File

paper123.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00863451, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

773

Files downloads

1162