Recently, I've become interested in CP. As part of the learning process, I'm getting myself familiar with different CP solvers and IDEs available. I've already searched the web to see what is out there, which is probably best-documented here on OR-X. So, here are my questions:

  1. As far as I understand, the availability of more constraints and sophisticated search algorithms as well as connectivity to other solvers are the main factors for selecting a CP solver/IDE. Intending to work with large-scale problems, the performance of the solver (in terms of CPU time) is important to me as well. So, I'm wondering if there is any comparison of CP solvers and IDEs based on their performance on standard sets of CP instances (similar to what we have for LP and MIP solvers)?
  2. Eventually, I'm interested in hybrid methods, which requires integrating of MP and CP solvers. Besides the IBM ILOG CPLEX and Google OR-Tools, which other options are available out there (either in one package or not)?
  3. Which CP solver/IDE do you recommend for both pure and hybrid CP work?

Thanks in advance for your time and kind attention.

asked 01 Aug '16, 09:32

Ehsan's gravatar image

Ehsan ♦
4.8k31124
accept rate: 16%


Hi Ehsan,

  1. The MiniZinc challenge is an annual competition for CP solvers: http://www.minizinc.org/challenge.html P.S. Some industrial solvers, such as IBM ILOG CPLEX CPO, have not participated in this challenge.

  2. FICO XPRESS also has a CP solver (Kalis), and a modeling language that supports hybrid optimization.

  3. It depends on your application: For large-scale scheduling problems, I recommend IBM ILOG CPLEX CPO. For complex routing problems, I would recommend CPO or OR-Tools. Both can be used for 'pure' CP problem and for hybrid optimization.

link

answered 01 Aug '16, 11:49

Willem%20van%20Hoeve's gravatar image

Willem van H...
663
accept rate: 100%

edited 01 Aug '16, 11:50

Thanks @Willem and welcome to OR-X. Glad to have you here.

(01 Aug '16, 13:42) Ehsan ♦

As several other answers, I usually recommend MiniZinc as a first entry point to CP modelling as it is by far the simplest tool to use and you can already get great results. Unfortunately, there is currently no support for manually specified hybrid solving, although some of the underlying solvers use some "hybrid" technologies: for instance, SCIP supports MiniZinc and there are some portfolio solvers that may use both CP and MIP base solvers.

Another tool to look at is OscaR (https://bitbucket.org/oscarlib/oscar/), which is a toolkit comprising (among other things) a CP solver, a CBLS solver (local search), and a wrapper to several MIP solvers (namely gurobi, glpk, and lp_solve). OscaR is a Scala library, making for relatively succinct models (almost on par with modelling languages). I think there are a few examples in the distribution of hybrid CP-MIP solving.

Regarding the comparative performance of different CP solvers, one might want to study and choose according to which "global constraints" are implemented as they can make a huge difference. Most solvers will implement the famous "all-different" constraint but more specific constraints are not available (or as well implemented) in all solvers. For instance, if you are planning to solve scheduling problems, then OscaR has state-of-the-art propagators for the relevant constraints (usually called cumulative and disjunctive). But if you want to solve placement problems, you might want to use the "diff2" or "geost" constraints, which would rather be available in SICStus Prolog or Choco (if I remember correctly).

Then again, if you are able to use MiniZinc, then it is much easier to compare the performance of several solvers and find the most appropriate one. MiniZinc has limitations and sometimes you want to access features of solvers that are not available through MiniZinc, but it is certainly a very good way to prototype your models, and it happens that the prototype is good enough.

link

answered 02 Aug '16, 03:46

jmonette's gravatar image

jmonette
1413
accept rate: 50%

Thanks @jmonette. OscaR is very promising as it has various capabilities in addition to CP and MP. Although, it seems to be limiting for me as it requires me to migrate my previously-written codes from C++ and C# to Scala.

(02 Aug '16, 14:48) Ehsan ♦

Yes, this is not something I considered in my answer. Beside CPO and OR-tools, then Gecode is written in C++ and worth having a look at. It is also one of the solvers coming by default with MiniZinc.

(03 Aug '16, 07:08) jmonette

Dear Ehsan, I used MiniZinc IDE as CP and MIP solver. Recently, I have found JaCoP: http://jacop.osolpro.com/. I do not know its performance. Find a detailed answer in Håkan Kjellerstrand page about CP: http://www.hakank.org/constraint_programming_blog/

link

answered 01 Aug '16, 18:39

hkarimi's gravatar image

hkarimi
5839
accept rate: 0%

edited 01 Aug '16, 19:55

Thanks dear Hossein. I've been working with MiniZinc for sometime, however I'm not quite sure whether it is possible to have hybrid CP & MP model in MiniZinc. Do you have any experience with that?

(02 Aug '16, 01:15) Ehsan ♦

No, I did not try to hybrid CP & MIP in MiniZinc before.

(02 Aug '16, 05:09) hkarimi

MiniZinc is a great starting point. The MiniZinc developers also released a MiniZinc IDE which greatly lowers the entry barrier. Check it out at http://www.minizinc.org/ide

link

answered 01 Aug '16, 19:28

turli's gravatar image

turli
212
accept rate: 0%

Thanks @turli. I've started with MiniZinc and it seems nice.

(02 Aug '16, 01:08) Ehsan ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×46
×39
×37
×3

Asked: 01 Aug '16, 09:32

Seen: 1,241 times

Last updated: 03 Aug '16, 07:08

OR-Exchange! Your site for questions, answers, and announcements about operations research.