A New Characterization of Relevant Intervals for Energetic Reasoning

Alban Derrien (1, 2) , Thierry Petit (2, 1)

1 TASC - Theory, Algorithms and Systems for Constraints
2 Mines Nantes - Mines Nantes

Energetic Reasoning (ER) is a powerful filtering algorithm for the Cumulative constraint. Unfortunately, ER is generally too costly to be used in practice. One reason of its bad behavior is that many intervals are considered as relevant, although most of them should be ignored. In the literature, heuristic approaches have been developed in order to reduce the number of intervals to consider, leading to a loss of filtering. In this paper, we provide a sharp characterization that allows to reduce the number of intervals by a factor seven without loss of filtering.

Domaines: Recherche opérationnelle [math.OC]; Mathématique discrète [cs.DM]

Alban Derrien, Thierry Petit. A New Characterization of Relevant Intervals for Energetic Reasoning. Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. pp.289 - 297, ⟨10.1007/978-3-319-10428-7_22⟩. ⟨hal-01084436⟩