SODA

A geometric constraint over k-dimensional objects and shapes subject to business rules

Carlsson, Mats and Beldiceanu, Nicolas and Martin, Julien (2008) A geometric constraint over k-dimensional objects and shapes subject to business rules. In: CP 2008: 14th International Conference on Principles and Practice of Constraint Programming, 14-18 Sept 2008, Sidney, Australia.

[img]
Preview
PDF
259Kb

Official URL: DOI:10.1007/978-3-540-85958-1_15

Abstract

This report presents a global constraint that enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. The business rules allow to express a great variety of packing and placement constraints, while admitting efficient and effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer and tested on a set of real packing problems under these rules, as well as on a packing-unpacking problem.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Published in Lecture Notes in Computer Science; Volume 5202
ID Code:3455
Deposited By:Vicki Carleson
Deposited On:03 Nov 2008
Last Modified:18 Nov 2009 16:22

Repository Staff Only: item control page