SODA

Compiling business rules in a geometric constraint over k-dimensional objects and shapes

Beldiceanu, Nicolas and Carlsson, Mats and Martin, Julien (2009) Compiling business rules in a geometric constraint over k-dimensional objects and shapes. [SICS Report]

[img]
Preview
PDF
317Kb
[img]Postscript
278Kb

Abstract

It is well known that real-life applications rarely admit a constraint model expressed purely in terms of a few global constraints. Usually, the global constraints capture a relaxed form of the problem, but needs additional side-constraints to capture the full problem. Handling such side-constraints inside the global constraints, as opposed to in conjunction with it, improves propagation. Historically, this has been done by extending the global constraints with a host of specific options, each connected to a specific filtering method. Being able to express and filter side-constraints in a more uniform and systematic way would seem a more elegant and manageable solution. This report presents such a mechanism for the global non-overlapping constraint "geost", which handles the location in space of k-dimensional objects. Side-constraints are expressed as rules written in a language based on arithmetic and first-order logic, which should hold among the objects. We explain in detail the way the rules are compiled into a form that is accessed by the constraint's sweep-based filtering algorithm. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are transformed to generators of k-dimensional forbidden sets. Thirdly, the generators are transformed to procedures answering queries about candidate coordinate points for a given object. Such queries are at the heart of the filtering algorithm. The business rules allow to express a great variety of packing and placement constraints, while admitting 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 was evaluated on several benchmarks.

Item Type:SICS Report
Uncontrolled Keywords:Global Constraint, Geometric Constraint, Rule Language, Sweep, Quantifier-Free Presburger Arithmetic
ID Code:3575
Deposited By:Vicki Carleson
Deposited On:02 Nov 2009
Last Modified:18 Nov 2009 16:24

Repository Staff Only: item control page