Bandit-based Search for Constraint Programming - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Bandit-based Search for Constraint Programming

(1) , (2) , (1, 3, 4) , (2, 5)
1
2
3
4
5

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.
Fichier principal
Vignette du fichier
paper123.pdf (184.44 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-00863451 , version 1 (18-09-2013)

Identifiers

  • HAL Id : hal-00863451 , version 1

Cite

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⟩
463 View
1071 Download

Share

Gmail Facebook Twitter LinkedIn More