Reinforcement learning for search tree size minimization in Constraint Programming: New results on scheduling benchmarks
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00384962" target="_blank" >RIV/68407700:21230/25:00384962 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/25:00384962
Result on the web
<a href="https://doi.org/10.1016/j.cie.2025.111413" target="_blank" >https://doi.org/10.1016/j.cie.2025.111413</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.cie.2025.111413" target="_blank" >10.1016/j.cie.2025.111413</a>
Alternative languages
Result language
angličtina
Original language name
Reinforcement learning for search tree size minimization in Constraint Programming: New results on scheduling benchmarks
Original language description
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 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Computers & Industrial Engineering
ISSN
0360-8352
e-ISSN
1879-0550
Volume of the periodical
209
Issue of the periodical within the volume
November
Country of publishing house
GB - UNITED KINGDOM
Number of pages
23
Pages from-to
—
UT code for WoS article
001723926200001
EID of the result in the Scopus database
2-s2.0-105014103087