Generalizing the Edge-Finder Rule for the Cumulative Constraint
Abstract
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. PDF
Cite
Text
Gingras and Quimper. "Generalizing the Edge-Finder Rule for the Cumulative Constraint." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Gingras and Quimper. "Generalizing the Edge-Finder Rule for the Cumulative Constraint." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/gingras2016ijcai-generalizing/)BibTeX
@inproceedings{gingras2016ijcai-generalizing,
title = {{Generalizing the Edge-Finder Rule for the Cumulative Constraint}},
author = {Gingras, Vincent and Quimper, Claude-Guy},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {3103-3109},
url = {https://mlanthology.org/ijcai/2016/gingras2016ijcai-generalizing/}
}