AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
The Multi-Inter-Distance Constraint
Pierre Ouellet, Claude-Guy Quimper

Last modified: 2011-06-28


We introduce the MULTI-INTER-DISTANCE constraint that ensures no more than m variables are assigned to values lying in a window of p consecutive values. This constraint is useful for modeling scheduling problems where tasks of processing time p compete for m identical resources. We present a propagator that achieves bounds consistency in cubic time. Experiments show that this new constraint offers a much stronger filtering than an edge-finder and that it allows to solve larger instances of the runway scheduling problem.

Full Text: PDF