Combining CP and MIP

Application problems often combine different subproblems that are solved better with one or another solver, making the complete problem difficult or unmanageable for a single solver. A typical example is production planning and scheduling applications. The long-term (planning) aspects are usually more easily handled by LP solvers whereas the short-term (scheduling) subproblems are better suited for CP solvers. Solving these two parts completely independent of each other may lead to infeasible scheduling subproblems or plans that do not correspond to the reality of production. A possible solution to this dilemma is to iteratively solve LP planning problems and CP scheduling problems, until a feasible schedule for the planned quantities is obtained.

Another method of combined MIP-CP problem solving that provides a tighter integration of the two techniques consists of solving CP subproblems for generating cuts at the nodes of a MIP Branch-and-Bound search. This technique has already been applied successfully to several large-scale planning and scheduling applications by PSA and BASF (see for instance the description of hybrid MIP-CP algorithms implemented with Mosel in [BP03] and [Sad04]). This type of combination is more technical than sequential CP and LP/MIP solving since it requires the developer of the algorithm to interact with the MIP search at every node.

Cut generation algorithms can be implemented with the help of the Xpress Optimizer callbacks (see the `Mosel Language Reference Manual' for the definition of callbacks with Mosel and the `Xpress Optimizer Reference Manual' for an explanation of the Optimizer callback functions).

The original description of the example in this section was published in [JG99]. A prototype implementation was developed by N.  Pisaruk in the context of the EU-project LISCOS.