PaLM stands for Propagation and Learning with Move because it can be used to design powerful algorithms that efficiently combine propagation techniques, repairs (the move in PaLM) and explanation-based learning for efficiently guiding the search.

This note is a complete guide for designing search algorithms within PaLM.

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

Overview

• A general search algorithm
• Making choices: the EXTEND component
• Recovering from contradictions: the REPAIR component
• Maintaining information: the STATE component
• Avoiding past mistakes: adding a LEARNING component
• Putting bits and pieces together
• An example: a tabu path-repair instance
• Branch and Bound in PaLM

Adding explanations within constraint programming deeply changes the way of considering search. [Jussien, 2001] gives a good panorama of the origin of those modifications.

In PaLM, every search-related information is stored in a PalmSolver attached to a given PalmProblem. The run method is called to actually perform the search.

Algorithm 1 gives the general search algorithm that is used in PaLM. The idea is quite simple. First, perform search as usual: extend your current partial solution (i.e. add decisions as long as no solution is found). Second, if a contradiction occurs do not backtrack but repair the solution (ŕ la Dynamic Backtracking [Ginsberg, 1993]).

[run(algo: PalmSolver)
 -> let pb := algo.problem    // fetch the attached problem
    in (
        try (
              propagate(pb),  // initial propagation
              while not(algo.finished) ( // finished is true if 
                                                  - a solution has been found
                                                  - no solution can be found
                 try (
                    extend(algo),      // make some new decisions
                    propagate(pb)
                 )
                 catch PalmContradiction (
                    repair(algo) // handling contradiction
                 )
              ),
              algo.feasible := true      // A solution was found
         )
         catch contradiction ( // There is no possible solution
              algo.finished := true,
              algo.feasible := false
         )
    )]

This search algorithm is based on the generic notion of decision constraint. Informally, decision constraints are constraints that help pruning the search space by committing into a choice during exploration. Here are some possible decision constraints:

• For classical CSP, decision constraints are value assignment constraints (the AssignmentConstraint class is provided in PaLM).
• For numerical CSP, decision constraints can be splitting constraints (such as in [Jussien and Lhomme, 1998]).
• For scheduling problems, decision constraints can be precedence constraints (such as in [Jussien and Lhomme, 2002])

Search in PaLM constantly adds and remove decision constraints until a feasible set of decision constraints has sufficiently reduced the search space to only leave one solution or that the problem has been proven to be over-constrained.

Decision constraint addition is fully controlled by the extend component of the current PalmSolver. Extending a partial solution means determining a set of possible choices taking into account the current situation and committing to a choice.

As in choco, decisions to be made are provided by a branching object. In order to easily control the extension part of the search, an ordered list of PalmBranching can be attached to the current problem (see the attachPalmBranchings method).

Extension in PaLM consists in exploring the search space that is provided by the attached PalmBranchings. Algorithm 2 shows how it works.

[extend(algo: PalmSolver): void
 => explore(algo.extending, algo.extending.branching)]    
     // branchings are chained ... we start from the first one

[explore(ext: PalmExtend, b: PalmBranching) : void
 -> when v := selectBranchingItem(b) in (	
		propagateAllDecisionConstraints(ext.manager.problem, selectDecisions(b, v))
	) 
	else ( 
		when nB := get(nextBranching, b) in explore(ext, nB) 
                     // check the following branching
		else b.extender.manager.finished := true 
                     // when no branching is left, search is terminated
	)]

Several different methods are used in Algorithm 2:

• selectBranchingItem returns the object about which decisions will be made (a variable in the default behavior, a couple of taks in scheduling problems, ...). If no more object is left to decide upon, this method returns unknown.
  This method needs to be specialized when defining a new PalmBranching.

• selectDecisions returns a list of constraints that represent the decision to make with the PalmBranching parameter. For example, if the branching object is PalmIntVar the decision to be made could be assigning its lower bound to the variable.
  This method needs to be specialized when defining a new PalmBranching.

• propagateAllDecisionConstraints adds the set of decision constraints returned by the PalmBranching and then propagates the new problem.

The following PalmBranchings are provided in standard PaLM:

• PalmAssignVar returns a PalmIntVar (with no specified heuristic) as branching object and returns an AssignmentConstraint that assigns its lower bound to the variable.

• PalmAssignMinDomVar works as a PalmAssignVar except that the returned PalmIntVar is the one with the minimum domain size.

• PalmAssignMinDomDegVar works as a PalmAssignVar except that the returned PalmIntVar is the one with the minimum domain size vs. current degree ratio.

When a contradiction occurs there is no backtrack in PaLM. Instead, PaLM provides a repair mechanims is provided which modifies (by removing decision constraints) the current constraint system in order to get into a consistent constraint network.

Algorithm 3 describes how repair works in PaLM.
Notice that this code is not the real PaLM code. It has been edited for sake of simplicity.

[repair(algo: PalmSolver) : void
 -> let pb := algo.problem,
	pe := pb.propagationEngine,
	repairer := algo.repairing
    in (
	if (pe.contradictory) ( // Check that we are handling a contradiction
	   let e  := Explanation() // the contradiction explanation
	       fv := pe.contradictionCause // the cause of the last contradiction
	   in (
		self_explain(fv, DOM, e), // compute e
		pe.contradictory := false, // the contradiction is being handled
		if (empty?(e)) ( // the problem is structurally over-constrained
			raiseSystemContradiction(pe) // raise a choco contradiction
		)
		else (	
		     when ct := selectDecisionToUndo(repairer, e)
		     in (
		        if (weight(ct) = 0) ( // a decision constraint
			   try (
			       remove(pb,ct),  // undo past effects of ct
   			       propagate(pb) // repropagate 
			   )
			   catch PalmContradiction (
			       repair(algo) // recursive call if necessary
			   ),
			   e :delete ct,
			   when negct := negate(ct)
			   in (
		               if valid?(e) ( // the context is still valid
				  try (
				       post(pb, negct, e), // indirect negation
                                       propagate(pb)
				  )
				  catch PalmContradiction (
				       repair(algo) // another recursive call
				  )
			       )
  			   )
                        ) else raiseSystemContradiction(pe) // inadequate constraint
                     ) else raiseSystemContradiction(pe) // no available constraint
		 )
	   )
	)
      )]

Repairing an inconsistent partial solution with explanations is done in the following way:

• First, compute an Explanation of the current contradiction. It is a set of constraints whose conjunction induces the contradiction.

• Second, select in that explanation a decision constraint to remove. This is done through the selectDecisionToUndo method.

• Third, undo the past effects of the selected constraints using the remove method.

• Fourth, determine the negation of the undone constraint. Notice that we do not use the opposite choco method because we do not want to post a constraint when it is already subsumed by the constraint system.

• Finally, post the negation constraint with an attached context. It is called an indirect constraint in PaLM.

PaLM provides several comparison methods that can be used in the selectDecisionToUndo method:

• standard_better_constraint which can be used to return the most recent least important constraint in the Explanation parameter.

• standard_better_ordered_constraint which can be used to return the most recent constraints that has the least searchInfo value in its PalmInfoConstraint.

In PaLM, recording information during search is offered through the PalmState class. This class is used to represent the current search state.

The main information that is maintained through this class is the current set of active decision constraints i.e. the current path that is being expanded in the search tree.

A set of different methods is used to automatically maintain that information:

• addDecision which is called when a new decision constraint is added to the constraint system.
• removeDecision which is called when a decision constraint is removed from the constraint system.
• reverseDecision which can be called when a decision constraint is not really added to the constraint system because it is already subsumed by the problem. In that case, the constraint is not really removed but the addDecision needs to be undone.

PaLM search is based on learning from the past through the recording of explanations. Unfortunately, for efficiency reasons, all computed explanations cannot be kept throughout search. However, it is often useful to record past information for future use. This is why PaLM provides the PalmLearn class.

There are two ways to learn from the past:

• When a contradiction occurs some information can be recorded. The learnFromContradiction method is automatically called when a contradiction is repaired in PaLM.

• When a decision constraint is removed from the current constraint system. The learnFromRemoval method is automatically called in such a situation.

Learnt information is used through the following methods:

• checkAcceptable(l, cts) checks if the set of decision constraints cts is acceptable considering the information kept by the PalmLearncomponent l.

• checkAcceptableRelaxation(l, ct) checks if the removal of constraint ct will not lead to an unacceptable situation considering the recorded information about the past of the search stored in l.

• sortConstraintsToUndo is used to sort constraints in a contradiction explanation in order to possibly iterate on the that set of constraints (especially if checkAcceptableRelaxation returns false for the first ones).

In order to make an efficient use of the PalmLearn component, PaLM provides two new classes: the PalmUnsureExtend and the PalmUnsureRepair classes. Both classes asks permission to the PalmLearn component before performing any action.

Algorithm 4 shows how the explore method is written for a PalmUnsureExtend component (compared to algorithm 2).

[explore(ext: PalmUnsureExtend, b: PalmBranching) : void
 -> when v := selectBranchingItem(b) 
    in (	
	propagateAllDecisionConstraints(ext.manager.problem, selectAuthorizedDecisions(b, v))
    ) 
    else ( 
	when nB := get(nextBranching, b) in explore(ext, nB) 
               // check the following branching
	else b.extender.manager.finished := true 
               // when no branching is left, search is terminated
    )]

[selectAuthorizedDecisions(b: PalmBranching, v: any) : list[AbstractConstraint]
 -> let accepted := false,
		ext := b.extender, 
		pb := ext.manager.problem
	in (
		let decisions: list[AbstractConstraint] := getNextDecisions(b)
		in (
			while not(checkAcceptable(b, decisions) 
                                  & checkAcceptable(ext.manager.learning, decisions)) (
					learnFromRejection(b),
					decisions := getNextDecisions(b)
                                        // decisions iteration
			),
			decisions
		)
	)]

As shown in algorithm 4 several new methods are defined. A PalmBranching object needs to check if the decision to be made is both acceptable by the PalmProblem itself (through the checkAcceptable method called on a PalmBranching) and by the PalmLearn component.

Moreover, decision constraints that are to be added must be iterated within the PalmBranching object: this is performed by the getNextDecisions method). Notice that each constraint rejection is notified to the PalmBranching object by the learnFromRejection method in which a contradiction is to be raised if there is no more possible decision constraint to add.

Using a PalmUnsureRepair modifies the way constraints are selected for relaxation during the repair phase. Algorithm 5 shows how it works.

[selectDecisionToUndo(repairer: PalmUnsureRepair, 
             e: Explanation) : (AbstractConstraint U {unknown})
 => let solver := repairer.manager, 
	learner := solver.learning,
	state := solver.state,
	cts := sortConstraintsToUndo(learner, e),
	idx_ct_out := 0,
	nbCandidates := length(cts),
	ct_out:(AbstractConstraint U {unknown}) := unknown,
	foundCandidate := false
    in (
	while (not(foundCandidate) & (idx_ct_out < nbCandidates))(
		idx_ct_out :+ 1,
		ct_out := cts[idx_ct_out],
		foundCandidate := checkAcceptableRelaxation(learner, ct_out)
	),
	if foundCandidate (
		ct_out
	)
	else 
	   unknown
     )]

In this version, constraints that constitutes the Explanation are sorted against a PalmLearn-related criterion. Then, constraints are iterated in the resulting order and permission for relaxation is asked to the PalmLearn component until a constraint is found.

If no constraint is satisfactory, selectDecisionToUndo returns unknown. This will raise a contradiction in repair as shown in algorithm 3.

As we saw in this note, search in PaLM is parameterized a set of components:

• an EXTEND component that is in charge of extending the current partial solution. Related objects: PalmExtend, PalmUnsureExtend and PalmBranching.

• a REPAIR component that is in charge of repairing the current contradictory partial solution. Related objects: PalmRepair and PalmUnsureRepair.

• a STATE component that is in charge of recording the current state of the search (the path in the search tree, ...). Related object: PalmState

• a LEARNING component that is in charge of keeping information about the past of the computation in order to avoid past errors. That information is only kept as wanted giving more opportunities to the user to keep space complexity as low as possible. Related object: PalmLearn.

The general search algorithm introduced in algorithm 1 can be seen as a generalization of the well known Dynamic Backtracking algorithm [Ginsberg, 1993]. Indeed, when using the provided PalmExtend and PalmRepair along with the PalmAssignVar branching is exactly the MAC-DBT algorithm.

Henceforth, our general search algorithm in its default configuration is sound and complete.

Notice that considering any branching mechanism that ensures the splitting of the search space in complementary pieces will keep those properties.

By modifying the constraint selection method, incomplete versions of the algorithm may be designed. The PATH-REPAIR algorithm is a good example (see also here).

Path-repair is a powerful heuristic for solving constraints problem. We present here an implementation of the tabu version of that algorithm using PaLM search-related objects.

First of all, recall that tabu path-repair is based on:

• selecting constraints to remove (in a repair step) based upon their frequence of apparition in contradiction explanations

• keeping track of past contradiction explanations in order to avoid loops in search

• cutting search if a certain amount of moves with no more improvements have been done

We need here a new learner: the PathRepairLearn class. This learner maintains a tabu list of past explanation in order to avoid past failures. The PathRepairLearn is described and coded in the p-solve.cl PaLM file (part 12).

We also need to PalmBranching that is capable of iterating possible constraint additions. We will base it upon the provided PalmAssignVar branching.

// defining a new branching
PathRepairAssignVar <: PalmAssignVar(
   variable: PalmIntVar, // the variable that is currently enumerated
   value: integer = 0 // the current value for iterating decision constraints
) 

// selecting a branching object
[selectBranchingItem(b: PathRepairAssignVar): any 
 -> when v := getMinDomVar(b.extender.manager.problem)
    in (
	b.variable := v,     // reset the iteration process
	b.value := getInf(v), 
	v
    ) 
    else unknown]

// iterating the set of constraints possible to add
[getNextDecisions(b: PathRepairAssignVar): list[AbstractConstraint]
 -> let ct := assign(b.variable, b.value)
    in (
	b.value :+ 1,
	list(ct)
    )]

// checking if the constraint is acceptable - mandatory redefinition
[checkAcceptable(b: PathRepairAssignVar, cts: list[AbstractConstraint]): boolean
 -> true] // no need for complicated code

// notice that the current constraint has been rejected
[learnFromRejection(b: PathRepairAssignVar): void
 -> let pe := b.extender.manager.problem.propagationEngine
    in (
        if (b.value = getSup(b.variable)) ( // no more available value
            raisePalmFakeContradiction(pe, becauseOf(theDom(b.variable)))
        )
    )]

It is now easy to perform a tabu path-repair solve for any PalmProblem.

// a 4x4 magic-square example
[demo() : void
 -> let pb := makePalmProblem("demo PR", 16),
	vars := list{ makeIntVar(pb, "x" /+ string!(i), 1, 16) | i in (1 .. 16) }
    in (
	post(pb, e-allDifferent(vars)),
	post(pb, e-sumVars(list{vars[i] | i in (1 .. 4)})           == 34),
	post(pb, e-sumVars(list{vars[i] | i in (5 .. 8)})           == 34),
	post(pb, e-sumVars(list{vars[i] | i in (9 .. 12)})          == 34),
	post(pb, e-sumVars(list{vars[i] | i in (13 .. 16)})         == 34),
	post(pb, e-sumVars(list{vars[i] | i in list(1,5,9,13)})     == 34),
	post(pb, e-sumVars(list{vars[i + 1] | i in list(1,5,9,13)}) == 34),
	post(pb, e-sumVars(list{vars[i + 2] | i in list(1,5,9,13)}) == 34),
	post(pb, e-sumVars(list{vars[i + 3] | i in list(1,5,9,13)}) == 34),
	post(pb, e-sumVars(list{vars[i] | i in list(1,6,11,16)})    == 34),
	post(pb, e-sumVars(list{vars[i] | i in list(4,7,10,13)})    == 34),
	setSolutionVars(pb, vars),
	attachPalmExtend(pb, PalmUnsureExtend()), // attaching a PalmUnsureExtend
	attachPalmRepair(pb, PalmUnsureRepair()), // attaching a PalmUnsureRepair
	attachPalmLearn(pb, makePathRepairLearn(PathRepairLearn,10,1000)),
	solve(pb, list(PathRepairAssignVar()))
    )]

Notice that in that particular instance, path-repair is not that efficient !

Branch and bound search in PaLM is performed by attaching a PalmBranchAndBound solver to the current problem. As in classical constraint programming solvers, branch and bound is performed by:

• computing a first solution to the complete problem

• geting the value of the objective variable (notice that there exists a getObjectiveValue method that returns that value)

• posting a new dynamic constraint that states that we must find a solution with a strictly better value for the objective variable. The postDynamicCut method is used.

• iterating that process until no new solution can be found (the last obtained solution being the best one).