next up previous contents
Next: ``Constructive'' Repair Up: Search Previous: Intelligent Backtracking and nogood

Solution Repair

At the end of the previous section we suggested that even for incomplete search, constructive search with good heuristics can outperform solution repair. However there are many important examples, such as job-shop scheduling and travelling salesman problems, where repair performs better than constructive search. Moreover repair is very important in handling dynamic problems, which change after an initial solution has been found. The problem may be changed because the user is unsatisfied with the solution for reasons which are not captured in the implementation, and adds new constraints to exclude this solution. Otherwise the change may be due to external circumstances such as unplanned delays, rush orders, cancellations, and so on.

ECLiPSe uses the concept of the tentative value to support solution repair. This is the same concept that is used to return proposed values for variables from the linear solver, as discussed in the preceding section. In the case of repair, however, the tentative value comes not from a constraint handler, but from the original solution to the original problem.

When the problem changes, some of the tentative values may no longer satisfy some of the new constraints. Indeed the simplest change is to constrain a variable to take a new value. In this case the tentative value violates the new constraint. In case there is no violation, of course, the tentative values comprise a feasible solution to the new problem and there is no need to repair the solution at all!

The purpose of the ECLiPSe repair library is to support the process of detecting a variable whose tentative value is in conflict with a constraint, and in detecting further violations that result from choosing a value for a variable that differs from its tentative value.

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