Name
Title | ||
|---|---|---|
New Filtering for the cumulative Constraint in the Context of Non-Overlapping Rectangles |
Abstract | ||
|---|---|---|
This paper describes new ltering methods for the cumulative con- straint. The rst method introduces bounds for the so called longest cumula- tive 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 specic time- point with the total height of the tasks that start at the same time-point. Exper- iments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for nding all solutions as well as for nding the rst solution. For example, we found without backtracking all solutions to 66 perfect square instances of order 23-25 and sizes ranging from 332 332 to 661 661. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-540-68155-7_5 | Annals OR |
Keywords | Field | DocType |
specific timepoint,non-overlapping rectangle,knapsack constraint,cumulative constraint,non-overlapping constraint,tight rectangle packing problem,longest cumulative hole problem,total height,perfect square instance,cumulant | Discrete mathematics,Square number,Mathematical optimization,Packing problems,Algorithm,Filter (signal processing),Ranging,Knapsack problem,Backtracking,Mathematics,Rectangle packing | Journal |
Volume | Issue | ISSN |
184 | 1 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-68154-X | 15 | 0.83 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Beldiceanu | 1 | 547 | 51.14 |
| Mats Carlsson | 2 | 975 | 79.24 |
| Emmanuel Poder | 3 | 31 | 4.38 |