mlsanityData to 14 Oct 2026

Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks

arXiv 2508.20056 ↗First posted 27 Aug 2025cs.LGcited by 2

On the map: Deep reinforcement learning methods → RL for energy, networks and operations

Abstract (arXiv)

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.1 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-second 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.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL for energy, networks and operations, one of 15 directions in Deep reinforcement learning methods. Builds on 8 of its 56 references that are in the map. First posted on arXiv 27 Aug 2025.

Builds on

8 of 56 references.

References · 8

  1. 2019Optuna: A Next-generation Hyperparameter Optimization Frameworkcited by 2,501
  2. 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policiescited by 63
  3. 2021SeaPearl: A Constraint Programming Solver guided by Reinforcement Learningcited by 6
  4. 2024Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardinesscited by 6
  5. 2018Learning Robust Search Strategies Using a Bandit-Based Approachcited by 4
  6. 2020Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problemcited by 3
  7. 2023Constraint Programming and Constructive Heuristics for Parallel Machine Scheduling with Sequence-Dependent Setups and Common Serverscited by 3
  8. 2025Bottleneck Identification in Resource-Constrained Project Scheduling via Constraint Relaxationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approachcited by 0
  2. 2026Schedulable Job-Level Dependencies for Cause-Effect Chains via Graph Neural Networkscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
  2. 2024Graph Neural Networks for Job Shop Scheduling Problems: A Survey
  3. 2024Learning to Solve Job Shop Scheduling under Uncertainty
  4. 2024Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem
  5. 2025Optimizing Job Allocation using Reinforcement Learning with Graph Neural Networks
  6. 2024Offline Reinforcement Learning for Learning to Dispatch for Job Shop Scheduling
  7. 2025Learning to Solve Resource-Constrained Project Scheduling Problems with Duration Uncertainty using Graph Neural Networks
  8. 2022Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning