EURO 2025 Leeds
Abstract Submission

1765. Accelerating Constraint Programming Using OptalCP Solver: Results on Jobshop and RCPSP

Invited abstract in session MD-7: Extensions of the Resource-Constrained Project Scheduling Problem, stream Scheduling and Project Management.

Monday, 14:30-16:00
Room: Clarendon GR.01

Authors (first author is the speaker)

1. Zdenek Hanzalek
CTU Prague
2. Vilem Heinz
Czech Technical University in Prague
3. Petr Vilím
ScheduleOpt
4. Simon Zvara
CTU Prague
5. Vit Knobloch
CTU Prague

Abstract

This presentation discusses the application of reinforcement learning (RL) and metaheuristic algorithms to enhance the performance of the constraint programming (CP) solver OptalCP.
Building on our previous research, we propose an extension of an RL framework originally based on the Multi-Armed Bandit algorithm used to select promising branching decisions (branches) in the search tree.
In this work, instead of precomputing all branches at the start, branches are computed on-the-go by neural network within a REINFORCE algorithm.
This enables dynamic adaptation of branching decisions based on the current search tree context.
Meanwhile, metaheuristic algorithms integrated to the solver through communication interface, enhance its ability to identify promising solutions faster and more efficiently, providing both solutions and bounds which can be utilized by the solver.
The combined goal of these approaches is twofold: reinforcement learning primarily improves the solver’s ability to reach the optimal solution sooner, while metaheuristics focus on delivering high-quality solutions within practical time limits.
While our approach is demonstrated using OptalCP, it is applicable to any CP solver that employs branch-based algorithms for optimal solution search, is sufficiently open to allow code modifications, and provides an interface for real-time interaction with external algorithms.

Keywords

Status: accepted

Back to the list of papers