1

In have recently addressed a couple of scheduling projects using CP Optimizer (the CPLEX Constraint Programming solver) and was able to get some really good results with it. However, compared to Cplex, CP Optimizer is still a big black box for me. Often it is possible to formulate a problem in different ways and small changes can make huge differences in performance. In my opinion there is a lack of documentation and examples, which makes it hard to work with it. There is also no standardized set of constraints that is shared by all constraint programming solvers and not even an export format that would allow me to take a problem that was stated with CP Optimizer and an alternative solver (Xpress Kalis or an open source alternative like Gecode, for example).

While I am aware that commercial MIP solvers are much more powerful than open source alternatives, I haven't seen any studies that compare different constraint programming solvers.

I was wondering how other constraint programming solvers compare to CP Optimizer. I am particularly interested in scheduling applications, for which CP Optimizer has a special set of variables (interval and sequence) and a lot of useful constraints (precedence, no overlap etc.). I don't mind using integer variables instead of interval variables and formulating constraints in a more complex way, but I was wondering if there are any open source constraint programming solvers that can compete with the commercial ones.

Petr Vilím
  • 175
  • 5
wsg
  • 161
  • 1
  • 6
  • I know of https://www.minizinc.org/challenge.html. Unfortunately it does not include IBM's CP solver. As performance is very problem (and implementation) specific, you may be better off by trying things out with your actual problems. – Erwin Kalvelagen Dec 16 '19 at 02:15
  • Gecode has all those modelling options you mention (although possibly under different names). There is no interval-var in vanilla-gecode, but i did not miss those yet. It has very high-quality implementations of state-of-the-art propagators, which are actually following Petr's (the one answering below) research-work. Also other state-of-the-art cp features like propagator-rewriting; dynamic scheduling of propagators and such things. Gecode can be very powerful, but i expect CPOPT to be much better as black-box,using lp-relaxation guided-search,lns-search, restarts + other tricks automatically – sascha Dec 19 '19 at 00:58

1 Answers1

8

There are actually multiple questions. As CP Optimizer developer I try to answer some that are directly related to CP Optimizer.

Before CP Optimizer there was ILOG Solver and ILOG Scheduler. Scheduling problems were modeled by "activites" in Scheduler, an activity consisted from several integer variables. Scheduler was a success, but it was harder and harder to keep up with customer needs. Industrial problems often contain some kind of alternative recipes, alternative resources, optional goals etc. It was hard to model them using activities (e.g. what is a length of an unperformed activity?). It was also hard to solve those models.

For this reason ILOG Scheduler was discontinued. And instead we created CP Optimizer with optional interval variables. We designed completely new language for scheduling problems that, by our opinion, allows to describe scheduling problems in more simple ways. And it gives the solver information it needs to solve the problem more efficiently. If you want to know more I recommend the following papers:

  • Laborie, Rogerie: Reasoning with Conditional Time-intervals
  • Laborie, Rogerie, Shaw, Vilim: Reasoning with Conditional Time-intervals, Part II: an Algebraical Model for Resources

Therefore comparing with other solvers, the scheduling language is mostly different. And if you come from a different solver, you have to write your (scheduling) model from scratch. But we believe it pays off since the alternative is "Scheduler-like" model. That's the reason there's no common export format.

Regarding efficiency of CP Optimizer. Yes, there is no direct comparison. I'm afraid you have to experiment for yourself. And write your model twice since the languages are different. If I may give just one argument why it may be worth trying then, for example, CP Optimizer was able to solve number of scheduling problems that were open for decades:

  • Vilim, Laborie, Shaw: Failure-directed Search for Constraint-based Scheduling

Finally regarding the fact that small change in the model can have a dramatic impact on the performance. Yes, it is usual. And I don't think it is only CP Optimizer that suffers from it. It helps to understand in some degree how the solver works. Still sometimes I also cannot guess in advance what approach will be the best. So my advice is to experiment. Usually shorter models perform better. Luckily experimenting with different versions of the model is not that expensive.

Xavier Nodet
  • 5,033
  • 2
  • 37
  • 48
Petr Vilím
  • 175
  • 5