Compiling business rules in a geometric constraint over k-dimensional objects and shapes
Number of Authors: 3
2009 (English)Report (Other academic)
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
Global Constraint, Geometric Constraint, Rule Language, Sweep, Quantifier-Free Presburger Arithmetic
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-15803OAI: oai:DiVA.org:ri-15803DiVA: diva2:1037826