Search

Richer Search

Constraint programming systems typically employ tree search to complement constraint propagation. Moreover the search is depth first and alternative search choices are only explored after backtracking to the relevant choice point. This form of search makes very efficient use of the computational memory available.

By contrast MIP search typically explores the search tree in a best-first fashion, which requires a multitude of `open' nodes to be recorded, ready for expansion at a later time. The memory requirements were traditionally kept down by recording very little information about each open node.

Increasingly there is a recognition that the facility to record a set of open nodes, to which the search can jump, is important for CP: the Oz CP system pioneered this view, and ECLiPSe implemented this functionality in support of `or-parallel' search. At the same time, MIP implementers now recognise that it is possible to record more information about each open node without exceeding the computer's virtual memory. With G12 we shall pursue the convergence of CP and MIP search by reducing the cost of jumping between open nodes, and maintaining flexibility between the many different tree search strategies.

However local search techniques are playing an increasingly important role in CP. The Comet CP system supports a wide range of local search techniques (enabling the programmer to implement simulated annealing, tabu search, and GSAT for example), with constraint handlers adapted to the local search paradigm. The final addition to the arsenal of search methods offered by G12 will be population-based search methods, such as genetic algorithms. These methods explore a whole population of solutions concurrently, and then combine the results from the population to focus the search on promising areas of the search space.

To date no system has enabled the user to specify the problem in terms of an algorithm-independent conceptual model, and have the computer map this into, say, an ant colony optimisation algorithm. The challenge for G12 is not to make this mapping automatic, but rather to enable the user to augment the conceptual model with enough control information to make the choice of (say) ant colony optimisation unique and unambiguous.