Innovations in Constraint Programming and Scheduling: TUPLES Contributions at the CP/SoCS/SAT 2025 Conference

Here’s a short overview of each contribution, with links to the corresponding papers for those who’d like to explore further.

Award-Winning Industrial Application

A major highlight was the paper “Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem” by Ignace Bleukx, Ryma Boumazouza, Tias Guns, Nadine Laage, and Guillaume Poveda, which received the Best Application Paper Award. The research addresses the complex task of allocating and scheduling workforces in aircraft manufacturing, a domain where disruptions due to technical failures, weather conditions, or resource unavailability are frequent.
The paper introduces advanced CP models that balance efficiency and fairness in workforce allocation, while also embedding explainability into the decision-support process. Techniques such as Minimal Unsatisfiable Subsets (MUSes) and Minimal Correction Subsets (MCSes) allow planners to understand why schedules fail and explore automated repair strategies. This award-winning work exemplifies TUPLES’ mission: developing trustworthy, robust, and explainable AI tools that can be deployed in real-world industrial contexts.
See the full paper here: https://bit.ly/41lVrpf

New Solver Architectures for Scheduling

Another paper, “Disjunctive Scheduling in Tempo” by Emmanuel Hebrard, presents Tempo, a novel hybrid CP/SAT solver. Tempo integrates lazy clause generation with difference logic, making it particularly effective for temporal and scheduling problems. Its design leverages edges in temporal graphs as branching variables, combining propagation and inference in an elegant and efficient way.
Experiments on job-shop scheduling benchmarks demonstrate that Tempo achieves competitive performance with state-of-the-art solvers like OR-Tools and CP Optimizer, while maintaining a simpler and more transparent architecture. This work underscores the importance of solver design choices and opens promising directions for extending hybrid methods to broader classes of scheduling and resource allocation problems.

See the full paper here:https://bit.ly/45KmyLX

Understanding the Role of Heuristics

The third contribution, “Understanding the Impact of Value Selection Heuristics in Scheduling Problems” by Tim Luchterhand, Emmanuel Hebrard, and Sylvie Thiébaux, sheds light on the often-overlooked role of value selection heuristics in constraint programming.
Through extensive experiments, the authors show that while value heuristics generally have less impact than variable ordering, their role becomes critical in hard scheduling problems. Surprisingly, they find that heuristic accuracy tends to decrease as the problem becomes tighter, exactly when mistakes become most costly. Moreover, sophisticated heuristics, while more accurate overall, pay a disproportionately higher price when they make an error.
This nuanced analysis provides a deeper understanding of why designing impactful value selection heuristics is challenging, offering guidance for future heuristic design and integration with machine learning approaches.

See the full paper here: https://bit.ly/4oVrN4v

Prominent Paper Award

We are also delighted to celebrate Hélène Verhaeghe, who was a member of the TUPLES consortium, for receiving the Prominent Paper Award of the Constraints Journal for her work “Learning Optimal Decision Trees Using Constraint Programming”, co-authored with Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus.

A Strong Presence at CP 2025

Together, these three papers illustrate the breadth and depth of TUPLES’ contributions to the constraint programming community: from award-winning industrial applications, to innovative solver architectures, to fundamental insights into search heuristics.
By combining applied impact with theoretical advances, TUPLES researchers are pushing the boundaries of trustworthy, explainable, and high-performance AI for scheduling—advancing both the science and its deployment in real-world domains.