5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I don't know it is exactly relevant but Google OR-Tools has a CP-SAT algorithm doing something similar. developers.google.com/optimization/cp/cp_solver $\endgroup$
    – berkorbay
    Dec 11, 2023 at 18:59
  • $\begingroup$ @berkorbay, Thank you so much for mentioning this. I am not an or-tools user, but I will see that asap. $\endgroup$
    – A.Omidi
    Dec 12, 2023 at 4:50

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, @Sune, for your answer. I saw the mentioned paragraph, but as I have no experience with Benders and its variants, I cannot understand the gist of that. Based on what you proposed, is it possible to say, that the problem was solved based on the combinatorial Benders algorithm? And also, do you have any similar materials? $\endgroup$
    – A.Omidi
    Dec 12, 2023 at 4:57
  • 1
    $\begingroup$ @A.Omidi The general idea probably qualifies as combinatorial benders. Regarding a reference I am sorry to say I have non. It is mentioned in many papers on combinatorial benders that the sub problem could be solved by CP but I cannot recall I have ever seen it done $\endgroup$
    – Sune
    Dec 12, 2023 at 16:51
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you so much for the detailed explanation and already the mentioned link. 🙏 $\endgroup$
    – A.Omidi
    Dec 13, 2023 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.