Browse Prior Art Database

A CSP Quadratic Propagator

IP.com Disclosure Number: IPCOM000188069D
Original Publication Date: 2009-Sep-22
Included in the Prior Art Database: 2009-Sep-22
Document File: 4 page(s) / 41K

Publishing Venue

IBM

Abstract

This article describes an automatic CSP propagator builder for quadratic constraints.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 30% of the total text.

Page 1 of 4

Described here is an automatic CSP propagator builder for quadratic constraints.

quadratic constraint is a constraint that,

the constraint

should be invoked on every pair of these objects. Users can specify on which pair the constraint should not be relevant. This article describes how to create automatically an efficient propagator.

A constraint in a CSP can be expressed in one of several manners:

• Explicit enumeration of the tuples that satisfy the constraint. The width of the tuple is the arity of the constraint. The following example exemplifies a constraint

with arity

      2, that enables three combinations of values for the two variables { {2, 1}, {3, 1}, {3, 2}}.

A mathematical expression composed of variables,

                                     operators, constants, and connectives as in first-order logic. This provides a way to construct complex constraints by forming expressions over atomic (elementary) constraints and composition operands such as 'and' (conjunction), 'or' (disjunction), and 'imply' (->).

An example of such a constraint would be "a=b

                              -> c>3" where a, b, and c are the variables and a=b, c>3 are two atoms connected with a conjunction operator. This representation is extremely important when the domain of the variables is large. The propagator of this invention gets the constraint written in this way.

The propagator gets the vector of variables (

V),

                                   their initial domains and an expression. It creates a propagator that is called by the MAC solver. Since the arity of the constraint could be large, it is extremely important to implement this propagator as an incremental propagator.

An incremental propagator has an

internal-state which is retained between consecutive runs of the propagator. Each propagator call uses the updated variable domains and its internal state. This is in contrast to a non-incremental propagator,

which reduces the variable domains only

according to their input domains. The propagator's state reduces the run-time by preventing recalculation of the same data in consecutive runs.

    To support MAC backtrack algorithm, the incremental propagator has to be an undoable object. This undoable object maintains history of states. Once the MAC algorithm backtracks, it also restores the previous saved propagator's state.

    Limitations: This propagator supports expressions from the type "prefix -> suffix" such that the prefix and the suffix can be any expression composed of: 1) the connectives 'and', 'or'; 2) predicate such as '=', '!=', '<', '

', '>=' that operate on similar variables belongs to different entries of the vector (for example the prefix ai >

a

A variable does not appear

more than once in the expression.

The propagator operates as follows:


When the MAC solver calls the propagator, it provides the propagator a list of variables, their current domains, and a list of modified variables (i.e., the variables that their domain has been changed since the last call to the propagator). The pro...