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.