---
title: "Generalizing the Edge-Finder Rule for the Cumulative Constraint"
authors:
  - "Vincent Gingras"
  - "Claude-Guy Quimper"
doi: ""
url: "https://ijcai.org/proceedings/2016/440"
pdf: "https://ijcai.org/proceedings/2016/0440.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3103-3108"
track: ""
keywords:
---

# Generalizing the Edge-Finder Rule for the Cumulative Constraint

Vincent Gingras, Claude-Guy Quimper

*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.