Change search
ReferencesLink to record
Permanent link

Direct link
Bandit-based search for constraint programming
Show others and affiliations
2013 (English)In: AAAI Workshop - Technical Report: Volume WS-13-07, 2013, AI Access Foundation , 2013, 8-13 p.Conference paper (Refereed)
Abstract [en]

Constraint Programming (CP) solvers classically explore the solution space using tree-search based heuristics. MonteCarlo Tree-Search (MCTS) is a tree-search method aimed at optimal sequential decision making under uncertainty. 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. Formally, MCTS simultaneously estimates the average node reward, and uses it to bias the exploration towards the most promising regions of the tree, borrowing the multi-armed bandit (MAB) decision rule. The two contributions in BASCOP concern i) a specific reward function, estimating the relative failure depth conditionally to a (variable, value) assignment; ii) a new decision rule, hybridizing the MAB framework and the spirit of local neighborhood search. Specifically, BASCOP guides the CP search in the neighborhood of the previous best solution, by exploiting statistical estimates gathered across multiple restarts. BASCOP, using Gecode as the underlying constraint solver, shows significant improvements over the depthfirst search baseline on some CP benchmark suites. For hard job-shop scheduling problems, BASCOP matches the results of state-of-the-art scheduling-specific CP approaches. These results demonstrate the potential of BASCOP as a generic yet robust search method for CP.

Place, publisher, year, edition, pages
AI Access Foundation , 2013. 8-13 p.
Keyword [en]
Estimation, Forestry, Logic programming, Trees (mathematics), Constraint programming, Constraint solvers, Depth first search, Job shop scheduling problems, Local neighborhood searches, Multi armed bandit, Optimal sequential, Tree-search methods, Constraint theory
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-147273ScopusID: 2-s2.0-84898865077ISBN: 978-157735618-9OAI: diva2:729801
2013 AAAI Workshop; Bellevue, WA; United States; 14 July 2013 through 14 July 2013

QC 20140626

Available from: 2014-06-26 Created: 2014-06-25 Last updated: 2014-06-26Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer systems, SCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 23 hits
ReferencesLink to record
Permanent link

Direct link