Hybridizing constraint programming and Monte-Carlo tree search: Application to the job shop problem
2013 (English)In: Lecture Notes in Computer Science / [ed] Giuseppe Nicosia and Panos Pardalos, 2013, 315-320 p.Conference paper (Refereed)
Constraint Programming (CP) solvers classically explore the solution space using tree search-based heuristics. Monte-Carlo Tree-Search (MCTS), a tree-search based method aimed at sequential decision making under uncertainty, simultaneously estimates the reward associated to the sub-trees, and gradually biases the exploration toward the most promising regions. This paper examines the tight combination of MCTS and CP on the job shop problem (JSP). The contribution is twofold. Firstly, a reward function compliant with the CP setting is proposed. Secondly, a biased MCTS node-selection rule based on this reward is proposed, that is suitable in a multiple-restarts context. Its integration within the Gecode constraint solver is shown to compete with JSP-specific CP approaches on difficult JSP instances.
Place, publisher, year, edition, pages
2013. 315-320 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; Vol. 7997
IdentifiersURN: urn:nbn:se:kth:diva-136456DOI: 10.1007/978-3-642-44973-4_35ScopusID: 2-s2.0-84890947392ISBN: 978-364244972-7OAI: oai:DiVA.org:kth-136456DiVA: diva2:676217
7th International Conference on Learning and Intelligent Optimization, LION 7; Catania, Italy, 7-11 January 2013
QC 201401142013-12-052013-12-052014-01-23Bibliographically approved