The SoftCumulative Constraint with Quadratic Penalty
Keywords:Constraint Satisfaction And Optimization (CSO)
AbstractThe 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.
How to Cite
Ouellet, Y., & Quimper, C.-G. (2022). The SoftCumulative Constraint with Quadratic Penalty. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3813-3820. https://doi.org/10.1609/aaai.v36i4.20296
AAAI Technical Track on Constraint Satisfaction and Optimization