SODA

Six ways of integrating symmetries within non-overlapping constraints

Ågren, Magnus and Beldiceanu, Nicolas and Carlsson, Mats and Sbihi, Mohamed and Truchet, Charlotte and Zampelli, Stéphane (2009) Six ways of integrating symmetries within non-overlapping constraints. [SICS Report]

[img]
Preview
PDF
398Kb
[img]
Preview
Postscript
825Kb

Abstract

This report introduces six ways for handling a chain of lexicographic ordering constraint between the origins of identical orthotopes (e.g., rectangles, boxes, hyper-rectangles) subject to the fact that they should not pairwise overlap. While the first two ways deal with the integration of a chain of lexicographic ordering constraint within a generic geometric constraint kernel, the four latter ways deal with the conjunction of a chain of lexicographic ordering constraint and a non-overlapping or a cumulative constraint. Experiments on academic two and three dimensional placement problems as well as on industrial problems show the benefit of such a strong integration of symmetry breaking constraints and non-overlapping ones.

Item Type:SICS Report
Uncontrolled Keywords:Global Constraints, Placement Problems, Symmetry Breaking, Non-Overlapping, Lexicographic ordering
ID Code:3530
Deposited By:Vicki Carleson
Deposited On:06 May 2009
Last Modified:18 Nov 2009 16:23

Repository Staff Only: item control page