CP, AI and OR researchers have devised very sophisticated algorithms for solving a variety of constraint satisfaction and optimisation problems. Now the boundaries between these different research communities are breaking down, and we are learning how our strengths and weaknesses complement each other. At the same time, a typical problem coming from industry comprises different kinds of constraints and variables, and is best handled by combining different approaches. Consequently at IC-Parc we are developing new techniques of combining models and algorithms - new forms of hybridisation.
Until appropriate forms of hybridisation are developed, it is only possible to combine algorithms by understanding their behaviour completely and building a new hybrid algorithm from scratch. Our aim is to define a set of modelling components that enable algorithms to be reused and combined without rewriting.
A hybridisation form is a mapping from two (or more) algorithms to a hybrid algorithm. For example one hybridisation form can be applied to any constraint propagation algorithm and any constructive search technique to produce an algorithm that interleaves propagation and search. Just as a single hybridisation form can be used to combine many different algorithms, so also there may be many different applicable hybridisation forms to hybridise a pair of algorithms. Some examples of hybridisation forms will be discussed, using ECLiPSe to illustrate their representation in the problem model.
Currently combining algorithms is a black art, practised only by modern alchemists. We seek to make it accessible to people with different levels of expertise, ranging from top chefs to amateurs with recipe books.