Comment by wenc | Hacker News Reader

Comment by wenc | Hacker News Reader

Parent Full thread

> Pulp and Jump are interfaces to CBC, GUROBI, CPLEX, XPRESS

Right, which is different from MiniZinc.

But to answer your original question "Can someone explain why I would use this instead of Python + Pulp or Pyomo, or Julia + JuMP", I don't think Pulp and Jump can handle constraint programming explicitly unless you reformulate the CP as an MIP or similar. As you alluded to, this is Minizinc's advantage -- it's a modeling language specifically for CPs, which Pulp and Jump are not. Despite the mathematical equivalencies, CP folks model stuff a little differently from MIP folks (modeling is more convoluted for MIPs).

To expand, Pulp and Jmp write out .nl files (AMPL binary format for optimization), which is a standard format for many optimization solvers. I don't know much about flatzinc, but due to a subset of mathematical equivalencies, I imagine the interfaces are able to translate to .nl, in which case, any number of optimization solvers can be deployed. However, the converse doesn't seem to be true -- I don't think models written in Pulp and Jmp can call CP solvers (not sure if there's an .nl subset to flatzinc interface).

Thank you for the explanation. Any idea why one would choose to use CP over an LP, IP, or MIP solver? Maybe some CP problems can't be translated? I'm not sure what the mathematical relationship is.

Most MIP solvers contain performance heuristics tailored to MIP metaphors.

If you're using translation, some CPs could translate into MIP formulations that MIP-solvers happen to not handle that well (these are theoretical worst-case exponential problems, and you can't know a priori if your solver is going to hit the worst case; MIP solvers are fast in general but there's a measure of luck involved in the solution process -- anyone who does discrete optimization for a living knows this). You're also at the mercy of the translation algorithm, which may not possess a library of the most efficient MIP formulations. Furthermore, MIP modeling is an art which takes years to hone (less so today than when I started -- algorithms are getting more and more sophisticated -- but nevertheless, it takes human reasoning and intuition to produce a good formulation).

It's always useful have a range of solvers at your disposal and not limit yourself. CP solvers are specialized to CP problems and for simple problems they may work better due to less translation overhead.

MIP solvers work themselves through the search tree using all sorts of clever tricks, constantly running LPs on relaxations (approximations) of the problem to prune the tree. They can be very efficient, but the constraints need to be linear for the LPs to work.

CP solvers are less sophisticated in their search (although some are getting more clever [1]), but they instead delegate to graph-theoretical algorithms [2] that can efficiently deal with more high-level constraints, for instance "I only want solutions where all these variables have different values", which in the MIP world would translate to tons of auxiliary linear constraints and variables that would slow down your solver.

So it really depends on how you write your model, and it's not even always obvious whether MIP or CP is better – which is why Minizinc is so useful. There are even attempts to automatically choose the algorithm to use based on the problem structure [3].

[1] https://github.com/chuffed/chuffed [2] http://www.emn.fr/x-info/sdemasse/gccat/sec5.html [3] https://github.com/CP-Unibo/sunny-cp

Reply on news.ycombinator.com