Change search
ReferencesLink to record
Permanent link

Direct link
Compiling business rules in a geometric constraint over k-dimensional objects and shapes
Number of Authors: 3
2009 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 2009, 1. , 57 p.
SICS Technical Report, ISSN 1100-3154 ; 2009:02
Keyword [en]
Global Constraint, Geometric Constraint, Rule Language, Sweep, Quantifier-Free Presburger Arithmetic
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-15803OAI: diva2:1037826
Available from: 2016-10-18 Created: 2016-10-18

Open Access in DiVA

fulltext(317 kB)4 downloads
File information
File name FULLTEXT01.pdfFile size 317 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 4 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link