next up previous contents
Next: Local Improvement Up: Solution Repair Previous: ``Constructive'' Repair

Weak Commitment

Instead of instantiating a variable in order to repair it, an alternative method is simply to change its tentative value. This approach requires no backtracking, since every conflict can be fixed by just changing tentative values. The disadvantage is that cycles can easily occur in which two variables repeatedly switch their tentative values.

A very successful algorithm based on repairing tentative values is called Weak Commitment [Yok94]. On starting all the variables have tentative values. Variables in conflict are repaired - by instantiating them - until either there are no more conflicts and the algorithm terminates, or the remaining conflicts cannot be repaired. The latter situation occurs when some variable in conflict cannot be instantiated to any value that is consistent with the variables instantiated so far.

When such a dead-end is encountered, the weak commitment algorithm simply uninstantiates all the variables, setting their tentative values to the values they had when they were instantiated. Then the algorithm restarts, fixing conflicts as before.

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997