Constructive repair and weak commitment are two algorithms designed to find feasible solutions to a problem. In case the problem additionally requires some cost to be minimised, the repair must be adapted to return better and better solutions.

For unconstrained problems, local improvement can be achieved by just changing the value of some variable, having chosen the variable and value such that the cost of the new solution is better than the cost of the previous solution. This idea underlies the various hill-climbing algorithms as well as stochastic techniques such as Simulated Annealing and Tabu search.

For problems with constraints, changing the value of a variable will not necessarily yield a feasible solution. The ECLiPSe repair library can be used, however, to find a feasible solution which incorporates the change.

A simulated annealing program has been written in ECLiPSe which ensures that moves respect the problem constraints. The program has been compared with a pure simulated annealing approach which simply associates a cost with violated constraints and otherwise treats the problem as unconstrained. Experiments showed that the ``constrained simulated annealing'' program outperformed the pure one.

For an industrial application the repair library has been used
together with the *eplex* linear constraint library.
In the algorithm used for this application, the relaxed optimum is
checked against the repair
constraints, and at each step a violated constraint is strengthened in
such a
way that the next solution returned from *eplex* must satisfy it.
The algorithm outperforms standard MIP search because the problem is a
dynamic constraint problem: there is an original solution and the
requirement is to modify that solution to satisfy some new
constraints.

Details of these algorithms are beyond the scope of this article, but hopefully this brief survey has offered a glimpse of the power of repair-based search in combination with the different solvers of ECLiPSe.

Wed Sep 3 18:07:19 BST 1997