The SoftCumulative Constraint with Quadratic Penalty

Yanick Ouellet, Claude-Guy Quimper

[AAAI-22] Main Track

Keywords
Poster Session 4 @ Blue 4, Poster Session 8 @ Blue 4, Oral Session 8 @ Blue 4, Poster Session 4, Poster Session 8, Oral Session 8

Download Paper
Enter the Virtual Venue
Abstract: The Cumulative constraint greatly contributes to the success of constraint programming at solving scheduling problems. The SoftCumulative, a version of the Cumulative where overloading the resource incurs a penalty is, however, less studied. We introduce a checker and a filtering algorithm for the SoftCumulative, which are inspired by the powerful energetic reasoning rule for the Cumulative. Both algorithms can be used with classic linear penalty function, but also with a quadratic penalty function, where the penalty of overloading the resource increases quadratically with the amount of the overload. We show that these algorithms are more general than existing algorithms and vastly outperform a decomposition of the SoftCumulative in practice.

Introduction Video

Sessions where this paper appears

  • Poster Session 4

    Blue 4

  • Poster Session 8

    Blue 4

  • Oral Session 8

    Blue 4