Re: Question: constraint terminology

From: (Michel Leconte)
Organization: ILOG S.A., France
Date: Mon, 3 Jul 95 12:44:52 GMT

|> Question: Could somebody explain the following terms:
|>  - Global constraints

The term "global constraint" is related with the level of consistency
achieved by the propagation engine. A classical example is the "alldiff"
setting that, in any solution, all the values of the xi must be
pairwise distinct.

The traditionnal (local) handling of this constraint ensures that, each
time a variable is instantiated to a value, this value does not appear
in the domains of the other variables.
More formally, the following holds:
  forall xi, forall xj != xi, forall u belonging to the domain of xi,
  there exists a value v in the domain of xj such that u != v.
The global handling of this constraint should maintain the following
  forall xi, forall u in the domain of xi, there exist values from
  domains of {x1,...,xj,...xn | xj != xi} such that u and these values
  are pairwise distinct.
In other words, the global consistency of a constraint is: any value in
the domain of a variable belongs to a solution.
The global consistency of the alldiff constraint has been shown by J-C
Regin in: "A filtering algorithm for constraint of difference in CSPs.
Jean-Charles Regin, AAAI 94, Seattle, Washington".

The paper "Beyond the Glass Box: Constraints as Objects. Jean-Francois
Puget, Michel Leconte, ILPS'95", discusses what kind of constructs are
needed to implement global constraints. Experimental results are also
given, demonstrating significant speedups vs local propagation

|>  - Specific and structural constraints 
|>  (in: CHIC lessons on CLP methodology, ECRC-report)

The CHIC project (Constraint Handling in Industry and Commerce, Esprit
project number 5291) was finished at the end of 1994. One of its result
concerns the CLP methodology, with a big emphasis on the qualification
phase: given a (instance of a) problem, (try to) predict if:
  - it is feasible,
  - it needs the coding of new constraints (e.g. the cooperation
    of OR [operations research] algorithms and propagations).

One of the first phases of the methodology is to differentiate specific
and structural constraints:

Structural constraints deals with global properties of the problem and
act on variables playing similar roles (the sub-problem is homogeneous).
For example, you can easily encode a flow transportation problem in a
CLP using elementary arithmetic constraint. Netherless, there is a more
global structure (a graph) that represents the problem together with a
_structural_ constraint (flow conservation) to express it.

At the opposite, specific constraints depends on the instance of the 

|> Also I would appreciate pointers to papers that explicitly deal with 
|> problem solving systems for a combination of continuous and symbolic 
|> constraints.

You could have a look at "H. Beringer and B. De Backer. Combinatorial
Problem Solving in Constraint Logic Programming with cooperating
Solvers. In C. Beierle and L. Plumers Editors, Logic Programming:
Formal methods and Practical Applications, Elsevier Science B.V. 1995"

 Michel Leconte                 net :
 ILOG S.A.                      tel : +33 1 49 08 35 00
 9, rue de Verdun - BP 85       fax : +33 1 49 08 35 10
 F-94253 Gentilly Cedex         url :
 FRANCE                         url :


Newsgroups: comp.constraints
Go Back Up

Go To Previous

Go To Next