×

zbMATH — the first resource for mathematics

New filtering for the cumulative constraint in the context of non-overlapping rectangles. (English) Zbl 1142.68505
Perron, Laurent (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 5th international conference, CPAIOR 2008 Paris, France, May 20–23, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68154-0/pbk). Lecture Notes in Computer Science 5015, 21-35 (2008).
Summary: This paper describes new filtering methods for the cumulative constraint. The first method introduces bounds for the so called longest cumulative hole problem and shows how to use these bounds in the context of the non-overlapping constraint. The second method introduces balancing knapsack constraints which relate the total height of the tasks that end at a specific time-point with the total height of the tasks that start at the same time-point. Experiments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for finding all solutions as well as for finding the first solution. For example, we found without backtracking all solutions to 66 perfect square instances of order 23–25 and sizes ranging from \(332 \times 332\) to \(661 \times 661\).
For the entire collection see [Zbl 1136.68010].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDF BibTeX Cite
Full Text: DOI