![[2602.15635] On inferring cumulative constraints](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.15635] On inferring cumulative constraints
Summary
This paper presents a method for inferring cumulative constraints in scheduling problems, improving search performance and generating new lower bounds and solutions.
Why It Matters
Cumulative constraints are critical in scheduling tasks efficiently. This research addresses limitations in current methods by introducing a preprocessing technique that enhances performance and accuracy in scheduling, which is vital for various applications in artificial intelligence and operations research.
Key Takeaways
- Introduces a preprocessing method for cumulative constraints in scheduling.
- Improves search performance and tightens objective bounds in scheduling problems.
- Discovers 25 new lower bounds and five new best solutions through inferred constraints.
- Enhances understanding of multi-resource interactions in scheduling.
- Demonstrates minimal degradation on unfavorable instances while improving favorable ones.
Computer Science > Artificial Intelligence arXiv:2602.15635 (cs) [Submitted on 17 Feb 2026] Title:On inferring cumulative constraints Authors:Konstantin Sidorov View a PDF of the paper titled On inferring cumulative constraints, by Konstantin Sidorov View PDF HTML (experimental) Abstract:Cumulative constraints are central in scheduling with constraint programming, yet propagation is typically performed per constraint, missing multi-resource interactions and causing severe slowdowns on some benchmarks. I present a preprocessing method for inferring additional cumulative constraints that capture such interactions without search-time probing. This approach interprets cumulative constraints as linear inequalities over occupancy vectors and generates valid inequalities by (i) discovering covers, the sets of tasks that cannot run in parallel, (ii) strengthening the cover inequalities for the discovered sets with lifting, and (iii) injecting the resulting constraints back into the scheduling problem instance. Experiments on standard RCPSP and RCPSP/max test suites show that these inferred constraints improve search performance and tighten objective bounds on favorable instances, while incurring little degradation on unfavorable ones. Additionally, these experiments discover 25 new lower bounds and five new best solutions; eight of the lower bounds are obtained directly from the inferred constraints. Comments: Subjects: Artificial Intelligence (cs.AI) ACM classes: I.2.8 Cite as: a...