Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Interleaving Innovization with Evolutionary Multi-Objective Optimization in Production System Simulation for Faster Convergence Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop Problem

Authors : Manuel Loth, Michéle Sebag, Youssef Hamadi, Marc Schoenauer, Christian Schulte

Published in: Learning and Intelligent Optimization

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Multiobjective Evolution of Mixed Nash Equilibria
next chapter From Grammars to Parameters: Automatic Iterated Greedy Design for the Permutation Flow-Shop Problem with Weighted Tardiness
Literature
1.
Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2–3), 235–256 (2002)CrossRefMATH
2.
Beck, J.C.: Solution-guided multi-point constructive search for job shop scheduling. J. Artif. Intell. Res. 29, 49–77 (2007)MATH
3.
4.
Gelly, S., et al.: The grand challenge of computer go: monte carlo tree search and extensions. Commun. ACM 55(3), 106–113 (2012)CrossRef
5.
Kocsis, L., Szepesvári, C.: Bandit based monte-carlo planning. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 282–293. Springer, Heidelberg (2006)CrossRef
6.
7.
Mathon, R., Rosa, A.: Tables of parameters for BIBD’s with \(r\le 41\) including existence, enumeration, and resolvability results. Ann. Discrete Math. 26, 275–308 (1985)MathSciNet
8.
Meseguer P.: Interleaved depth-first search. In: IJCAI 1997, vol. 2, pp. 1382–1387 (1997)
9.
Rimmel, A., Teytaud, F., Teytaud, O.: Biasing monte-carlo simulations through RAVE values. In: ICCG 2010, pp. 59–68 (2010)
10.
Runarsson, T.P., Schoenauer, M., Sebag, M.: Pilot, rollout and monte carlo tree search methods for job shop scheduling. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, vol. 7219, pp. 160–174. Springer, Heidelberg (2012)
11.
Watson, J.-P., Beck, J.C.: A hybrid constraint programming/local search approach to the job-shop scheduling problem. In: Trick, M.A. (ed.) CPAIOR 2008. LNCS, vol. 5015, pp. 263–277. Springer, Heidelberg (2008)
Metadata
Title
Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop Problem
Authors
Manuel Loth
Michéle Sebag
Youssef Hamadi
Marc Schoenauer
Christian Schulte
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Learning and Intelligent Optimization

Print ISBN: 978-3-642-44972-7

Electronic ISBN: 978-3-642-44973-4

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-44973-4_35

Premium Partner

    Image Credits