Bandit-based search for constraint programming
2013 (English)In: AAAI Workshop - Technical Report: Volume WS-13-07, 2013, AI Access Foundation , 2013, 8-13 p.Conference paper (Refereed)
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.
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
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-147273ScopusID: 2-s2.0-84898865077ISBN: 978-157735618-9OAI: oai:DiVA.org:kth-147273DiVA: diva2:729801
2013 AAAI Workshop; Bellevue, WA; United States; 14 July 2013 through 14 July 2013
QC 201406262014-06-262014-06-252014-06-26Bibliographically approved