``Constructive'' Repair

There are several very different repair algorithms that arise from different choices of how to change the value of a variable from its tentative value. The algorithm most similar to constructive search simply instantiates the variable to the chosen new value. In this case the tentative values do no more than support a specific heuristic within a constructive search algorithm. Notice that the heuristic can do more than simply choosing the tentative value as the first guess for each variable during labelling. It can also take into account for each value for a variable the number of other tentative values with which it conflicts according to the constraints. Thus when a variable is labelled to a new value, the value is chosen so as to minimise disruption to the original solution.

The ECLiPSe repair library defines primitives for setting a tentative value for a variable (tent_set) and for looking it up (tent_get). It also supports a special annotation which changes the behaviour of a constraint from propagation to simply checking against the tentative values of their uninstantiated variables. The annotation is written Constraint r, where Constraint can be any built-in or user-defined constraint. Whenever the check fails, the constraint is recorded as a conflict constraint, and full propagation on the constraint is switched on. The set of conflict constraints can be accessed via the predicate conflict_constraints. This can be used in the search procedure to decide which variable to label next.

A built-in search predicate called repair is provided which selects a variable whose tentative value violates a repair constraint, labels it and succeeds when all the remaining variables have consistent tentative values.

We illustrate this repair algorithm (with an example from the IC-Parc ECLiPSe library manual [SNE97]) in figure 5.2.1.

solve(X,Y,Z) :-
        [X,Y,Z]::1..3,                    % the problem variables
        Y ## X r,                         % state the constraints
        Y ## Z r,
        Y #= 3 r,
        [X,Y,Z] tent_set [1,2,3],              % set existing solution
        repair,                           % invoke repair labeling
        [X,Y,Z] tent_get [NewX,NewY,NewZ].  % get repaired solution

The ``Constructive'' Repair Algorithm  

The solutions found are [1,3,1] and [1,3,2], which means that only Z has been repaired. Initially only the constraint is inconsistent with the solution so variable Y is repaired to take the value 3. This now affects the constraint , and Z must be repaired to either 1 or 2.

The constraint is not affected by the update. In particular, X keeps the value of the existing solution, and is not even being labeled by repair/0.

Constructive repair is also known as informed backtracking and has been used successfully on a variety of benchmarks [MJPL92].