A $O(n^2 log(n))$ propagation for the Energy Reasoning

Session : PJC-2 / Prix Jeune Chercheur
Mercredi 10 février 15:00 - 16:00 Salle : Amphi-CI
Nicolas Bonifas

The most fundamental global constraint used in constraint-based scheduling is the cumulative constraint, so its efficient propagation is of critical practical importance. Several propagations have been studied, notably timetabling and edge-finding. But one of the strongest propagation available, the energy reasoning of Erschler and Lopez, is seldom used because of its $O(n^3)$ complexity. We introduce an algorithm to compute this propagation in time $O(n^2 log(n))$ which significantly improves on the algorithm which has been known for 25 years. This new approach relies on novel properties of the cumulative constraint and on a geometric study.

Mots clés : constraint-based scheduling, constraint programming, scheduling, global constraints, energy reasoning, energetic reasoning, discrete cumulative resource, cumulative resource, cumulative constraint, propagation, line sweep algorithm, envelope of line segments.