On 3/6/07, Jérémie Vautard <[EMAIL PROTECTED]> 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/ _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
