🤖 AI

On inferring cumulative constraints

This paper presents a preprocessing method that infers additional cumulative constraints by identifying task covers and applying lifting to strengthen them, thereby capturing multi-resource interactions that improve search performance and objective bounds in scheduling problems without significant overhead.

Original authors: Konstantin Sidorov

Published 2026-07-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Konstantin Sidorov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, chaotic orchestra where every musician is also a stagehand. You have a limited number of microphones, a finite amount of spotlight power, and only so many props to go around. Your job is to schedule every musician's solo and every stagehand's move so that no two people try to grab the same microphone at the exact same second, and the entire show finishes as quickly as possible. This is the heart of a field called Constraint Programming. It's a branch of computer science dedicated to solving puzzles where you have to fit many moving parts into a tight box without anything breaking.

In this world, a "Cumulative Constraint" is like a rule that says, "At any given moment, the total weight of everyone on stage cannot exceed the floor's limit." For decades, computers have been getting very good at checking this rule for one resource at a time—like checking the microphones, then checking the lights, then checking the props. But here's the catch: sometimes the real trouble isn't just one resource; it's the messy, hidden dance between them. A group of musicians might not be fighting over a microphone, but if they all try to use the same prop and the same spotlight simultaneously, the whole show grinds to a halt. The old way of checking these rules one by one often misses these hidden traffic jams, causing the computer to spin its wheels for hours, trying to find a solution that might not even exist.

This is where the paper by Konstantin Sidorov steps in. The author proposes a clever new way to look at the schedule before the computer even starts its main search. Instead of just checking the rules as they are, the paper suggests a "pre-game" strategy where the computer looks for groups of tasks that simply cannot happen together, no matter how you shuffle the schedule. Think of it as a detective realizing that three specific musicians are so demanding that if they are all on stage, the show collapses. The paper calls these groups "covers."

The core idea is to find these impossible groups and then use a mathematical trick called "lifting" to turn them into super-rules. Imagine you know that three musicians can't be on stage together. Lifting is like asking, "Okay, but what if we add a fourth musician? Can they join the party?" The math figures out exactly how many people can be on stage at once without breaking the rules, creating a new, tighter constraint. The paper then injects these new, super-tight rules back into the scheduling problem.

The results are promising. When the author tested this method on standard scheduling puzzles (known as RCPSP benchmarks), the computer didn't just work faster; it found better schedules and proved that certain schedules were impossible much quicker than before. In fact, the new method helped discover 25 new "best possible" lower bounds (meaning we now know for sure a show can't be finished in less than X minutes) and found five completely new best solutions for specific puzzles. Interestingly, the paper notes that while this method is a huge win for problems with hidden complexity, it doesn't hurt performance on simpler problems that don't have these tricky structures. It's a bit like adding a turbocharger to a car: it gives you a massive speed boost on the racetrack, but if you're just driving to the grocery store, it doesn't make the car slower, it just sits there quietly until you need it. The author suggests that by catching these hidden interactions early, we can solve scheduling nightmares that used to leave computers stuck in a loop of confusion.

Technical Summary: On Inferring Cumulative Constraints

Problem Statement

Cumulative constraints are a cornerstone of constraint programming (CP) for scheduling, modeling limited renewable resources. However, standard propagation techniques typically reason about each resource constraint independently. This "single-resource viewpoint" fails to capture interactions between multiple resources, leading to severe performance degradation on specific benchmarks (e.g., the "3n problem" structure).

Previous attempts to address this, such as the "Unite and Lead" (UNL) approach by Sidorov et al. [2025a], successfully identified hidden disjunctive structures (sets of tasks that cannot run in parallel). However, UNL suffers from two critical limitations:

Lack of Generality: It is restricted to disjunctive reasoning and cannot derive more general multi-resource interactions.
Search Overhead: It requires explicit probing for disjunctive cliques during the search, incurring significant overhead that often slows down solvers by an order of magnitude on instances lacking such structures.

The core problem addressed in this paper is how to infer valid multi-resource interactions and strengthen the model without incurring the search-time penalties associated with dynamic clique detection.

Methodology

The proposed approach reframes cumulative constraints as linear inequalities over occupancy vectors and applies techniques from polyhedral geometry and mixed-integer programming (MIP) to infer new constraints at the root node (preprocessing).

1. Theoretical Foundation

The method relies on representing task start times $s_i$ and durations $d_i$ as occupancy vectors $\langle s_i | d_i \rangle$ , where the vector is 1 during the interval $[s_i, s_i + d_i)$ and 0 otherwise. A cumulative constraint $\sum r_i \langle s_i | d_i \rangle \le C$ is thus viewed as a linear inequality.

Lemma 7 establishes that any valid inequality for the polyhedron defined by the occupancy vectors corresponds to a valid cumulative constraint for the original scheduling problem.
This allows the problem of inferring constraints to be treated as generating valid cutting planes.

2. The Lifting-Based Workflow

Instead of searching for disjunctive cliques dynamically, the algorithm performs a static preprocessing step involving three stages:

Cover Discovery: The algorithm enumerates "covers" (sets of tasks $C$ where the sum of resource requirements exceeds capacity, i.e., $\sum_{i \in C} r_i > C$ ). It generates "short" covers (cardinality 2 and 3) and "long" covers (grouped by resource consumption values) and selects the most promising candidates based on a capacity bound metric ( $L$ ), which estimates the minimum makespan spanned by the tasks.
Lifting: For each discovered cover, the method applies the lifting procedure (Padberg, 1975). This strengthens the basic cover inequality ( $\sum_{i \in C} x_i \le |C| - 1$ ) by determining the maximum coefficient $\beta$ for variables not originally in the cover, such that the inequality $\sum_{i \in C} x_i + \beta x_j \le |C| - 1$ remains valid. This is achieved by solving auxiliary subproblems (maximizing the left-hand side of the current inequality under specific constraints).
Constraint Injection: The resulting lifted inequalities are converted back into new cumulative constraints and injected into the problem instance before the CP solver begins its search.

The implementation uses Gurobi 12 to solve the lifting subproblems and limits the number of generated constraints ( $N_{out}$ ) and initial covers ( $N_{cover}$ ) to control preprocessing time.

Key Contributions

Algorithmic Framework: A new method for inferring cumulative constraints that generalizes beyond disjunctive reasoning, capturing multi-resource interactions through valid inequalities.
Preprocessing Strategy: A root-node approach that avoids the search-time overhead of dynamic clique detection, thereby eliminating the instability observed in previous UNL-based methods.
Integration of MIP Techniques: The application of lifting and cover inequalities from integer programming to the domain of constraint programming scheduling.
Quality Metric: The introduction of the capacity bound ratio as a heuristic for selecting which covers to lift and which inferred constraints to retain.

Experimental Results

The method was evaluated on standard RCPSP (736 instances) and RCPSP/max (349 instances) benchmarks using state-of-the-art solvers (Pumpkin and CP-SAT).

Performance Gains:
- Optimality: For instances solved to optimality, lifting significantly reduced solving time, sometimes from dozens of minutes to sub-seconds.
- Search Progress: On instances not solved to optimality, the approach substantially improved the dual integral (rate of lower bound improvement), indicating faster convergence toward tight bounds.
- Stability: Unlike UNL, the degradation in performance (increased solving time) was rare. Only 19 pairs of runs showed significant slowdowns, and even the "2x degradation" event occurred only at the 95th percentile.
New Bounds:
- The approach discovered 25 new lower bounds and five new best solutions (upper bounds).
- Eight of the new lower bounds were verified directly by the inferred constraints without requiring any search.
Preprocessing Overhead: The preprocessing phase (cover generation and lifting) typically took only a few seconds. Instances where it took longer (>1 minute) were exclusively large-scale instances (UBO500/UBO1000) with over 500 tasks.
Constraint Types: The most significant gains were observed when the best inferred constraint was disjunctive (unit capacity), though general cumulative constraints also provided moderate improvements.

Significance and Claims

The paper claims that this approach successfully retains the positive traits of the UNL method (substantial gains on instances with hidden structures) while avoiding its primary weakness (instability and severe slowdowns on instances without such structures).

By interpreting cumulative constraints through the lens of polyhedral geometry, the method provides a systematic way to strengthen models with valid inequalities. The authors emphasize that this is a preprocessing technique; it does not replace the solver but enhances the input instance. The results suggest that inferring constraints via lifting is a robust strategy for advancing the state-of-the-art on scheduling benchmarks, particularly for tightening lower bounds and reducing search effort, without the risk of the "order of magnitude" slowdowns associated with previous dynamic probing techniques.