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-23488OAI: diva2:1042564
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(317 kB)7 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: 7 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

Total: 2 hits
ReferencesLink to record
Permanent link

Direct link