Generalizing the edge-finder rule for the cumulative constraint
Vincent Gingras, Claude-Guy Quimper · International Joint Conference on Artificial Intelligence · 2016
We present two novel filtering algorithms for the CUMULATIVE constraint based on a new energetic relaxation. We introduce a generalization of the Overload Check and Edge-Finder rules based on a function computing the earliest completion time for a set of tasks. Depending on the relaxation used to compute this function, one obtains different levels of filtering. We present two algorithms that enforce these rules. The algorithms utilize a novel data structure that we call Profile and that encodes the resource utilization over time. Experiments show that these algorithms are competitive with the state-of-the-art algorithms, by doing a greater filtering and having a faster runtime.