[gecode-users] Cumulative constraint propagation

[Mikael Zayenz Lagerkvist]

On 3/6/07, Jérémie Vautard <jeremie.vautard at laposte.net> wrote:
> I asked a few month ago (October 4th) what propagation the cumulative
> constraint did (*Mikael Zayenz Lagerkvist answered me that it did not
> very much). Does it do more now ?

It does not do anything more. The constraint implemented, called
cumulatives, is a very general constraint. To read more about the
specific prunings done, see "A New Multi-resource cumulatives
Constraint with Negative Heights" by Beldiceanu and Carlsson
(http://www.springerlink.com/content/yblp5037rxkqn2u0/).


> Could someone indicate me a paper describing the state of the art in
> this domain ?

Bounds-consistent pruning for cumulative is NP-complete, so we must
look for weaker algorithms. Some common algorithms used are edge
finding, not-first/not-last, and energetic reasoning.

The most complete reference for scheduling constraints is probably
"Constraint-Based Scheduling" by Baptiste, Le Pape, and Nuijten
(http://www.springer.com/west/home?SGWID=4-102-22-33293925-0).

For some updates on edge-finding for cumulative constraints, see "Edge
Finding for Cumulative Scheduling" Mercier and Van Hentenryck
(http://www.cs.brown.edu/people/pvh/ef2.pdf).


Hope this helps,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/