Summary

The examples in this whitepaper show two schemes of combining CP and LP/MIP modeling and problem solving. Whilst the first is a loosly coupled combined algorithm (execution of a CP and an LP problem in sequence) the second is an example of a fairly tight integration, using CP as cut generation algorithm for a MIP branch-and-cut search. Many other schemes are possible (for instance, iterative solving of a series of MIP and CP subproblems as in [Tim02])—an hybridization scheme must always be chosen depending on the particular structure of an application problem and its typical data instances.

Although the combination of different solving techniques has proven successful in a number of applications, the author would like to issue a warning to the interested reader that it is seldom worthwhile spending time on a problem that can be tackled by one of the techniques separately. Hybrid solution algorithms need to be developed, implemented, and tested on a case-by-case basis, meaning a considerable investment in terms of development effort and requiring a good understanding of the solution methods and solvers involved.