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.
Type de document :
Communication dans un congrès
Christian Schulte. International Conference on Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. Springer Verlag, 8124, pp.464-480, 2013, LNCS
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00863451
Contributeur : Manuel Loth <>
Soumis le : mercredi 18 septembre 2013 - 21:43:32
Dernière modification le : jeudi 12 avril 2018 - 01:48:11
Document(s) archivé(s) le : vendredi 20 décembre 2013 - 15:04:35

Fichier

paper123.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00863451, version 1

Collections

Citation

Manuel Loth, Michèle Sebag, Youssef Hamadi, Marc Schoenauer. Bandit-based Search for Constraint Programming. Christian Schulte. International Conference on Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. Springer Verlag, 8124, pp.464-480, 2013, LNCS. 〈hal-00863451〉

Partager

Métriques

Consultations de la notice

632

Téléchargements de fichiers

867