Re: Question: constraint terminology

From: leconte@ilog.fr (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"
constraint:
  alldiff(x1,...xi,...xn)
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
property:
  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
implementations.

|>  - 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 
application.

|> 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 : leconte@ilog.fr
 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 : http://www.ilog.com
 FRANCE                         url : http://www.ilog.fr
----------------------------------------------------------

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Newsgroups: comp.constraints