SODA

New Filtering for the Cumulative Constraint in the Context of Non-Overlapping Rectangles

Beldiceanu, Nicolas and Carlsson, Mats and Demassey, Sophie and Poder, Emmanuel (2011) New Filtering for the Cumulative Constraint in the Context of Non-Overlapping Rectangles. Annals of Operations Research, 1 (184). pp. 27-50. ISSN 0254-5330

Full text not available from this repository.

Official URL: http://www.springer.com

Abstract

This article 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 65 perfect square instances of order 22-25 and sizes ranging from 192x192 to 661x661.

Item Type:Article
ID Code:4159
Deposited By:Mats Carlsson
Deposited On:03 May 2011 15:33
Last Modified:03 May 2011 15:33

Repository Staff Only: item control page