Previous Up Next

10.4  Conflict Sets

Given a tentative assignment, there are two kinds of conflicts that can occur: To obtain a tentative assignment which is a solution to the given problem, both kinds of conflicts must be repaired. The repair library supports this task by dynamically maintaining conflict sets. Typically, a search algorithm examines the conflict set(s) and attempts to repair the tentative assignment such that the conflicts disappear. When all conflict sets are empty, a solution is found.

conflict_vars(-Vars)

When a variable becomes untenable, it appears in the set of conflict variable, when it becomes tenable, it disappears. This primitive returns the list of all currently untenable variables. Note that all these variables must be reassigned in any solution (there is no other way to repair untenability). Variable reassignment can be achieved by changing the variable's tentative value with tent_set/2, or by instantiating the variable. Care should be taken whilst implementing repairs through tentative value changes since this is a non-monotonic operation: conflicting repairs may lead to cycles and the computation may not terminate.

conflict_constraints(+ConflictSet, -Constraints)

When a repair constraint goes into conflict (i.e. when it does not satisfy the tentative assignment of its variables), it appears in a conflict set, once it satisfies the tentative assignment, it disappears. This primitive returns the list of all current conflict constraints in the given conflict set. ConflictSet is the conflict set name (or handle) which has been used in the corresponding constraint annotation. For example
conflict_constraints(cap_cstr, Conflicts)
would retrieve all constraints that were annotated with cap_cstr and are currently in conflict.

At least one variable within a conflict constraint must be reassigned to get a repaired solution. Variable reassignment can be achieved by changing the variable's tentative value with tent_set/2, or by instantiating the variable. Care should be taken whilst implementing repairs through tentative value changes since this is a non-monotonic operation: conflicting repairs may lead to cycles and the computation may not terminate.

Note that any repair action can change the conflict set, therefore conflict_constraints/2 should be called again after a change has been made, in order to obtain an up-to-date conflict set.

poss_conflict_vars(+ConflictSet, -Vars)

The set of variables within the conflict constraints. This is generally a mixture of tenable and untenable variables.


Previous Up Next