Change search
ReferencesLink to record
Permanent link

Direct link
Hybridizing constraint programming and Monte-Carlo tree search: Application to the job shop problem
Show others and affiliations
2013 (English)In: Lecture Notes in Computer Science / [ed] Giuseppe Nicosia and Panos Pardalos, 2013, 315-320 p.Conference paper (Refereed)
Abstract [en]

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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-136456DOI: 10.1007/978-3-642-44973-4_35ScopusID: 2-s2.0-84890947392ISBN: 978-364244972-7OAI: diva2:676217
7th International Conference on Learning and Intelligent Optimization, LION 7; Catania, Italy, 7-11 January 2013

QC 20140114

Available from: 2013-12-05 Created: 2013-12-05 Last updated: 2014-01-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer systems, SCS
Computer 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

Altmetric score

Total: 28 hits
ReferencesLink to record
Permanent link

Direct link