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.constraintsGo Back Up