How to combine MIP solver with a CP one?

Question

I am working on the scheduling problem in the class of parallel resource scheduling models. When I have studied some papers regarding that, I see the method that combines an MIP with a CP. The proposed procedure was:

The formulation was divided into two parts. The first part, actually assigning parts, was solved by an MIP solver, and the second part, the disjunction part, was solved by a CP solver. And as far as I understand these parts work simultaneously in the branch and cut algorithm. (This is where I am interested in).

Now, I would like to know if there is any resource, particularly, code source to see how this method works.

---

_{[1] Ruslan Sadykov, Laurence Wolsey. Integer Programming and Constraint Programming in Solving a Multimachine Assignment Scheduling Problem with Deadlines and Release Dates. May 2006 - INFORMS Journal on Computing. 18(2):209-217}

Answer 1

I think they actually state it very clearly in the paper in the part they call Algorithm 3. IP/CP: solve a relaxation of the original and then generate no-good cuts that remove infeasible solution. In order to separate no-good cuts, a CP model is used to check whether the current solution is feasible or not. The method is very similar to combinatorial benders’ where the sub problem is solved using a CP model.

Answer 2

General

Many works combining MILP and CP are what's sometimes called logic-based benders decomposition and there is even a book on the topic:

Hooker, John. "Logic-Based Benders Decomposition: Theory and Applications." (2023).

Besides Hooker who probably coined the term, most of the work i read (scheduling/routing) was from Christopher Beck

For a good background (when shift from master to sub-problem solver: basically with primal feasible solution or only when reached an optimal one), the following might also be a worthwile read:

Beck, J. Christopher. "Checking-up on branch-and-check." Principles and Practice of Constraint Programming–CP 2010: 16th International Conference, CP 2010, St. Andrews, Scotland, September 6-10, 2010. Proceedings 16. Springer Berlin Heidelberg, 2010.

Implementation

A high-quality implementation (linked to papers and a dissertation) which is a bit more far-reaching (and therefore introducing some complexity) would be:

https://github.com/ed-lam/nutmeg

This and some others howewer are using CP/SAT-Hybrids as their sub-problem solver component aka "CP" (or-tools cp-sat is also a CP/SAT/MILP-hybrid).

Among other differences to pure CP, these hybrids are very good at efficiently inferring conflict-clauses (because of SAT-style conflict-analysis) which is a very good thing in LBBD because the cuts will be much more accurate.

Imagine a vehicle-routing problem where a MILP does assign routes to vehicles and the sub-problem solver not only recognized that this tour of 11 stops isn't feasible (e.g. duration or time-windows) but efficiently infer that out of those 11 stops, those 3 alone are a source of infeasibility.

Compare with some or-tools cp-sat API:

  // A list of literals. The model will be solved assuming all these literals
  // are true. Compared to just fixing the domain of these literals, using this
  // mechanism is slower but allows in case the model is INFEASIBLE to get a
  // potentially small subset of them that can be used to explain the
  // infeasibility.
  //
  // Think (IIS), except when you are only concerned by the provided
  // assumptions. This is powerful as it allows to group a set of logically
  // related constraint under only one enforcement literal which can potentially
  // give you a good and interpretable explanation for infeasiblity.
  //
  // Such infeasibility explanation will be available in the
  // sufficient_assumptions_for_infeasibility response field.
  repeated int32 assumptions = 7;

The paper linked to the implementation even claims, that this general-purpose conflict-analysis discovers the same cuts as specialized TSP/VRP ones developed specifically for these tasks.