The SoftCumulative Constraint with Quadratic Penalty

No. 4: AAAI-22 Technical Tracks 4

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Constraint Satisfaction and Optimization

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.

10.1609/aaai.v36i4.20296