Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Compiling business rules in a geometric constraint over k-dimensional objects and shapes
RISE, Swedish ICT, SICS, Computer Systems Laboratory.ORCID iD: 0000-0003-3079-8095
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. , p. 57
Series
SICS Technical Report, ISSN 1100-3154 ; 2009:02
Keywords [en]
Global Constraint, Geometric Constraint, Rule Language, Sweep, Quantifier-Free Presburger Arithmetic
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-23488OAI: oai:DiVA.org:ri-23488DiVA, id: diva2:1042564
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2023-05-05Bibliographically approved

Open Access in DiVA

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

Authority records

Carlsson, Mats

Search in DiVA

By author/editor
Carlsson, Mats
By organisation
Computer Systems Laboratory
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 83 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

urn-nbn

Altmetric score

urn-nbn
Total: 77 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf