cs.AIFeb 17, 2026

On inferring cumulative constraints

Authors: Konstantin Sidorov

Organizations: Faculty of Electrical Engineering, Mathematics & Computer Science, Delft University of Technology, Delft, The Netherlands

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.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

    May 14, 2026Sohaib AfifiConstraint Programming

  2. Implementing Cumulative Functions with Generalized Cumulative Constraints

    Aug 3, 2025Pierre Schaus, Charles Thomas, Roger KameugneConstraint PropagationConstraint Satisfaction

  3. Domain-Independent Dynamic Programming with Constraint Propagation

    Mar 17, 2026Imko Marijnissen, J. Christopher Beck, Emir Demirović +1Resource-Constrained Project SchedulingConstraint Propagation