PaLM is an explanation-based constraint programming (e-constraints) language. It is a constraint programming tool that makes heavy use of explanations. Informally, an explanation is a set of constraints (either original constraint or decisions constraints) that justifies a solver action (a value removal, a bound update, a contradiction, etc.). More detailed information about explanations is available on the introduction page.

We suppose here that the user is fluent in choco, the base language of PaLM. Moreover, the user should have successfully installed and configured PaLM.

The examples shown here are available in the doc/tutorial-1.cl file in the PaLM release directory.

Overview

• A first program
• Getting information about propagation: explanations
• Using dynamic capabilities of PaLM
• Solving over-constrained problems

PaLM has been designed to let any choco user switch to PaLM features by changing only a few things in its code. Let's take a simple example:

[classical-choco-program()
 -> let pb := choco/makeProblem("demo constraint program", 5), // a problem
        a  := choco/makeBoundIntVar(pb, "a", 1, 3),            // a few variables
        b  := choco/makeBoundIntVar(pb, "b", 1, 3),
        c  := choco/makeBoundIntVar(pb, "c", 1, 3)
    in (
        printf("Variables: ~S\n", list(a,b,c)),  printf("posting a > b \n"),
        post(pb, a > b), propagate(pb),

        printf("Variables: ~S\n", list(a,b,c)),  printf("posting a > c \n"),
        post(pb, a > c), propagate(pb),

        printf("Variables: ~S\n", list(a,b,c)),  printf("posting b > c \n"),
        post(pb, b > c), propagate(pb),

        printf("Variables: ~S\n", list(a,b,c))
    )]

Loading and interpreting it into a classical choco interpreter (you can even use the PaLM module for that), the following result is obtained (see example 2). As expected, one can see the various propagation results after posting each constraint.

palm> classical-choco-program()
  Variables: (a:[1.3], b:[1.3], c:[1.3])
  posting a > b
  Variables: (a:[2.3], b:[1.2], c:[1.3])
  posting a > c
  Variables: (a:[2.3], b:[1.2], c:[1.2])
  posting b > c
  Variables: (a:3, b:2, c:1)
  nil
palm>

Switching to PaLM is as simple as defining a PalmProbleminstead of a Problem. Example 3 shows the resulting PaLM code from example 1. As expected, the result (see example 4) is exactly the same except for the pretty printing of variables which is specific to PaLM.

[classical-palm-program()
 -> let pb := makePalmProblem("demo constraint program", 5), // a PaLM problem !!!
        a  := makeBoundIntVar(pb, "a", 1, 3),            // a few variables
        b  := makeBoundIntVar(pb, "b", 1, 3),
        c  := makeBoundIntVar(pb, "c", 1, 3)
    in (
        printf("Variables: ~S\n", list(a,b,c)),  printf("posting a > b \n"),
        post(pb, a > b), propagate(pb),

        printf("Variables: ~S\n", list(a,b,c)),  printf("posting a > c \n"),
        post(pb, a > c), propagate(pb),

        printf("Variables: ~S\n", list(a,b,c)),  printf("posting b > c \n"),
        post(pb, b > c), propagate(pb),

        printf("Variables: ~S\n", list(a,b,c))
    )]

palm> classical-palm-program()
  Variables: (a:[1..3], b:[1..3], c:[1..3])
  posting a > b
  Variables: (a:[2..3], b:[1..2], c:[1..3])
  posting a > c
  Variables: (a:[2..3], b:[1..2], c:[1..2])
  posting b > c
  Variables: (a:3, b:2, c:1)
  nil
palm>

Of course, life is not always that simple. You will find on the reference manual page a complete choco/PaLM compatibility list (some constraints need a new API to work with PaLM). You can also have a look to the complete reference online guide to PaLM.

The main advantage of explanation-based constraint programming systems such as PaLM is of course the notion of explanation (implemented as the Explanation class). Accessing explanations in PaLM is quite simple: just use the explain method.

Let us first introduce a small example problem that will be used throughout the demonstration of the explain method.

palm> pb :: makePalmProblem("demo explain", 3)
palm> a :: makeIntVar(pb, "a", 1, 3)
palm> b :: makeIntVar(pb, "b", 1, 3)
palm> c :: makeIntVar(pb, "c", 1, 3)
palm> post(pb, b > c)
palm> post(pb, a > b)
palm> propagate(pb) 
palm> printf("~S ~S ~S\n",a,b,c)
eval> a:3 b:2 c:1

This example shows a classical possible interaction in any constraint solver. As we can see, all variables are instantiated. But, if we want to known exactly why each variable as a value, there is no possible way in classical solvers. However, PaLM provides the explain method.

The explain method can be called in the following ways (see also the reference guide):

• explain(v: PalmIntVar, s: {INF, SUP, DOM})returns an Explanation (the PaLM class for storing explanations) for the current lower bound (INF), upper bound (SUP) or domain (DOM) of variable v.

  In example 5, we can analyse the current domain of the different variables. For example, calling explain(b, DOM) shows that the current domain of variable b is due to the set {b >= c + 1, a >= b + 1}. More precisely, we can see that the current lower bound of b is due to explain(b, INF) = {b >= c + 1} and the current upper bound is due to explain(b, SUP) = {a >= b + 1}.

  explain can even provide more precise information: why does not value 3 appear in the current domain of variable c ? To answer that you can just check explain(c, VAL, 3) = {b >= c + 1}.

• explain(c: AbstractConstraint) returns an Explanation for the current activity of constraint c.

  Usually, the Explanation is reduced to c itself. But, PaLM provides the notion of indirect constraints i.e. constraints that are active only if a given context is active at the same time. In that case, explain(c: AbstractConstraint) returns that context (see Manual note dedicated to indirect constraints).

• explain(pb: PalmProblem) returns an Explanation of the inconsistency of the argument problem. Example 6 shows an inconsistent problem. See in example 7 the information that can be gathered by PaLM.

  Example 6. An inconsistent PaLM problem

  [inconsistent-problem() -> let pb := makePalmProblem("demo explain", 5), a := makeBoundIntVar(pb, "a", 1, 3), b := makeBoundIntVar(pb, "b", 1, 3), c := makeBoundIntVar(pb, "c", 1, 3), d := makeBoundIntVar(pb, "d", 1, 3), e := makeBoundIntVar(pb, "e", 1, 3) in ( printf("\nVariables: ~S\n", list(a,b,c,d,e)), post(pb, a > c), propagate(pb), post(pb, b > d), propagate(pb), post(pb, c > e), propagate(pb), post(pb, d > e), propagate(pb), printf("Variables: ~S\n", list(a,b,c,d,e)), post(pb, e > a), // The offending constraint propagate(pb) )]

  Example 7. An inconsistent PaLM problem (result)

  palm> inconsistent-problem() eval[0]> Variables: (a:[1..3], b:[1..3], c:[1..3], d:[1..3], e:[1..3]) Variables: (a:3, b:3, c:2, d:2, e:1) <integer> // this is symptomatic of a contradiction palm> explain(choco/getActiveProblem()) // choco/getActiveProblem() returns the current problem being solved eval[1]> {a >= c + 1, c >= e + 1, e >= a + 1} palm>

  Notice that the provided explanation is really focused on the cause of the problem and does not take into account constraints on variables b and d.

Constraints in explanations are expressed using the internal choco/PaLM representation and not the user definition. This can lead to pretty unreadable explanations. PaLM can provide user-friendly explanations [Jussien and Ouis, 2001] (see Manual note dedicated to them for more information).

PaLM is also a dynamic constraint solver. Constraints can be added (using the post method) either before, during or after search is performed. In the latter case, the search can be re-started from the reached point.

On another interesting feature of PaLM is that constraints can alse be incrementally removed from the constraint system. We use the remove method (you can have a look to the online reference guide).

remove(pb: PalmProblem, ct: AbstractConstraint) removes all the past effects of constraint ct. Some of these past effects can be proved another way and therefore a call to propagate is necessary to get back to a consistent state.

palm> pb :: makePalmProblem("demo remove", 3)
palm> a :: makeBoundIntVar(pb, "a", 1, 3)
palm> b :: makeBoundIntVar(pb, "b", 1, 3)
palm> c :: makeBoundIntVar(pb, "c", 1, 3)
palm> ct :: (b > c)  // defining ct as a constraint
palm> post(pb, ct)
palm> post(pb, a > b)
palm> propagate(pb) 
palm> printf("~S ~S ~S\n",a,b,c)
eval> a:3 b:2 c:1
palm> remove(pb, ct)
palm> printf("~S ~S ~S\n",a,b,c)
eval> a:[1..3] b:[1..2] c:[1..3]
palm> propagate(pb)
palm> printf("~S ~S ~S\n",a,b,c)
eval> a:[2..3] b:[1..2] c:[1..3]

The remove methods leads to the same resulting domains that if the constraints was never added (this is not necessary the case for the resulting explanations).

palm> pb :: makePalmProblem("demo remove", 3)
palm> a :: makeBoundIntVar(pb, "a", 1, 3)
palm> b :: makeBoundIntVar(pb, "b", 1, 3)
palm> c :: makeBoundIntVar(pb, "c", 1, 3)
palm> post(pb, a > b)
palm> propagate(pb) 
palm> printf("~S ~S ~S\n",a,b,c)
eval> a:[2..3] b:[1..2] c:[1..3]

Being able to identify explanations for contradiction and having access to incremental tools for removing constraints leads to the automatic resolution of over-constrained problems. PaLM provides a few tools for that:

• the post method can be used with a third parameter giving a user preference for the posted constraint (the lower the value, the weaker the importance of the constraint - see the online reference guide) along the with the ability to specify a maximum relaxation level when declaring a problem with makePalmProblem.

• the exception handling mechanisms of claire can be used to catch and handle contradiction during propagation or search. PaLM provides the PalmContradiction exception class denoting contradictions occuring during propagation.

• the repair(pb: PalmProblem) method takes an over-constrained problem, computes an explanation for the contradiction, selects constraints to relax (taking into account the user preferences - as in possibilistic CSP [Bistarelli et al., 1996]), and removes them. The repair code is recursively called until a feasible situation is achieved. (repair is described in the online reference guide)

[over-constrained-problem()
 -> let pb := makePalmProblem("demo over-constrained system", 3, 5), 
                                    // maximum relaxation level: 5
        a  := makeBoundIntVar(pb, "a", 1, 3),
        b  := makeBoundIntVar(pb, "b", 1, 3),
        c  := makeBoundIntVar(pb, "c", 1, 3),
	ct1 := (a > b),
	ct2 := (b > c),
	ct3 := (c > a)
    in (
        try ( // using claire exception handling mechanisms
            printf("Variables: ~S\n", list(a,b,c)),

            printf("posting ~S \n", ct1),
            post(pb, ct1, 2), propagate(pb), // ct1 is not that important (weight 2)
            printf("Variables: ~S\n", list(a,b,c)),

            printf("posting ~S \n", ct2),
            post(pb, ct2, 5), propagate(pb), // ct2 is really important (weight 5)
            printf("Variables: ~S\n", list(a,b,c)),

            printf("posting ~S \n", ct3),
            post(pb, ct3, 3), propagate(pb), // ct1 is quite important (weight 3)
            printf("Variables: ~S\n", list(a,b,c))
        )
        catch PalmContradiction ( // if a contradiction occurs
            repair(pb),
            printf("Variables: ~S\n", list(a,b,c))
        )
    )]

palm> over-constrained-problem()
eval[0]> 
  Variables: (a:[1..3], b:[1..3], c:[1..3])
  posting a >= b + 1
  Variables: (a:[2..3], b:[1..2], c:[1..3])
  posting b >= c + 1
  Variables: (a:3, b:2, c:1)
  posting c >= a + 1
  // here a contradiction occurred : repair is called
  PALM: Removing constraint a >= b + 1 (w:2) 
  // the least important relevant constraints has been chosen for relaxation
  Variables: (a:1, b:3, c:2)
  nil
palm>

The tutorial note dedicated to search can help you in designing your own over-constrained problem solver.