Constraint logic programming uses logical variables. This means that when a variable is instantiated, its value must satisfy all the constraints on the variable. For example if the program includes the constraint X>=2, then any attempt to instantiate X to a value less than 2 will fail.
However, there are various contexts and methods in which it is useful to associate (temporarily) a value with a variable that does not satisfy all the constraints on the variable. Generally this is true of repair techniques. These methods start with a complete, infeasible, assignment of values to variables and change the values of the variables until a feasible assignment is found.
Repair methods are useful in the case where a problem has been solved, but subsequently external changes to the problem render the solution infeasible. This is the normal situation in scheduling applications, where machines and vehicles break down, and tasks are delayed.
Repair methods are also useful for solving problems which can be broken down into quasi-independent simpler subproblems. Solutions to the subproblems which are useful for solving the complete problem, may not be fully compatible with each other, or even completely feasible with respect to the full problem.
Finally there are techniques such as conflict minimisation which seek solutions that minimise infeasibility. These techniques can be treated as optimisation algorithms, whose constraints are wrapped into the optimisation function. However they can also be treated as repair problems, which means that the constraints can propagate actively during problem solving.
Repair is used for:
- Re-solving problems which have been modified
- Combining subproblem solutions and algorithms
- Implementing local search
- Implementing powerful search heuristics
Figure 13.1: Uses of Repair