New filtering for the cumulative constraint in the context of non-overlapping rectangles

Nicolas Beldiceanu (), Mats Carlsson (), Sophie Demassey () and Emmanuel Poder ()

Annals of Operations Research, 2011, vol. 184, issue 1, 27-50

Abstract: This article describes new filtering methods for the cumulative constraint. The first method introduces the so called longest closed hole and longest open hole problems. For these two problems it first provides bounds and exact methods and then shows how to use them 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 65 perfect square instances of order 22–25 and sizes ranging from 192×192 to 661×661. Copyright Springer Science+Business Media, LLC 2011

Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0731-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:184:y:2011:i:1:p:27-50:10.1007/s10479-010-0731-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0731-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().