ML Anthology

The Multi-Inter-Distance Constraint

Pierre Ouellet, Claude-Guy Quimper
IJCAI 2011 pp. 629-634
doi:10.5591/978-1-57735-516-8/IJCAI11-112 /ijcai/2011/ouellet2011ijcai-multi/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Ouellet and Quimper. "The Multi-Inter-Distance Constraint." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-112

Markdown

[Ouellet and Quimper. "The Multi-Inter-Distance Constraint." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/ouellet2011ijcai-multi/) doi:10.5591/978-1-57735-516-8/IJCAI11-112

BibTeX

@inproceedings{ouellet2011ijcai-multi,
  title     = {{The Multi-Inter-Distance Constraint}},
  author    = {Ouellet, Pierre and Quimper, Claude-Guy},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {629-634},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-112},
  url       = {https://mlanthology.org/ijcai/2011/ouellet2011ijcai-multi/}
}