Hybridizing Constraint Programming and Monte-Carlo Tree Search: Application to the Job Shop Problem
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 r
- PDF / 226,859 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 220 Views
bstract. Constraint Programming (CP) solvers classically explore the solution space using tree search-based heuristics. Monte-Carlo TreeSearch (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.
1
Introduction
This paper focuses on hybridizing Constraint Programming (CP) and MonteCarlo Tree Search (MCTS) methods. The proof of concept of the approach is given on the job-shop problem (JSP), where JSPs are modelled as CP problem instances, and MCTS is hybridized with the Gecode constraint solver environment [3]. This paper first briefly presents the JSP modeling in constraint programming and the MCTS framework, referring the reader to respectively [2] and [4,5] for a comprehensive presentation. The proposed hybrid approach, referred to as Bandit-Search for Constraint-Programming (BaSCoP), is thereafter described. The first experimental results on the difficult Taillard 11-20 20 × 15 problem instances are presented in Sect. 5. The paper concludes with a discussion w.r.t related work [10], and some perspectives for further research.
2
CP-Based Resolution of JSP
The job-shop problem, one of the classical scheduling problems, is concerned with allocating jobs to machines while minimizing the overall makespan. The G. Nicosia and P. Pardalos (Eds.): LION 7, LNCS 7997, pp. 315–320, 2013. c Springer-Verlag Berlin Heidelberg 2013 DOI: 10.1007/978-3-642-44973-4 35,
316
M. Loth et al.
CP modelling of JSP proceeds by considering a sequence of problems: after a given solution with makespan m has been found, the problem is modified by adding the constraint makespan < m. While specific JSP-driven heuristics have been used in CP approaches, e.g. [11], our goal in this paper is to investigate the coupling of a generic CP framework, specifically Gecode [3], with MCTS. The JSP modeling in Gecode, inspired from the reportedly best CP approach to JSP [2], is as follows: – the restart policy follows a Luby sequence [6]: the search is restarted after the specified number of failures is reached or when a new solution is found; – the variable ordering is based on the weighted-degree heuristics − found as Max Accumulated Failure Count (AfcMax) in Gecode [3]; – the search heuristics is a Depth-First-Search, starting from the last found solution, i.e. the left value associated to a variable is the value assigned to this variable in the previous best solution.
3
Monte-Carlo Tree Search
MCTS [5] is concerned with optimal sequential decis
Data Loading...
