Generalizing the Edge-Finder Rule for the Cumulative Constraint
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3103-3108.
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.
@inproceedings{ijcai2016p440,
title = {Generalizing the Edge-Finder Rule for the Cumulative Constraint},
author = {Gingras, Vincent and Quimper, Claude-Guy},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {3103--3108},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/440},
}
TY - CPAPER TI - Generalizing the Edge-Finder Rule for the Cumulative Constraint AU - Gingras, Vincent AU - Quimper, Claude-Guy T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 3103 EP - 3108 UR - https://ijcai.org/proceedings/2016/440 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
