10
$\begingroup$

I know some general concepts regarding Constraint Programming (e.g., the ones explained in this answer). I am interested in learning how to formulate a combinatorial optimisation problem as a constraint programming model. What steps should be taken for developing such a formulation? What is the standard practice/convention?

For example, the quality of LP-relaxation is an important factor for deciding the quality of an integer program. I was wondering what formulations are considered as good in constraint programming?

Finally, I appreciate if someone could give a simple example of an integer program and compares the way(s) it can be represented as a constraint program.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

at https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer

you may find some information about RCPSP with Linear programming and constraint programming.

Plus https://tidel.mie.utoronto.ca/pubs/JSP_CandOR_2016.pdf

concludes

Comparing the best MIP results with that of CP, results show that MIP performs similarly to CP for smaller problems in terms of proving optimality. However, CP dominates MIP for larger problems both in terms of proving optimality and solution quality.

Let me show how they are different and similar with OPL for jobshop :

With Linear Programming one can write

 int nbJobs = ...;
int nbMchs = ...;

range Jobs = 0..nbJobs-1;
range Mchs = 0..nbMchs-1;
// Mchs is used both to index machines and operation position in job

tuple Operation {
  int mch; // Machine
  int pt;  // Processing time
};

Operation Ops[j in Jobs][m in Mchs] = ...;

dvar int+ s[j in Jobs][o in Mchs];
dexpr int e[j in Jobs][o in Mchs]=s[j][o]+Ops[j][o].pt;



minimize max(j in Jobs) e[j][nbMchs-1];
subject to {
  forall (m in Mchs,ordered i,j in Jobs, o1 in Mchs,o2 in Mchs:Ops[i][o1].mch == m && Ops[j][o2].mch == m)
    (e[i][o1]<=s[j][o2]) || (e[j][o2]<=s[i][o1]);
  forall (j in Jobs, o in 0..nbMchs-2)
    e[j][o]<=s[j][o+1];
}

execute {
  for (var j = 0; j <= nbJobs-1; j++) {
    for (var o = 0; o <= nbMchs-1; o++) {
      write(s[j][o] + " ");
    }
    writeln("");
  }

whereas with Constraint Programming you would directly write a much better model that is within IBM CPLEX Optimization Studio

NB:

I am an IBM employee

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks Alex. The paper you attached includes a time indexed formulation for the scheduling problem studied. Such formulations are generally known for their good LP bound. I am not sure how good the time-indexed model is written but it seems that CP has performed better than this formulation. Can we solve an integer linear program with CP (without using alldifferent etc)? Is that a bad practice? It seems that the quality of LP bound is not quite important for CP (right?). Feel free to add details to your answer (not in the comment section in response to my comment). $\endgroup$
    – rasul
    Sep 10, 2019 at 14:13
  • $\begingroup$ You can solve an integer linear model with CP. You may solve an IP with both LP and CP, or even hybrid the 2 techniques. But for scheduling models, CPO intervals will outperform that CP naïve formulation. 20 years effort as you can read at ibm.com/developerworks/community/forums/html/… $\endgroup$
    – Alex Fleischer
    Sep 10, 2019 at 14:22
  • 1
    $\begingroup$ I think it should be pointed out in the answer (for the benefit of those not inclined to read the cited paper) that CP beats MIP for a class of job shop scheduling problems (not in general, which a casual reader might infer from the answer). $\endgroup$
    – prubin ♦
    Sep 10, 2019 at 20:37
3
$\begingroup$

I'm considerably more familiar with integer programming than with constraint programming, so what I'm about to say is personal opinion. I think one key characteristic of a "good" CP model is one that exploits global constraints. The best known global constraint is, I think, the "all different" constraint.

There is a possibly subtle implication to this. MILP solvers differ in their internals (what cuts they apply and when, for example), but they all work from models containing the same basic components (linear constraints, linear objectives, integrality restrictions, variable bounds). There may be some differences at the margin, regarding whether they inherently support SOS1 and SOS2 constraints and logical implications (and things like second order cone constraints, if you need to work with quadratic models), but I suspect that most commercial or high-quality open-source solvers have a pretty common set of model elements they can handle. So, for the most part, a "good" MIP formulation is a "good" formulation regardless of which solver you are using.

In contrast, I don't think there is a particularly large set of global constraints understood by all major CP solvers (although, somewhat ironically, I would bet that they are all similar in having "all different"). So, for instance, in developing a CP model for solving cutting stock problems, you would want to look for global constraints related to rectangles not overlapping. I don't know whether every good CP solver has them (maybe: similar constraints arise in resource scheduling), and, if so, I don't know whether every good CP solver supports non-overlap in the same way, and with equal efficacy.

So this is my long-winded way of saying that what makes a "good" CP model might be more solver-dependent than what makes a "good" MIP model is.

Improve this answer
$\endgroup$

Your Answer

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

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