Previous Up

11.6  Examples

More examples of repair library use, in particular in the area of local search, can be found in the Tutorial on Search Methods.

11.6.1  Interaction with Propagation

In the following example, we set up three constraints as both repair and fd-constraints (using the r_conflict_prop annotation) and install an initial tentative assignment (using tent_set). We then observe the result by retrieving the conflict sets: 

[eclipse 1]: lib(repair), lib(fd).             % libraries needed here
yes.
[eclipse 2]:
        fd:([X,Y,Z]::1..3),                    % the problem variables
        fd:(Y #\= X) r_conflict_prop confset,  % state the constraints
        fd:(Y #\= Z) r_conflict_prop confset,
        fd:(Y #=  3) r_conflict_prop confset,
        [X,Y,Z] tent_set [1,2,3],              % set initial assignment
        [X,Y,Z] tent_get [NewX,NewY,NewZ],     % get repaired solution
        conflict_constraints(confset, Cs),     % see the conflicts
        conflict_vars(Vs).

X = X{fd:[1..3], repair:1}
Y = 3
Z = Z{fd:[1, 2], repair:3}
NewX = 1
NewY = 3
NewZ = 3
Cs = [3 #\= Z{fd:[1, 2], repair:3}]
Vs = [Z{fd:[1, 2], repair:3}]

Delayed goals:
     ...
yes.

Initially only the third constraint Y #= 3 is inconsistent with the tentative assignment. According to the definition of r_conflict_prop this leads to the constraint Y #= 3 being propagated, which causes Y to be intantiated to 3 thus rendering the tentative value (2) irrelevant.

Now the constraint Y #\= Z, is in conflict since Y is now 3 and Z has the tentative value 3 as well. The constraint starts to propagate and removes 3 from the domain of Z [1..2].

As a result Z becomes a conflict variable since its tentative value (3) is no longer in its domain. The Y #\= Z constraint remains in the conflict constraint set because Z has no valid tentative assignment.

The constraint Y #\= X is not affected, it neither goes into conflict nor is its fd-version ever activated.

To repair the remaining conflicts and to find actual solutions, the repair/0 predicate described below could be used.

11.6.2  Repair Labeling

This is an example for how to use the information provided by the repair library to improve finite domain labeling. You can find the repair/1 predicate in the ’repairfd’ library file. 

repair(ConflictSet) :-
    ( conflict_vars([C|_]) ->       % label conflict
        indomain(C),                %  variables first
        repair(ConflictSet)
    ; conflict_constraints(ConflictSet, [C|_]) ->
        term_variables(C, Vars),    % choose one variable in
        deleteffc(Var,Vars, _),     %  the conflict constraint
        Var tent_get Val,
        (Var = Val ; fd:(Var #\= Val)),
        repair(ConflictSet)
    ;                               % no more conflicts:
        true                        % a solution is found.
    ).

The predicate is recursive and terminates when there are no more variables or constraints in conflict.

Repair search often finishes without labeling all variables, a solution has been found and a set of tenable variables are still uninstantiated. Thus even after the search is finished, Repair library delayed goals used for monitoring constraints will be present in anticipation of further changes.

To remove them one has to ground these tenable variables to their tentative values.

Note that the example code never changes tentative values. This has the advantage that this is still a complete, monotonic and cycle-free algorithm. However, it is not very realistic when the problem is difficult and the solution is not close enough to the initial tentative assignment. In that case, one would like to exploit the observation that it is often possible to repair some conflict constraints by changing tentative values. During search one would update the tentative values to be as near as pssible to what one wants while maintaining consistency. If the search leads to a failure these changes are of course undone.

Previous Up