Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks Journal: Computers & Industrial Engineering
Vilém Heinz, Petr Vilím, Zdeněk Hanzálek · 2025
Read Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks Journal: Computers & Industrial Engineering by Vilém Heinz, Petr Vilím, Zdeněk Hanzálek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20056.txt.
Introduction
Vilém Heinz, Petr Vilím, and Zdeněk Hanzálek speed up a scheduling search method with reinforcement learning, in this 2025 paper. Failure-directed search is a strong generic tool in constraint programming, and it shines on scheduling. The authors show that shrinking its search tree is closely tied to the multi-armed bandit problem, a classic learning setup.
They plug bandit algorithms into the search, tune them with problem-specific tweaks, and test on job shop and project scheduling sets. The enhanced search ran much faster than both the original and a leading commercial solver. It also improved most known lower bounds on open benchmark cases within a fifteen-minute limit.
Catalog record
| CREATOR | Vilém Heinz, Petr Vilím, Zdeněk Hanzálek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20056
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks Journal: Computers & Industrial Engineering Vilém Heinz, Petr Vilím, Zdeněk Hanzálek Abstract Failure-Directed Search (FDS) is a significant complete generic search algorithm used in Constraint Programming (CP) to efficiently explore the search space, proven particularly effective on scheduling problems. This paper analyzes FDS’s properties, showing that minimizing the size of its search tree guided by ranked branching decisions is closely related to the Multi-armed bandit (MAB) problem. Building on this insight, MAB reinforcement learning algorithms are applied to FDS, extended with problem-specific refinements and parameter tuning, and evaluated on the two most fundamental scheduling problems, the Job Shop Scheduling Problem (JSSP) and Resource-Constrained Project Scheduling Problem (RCPSP). The resulting enhanced FDS, using the best extended MAB algorithm and configuration, performs 1.7 times faster on the JSSP and 2.5 times faster on the RCPSP benchmarks compared to the original implementation in a new solver called OptalCP, while also being 3.5 times faster on the JSSP and 2.1 times faster on the RCPSP benchmarks than the current state-of-the-art FDS algorithm in IBM CP Optimizer 22.1. Furthermore, using only a 900 s 900\text{\,}\mathrm{s} time limit per instance, the enhanced FDS improved the existing state-of-the-art lower bounds of 78 of 84 JSSP and 226 of 393 RCPSP standard open benchmark instances while also completely closing a few of them. 2020 MSC 90-08 , 90B35 , 90C59 , 90C99 , 68T20 , 90C27 1 Introduction Constraint Programming (CP) is a declarative programming paradigm similar to Integer Linear Programming (ILP). It is used for various combinatorial problems, but it particularly excels in scheduling problems. Its application in this area often yields state-of-the-art results for both well-known general problems like [ 1 , 2 , 3 ] , as well as for more specific problems with many additional constraints like [ 4 , 5 , 6 ] , usually outperforming ILP [ 7 , 8 ] . This paper discusses Failure-Directed Search (FDS), a complete generic search algorithm designed to explore the search space of CP problems systematically and efficiently. FDS was introduced in [ 9 ] as an algorithm to prove optimality / infeasibility (and lower bounds 1 1 1 A value such that any smaller value of the objective is known to be unattainable. for minimization problems). It uses a Fail-First search strategy and a tree structure to navigate the search. FDS is used in IBM CPLEX CP Optimizer [ 10 ] (further referred to as CP Optimizer), and was often the algorithm responsible for proving the optimality of the solutions to the scheduling problems reported recently; see, e.g., [ 11 , 12 ] . CP Optimizer is considered the state-of-the-art solver for many classes of scheduling problems (e.g, [ 11 , 4 , 5 , 6 , 7 , 8 , 12 ] ), and although users of CP Optimizer may not notice it, FDS is an important component of this success. We implemented FDS as described in [ 9 ] in a new CP solver called OptalCP with the goal of getting a deeper understanding of its notable performance and used these insights to further improve it by reducing its search tree size. Formally, problems modeled with CP and solved by CP solvers like OptalCP or CP Optimizer are called Constraint Satisfaction Problems (CSPs). A CSP is characterized by a finite set of variables (the unknowns), each with its domain (a finite set of possible values) and a finite set of constraints over the variables that must be satisfied. These constraints can take various forms, such as equations, inequalities, their boolean combinations, or special global constraints like NoOverlap . We refer the reader to [ 13 ] for a more detailed understanding of the CSP formulation. Then, the CP solver’s task is to find variable assignments from their domains (a solution) that also satisfies all given constraints. Additionally, if an objective function is provided, the CSP becomes a Constrained Optimization Problem (COP). In this case, the CP solver not only searches for a feasible solution but also aims to minimize or maximize the objective function. We will further denote any CSP or COP simply as a Constrained Combinatorial Problem (CCP) because, for our purposes, the difference does not matter. In general, CCPs are \mathcal{NP} -hard problems. So, to find the optimal solution of a CCP, the CP solver needs to explore the search space exhaustively, which is where FDS comes into the picture. To improve the speed of the FDS algorithm, we propose a two-pronged approach combining Reinforcement Learning (RL) and parameter tuning, that aims at reducing the number of created search nodes (reducing the search tree size) while still covering the whole search space. The remainder of this paper is structured as follows. In Section 2 , we review the existing literature on CCP-related search algorithms, the use of machine learning for search guidance, and the combination of the two. In Section 3 , we lay the theoretical foundation by analyzing the properties of FDS and showing that minimizing its search tree can be interpreted as the well-known RL Multi-Armed Bandit (MAB) problem [ 14 ] . Based on this fact, in Section 4 we present four existing RL MAB algorithms that address the exploration-exploitation dilemma, a key aspect not considered in the original FDS. Search-guiding (choice-selection) strategies based on those algorithms are discussed, and a problem-specific improvement called choice rollback is proposed to increase their efficiency. Furthermore, in Section 4.2 , we discuss the tuning of the FDS parameters to improve its performance further. Although parameter tuning is often neglected, papers like [ 15 , 16 ] show that it is often a significant aspect of algorithm performance. In Section 5 , we describe the experimental setup and briefly introduce the OptalCP solver whose implementation of FDS we use in the experiments. In Section 6 , we provide detailed results measuring the performance of the proposed choice-selection strategies and tuning and compare it with the state-of-the-art. Finally, in Section 7 we summarize the main contributions, findings, and potential directions for future research. The main contributions of this paper are as follows. We propose new effective search strategies for the FDS algorithms, a state-of-the-art exhaustive search method in Constraint Programming. We conduct a systematic exploration of the FDS parameters and provide insights into how they influence search efficiency. We validate our approach through extensive experiments on standard benchmark datasets for two fundamental scheduling problems, JSSP and RCPSP, demonstrating that: (i) the runtime of the original FDS is reduced by half, (ii) the enhanced FDS is 2 to 4 times faster than the state-of-the-art implementation in CP Optimizer, and (iii) the state-of-the-art results in the standard benchmark sets are significantly improved. 2 Related Work The related literature can be grouped into three main categories based on their relevance to our research focus: (i) works that address Constraint Combinatorial Problems (CCPs) using search heuristics and algorithms without involving machine learning (see Section 2.1 ), (ii) works that use machine learning to guide search processes, such as branching decisions (see Section 2.2 ), and (iii) works that apply machine learning algorithms, specifically Multi-armed bandit ones, to the CCP search (see