Richer Hybridisation
With the different kinds of constraint solver and search methods, the range of possible hybridisation forms which combine them into different algorithms is considerable. The challenge here is to enable the user to take advantage of the power and flexibility of hybridisation, without asking him or her to implement each hybridisation needed for each industrial application again and again. Instead of an `assembly language' (in the literal sense), the user requires something closer to a scripting language.
A useful example is the incorporation of cutting plane techniques into the constraint programming framework. Given a solution to a relaxed problem, which happens to violate a relaxed problem constraint, a cutting plane is a new linear constraint added to exclude the previous violation. This technique can be applied to classes of `easy' and `difficult' constraints. Difficult constraints are relaxed, and a solution feasible for the easy constraints is found. Then a new easy constraint is imposed which precludes the previous violation and the new relaxed problem is solved. In a CP framework a variety of `difficult' constraints could be implemented together that generate a class of `easy' constraints when they are violated. This represents a new kind of constraint behaviour and represents a potential new class of global constraints of this kind.
Different problem decomposition techniques, such as Dantzig-Wolfe decomposition, offer natural hybridisation forms. For Dantzig-Wolfe decomposition, the subproblem can be solved by constraint propagation, or graph algorithms. The subproblem solution yields a new `column' which is added to the master problem and this is solved using linear programming. Similar hybridisation forms can be built from Benders and Lagrangian decomposition.
The different kinds of search offer a rich source of hybridisation forms. Loose hybridisation forms apply tree search to one subproblem and local search to another. Alternatively one form of search can be applied first (e.g. local search to obtain a tight cost bound) and then another form of search subsequently (e.g. tree search to obtain proof of optimality). There are also a variety of tight hybridisations. We give two useful examples. Rather than finding a complete feasible solution, using tree search, and improving on it using local search, it is much more effective to combine the two forms of search more tightly. A solution is constructed by labelling one variable at a time, but each partial solution is immediately improved by local search before the next variable is labelled. The second example has local search as the underlying method. However it is only applied to a subset of the decision variables. Given an assignment to these variables, a constructive labelling is used to complete the partial solution to a complete solution from which the cost can be derived. The local search method then changes the assignment to the original subset of variables and this is again completed by constructive search.
The identification of general classes of algorithms and a minimal `covering' set of hybridisation forms is a very important research goal. Success will make it straightforward to design a mapping formalism that allows the user to freely experiment with different hybrid algorithms to solve his or her problem.