Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
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
Identifiers
URN: urn:nbn:se:kth:diva-136456DOI: 10.1007/978-3-642-44973-4_35Scopus ID: 2-s2.0-84890947392ISBN: 978-364244972-7 (print)OAI: oai:DiVA.org:kth-136456DiVA: diva2:676217
Conference
7th International Conference on Learning and Intelligent Optimization, LION 7; Catania, Italy, 7-11 January 2013
Note

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

Authority records BETA

Schulte, Christian

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 59 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf