Constraint Solving with MiniZinc
hillelwayne.com
hillelwayne.com
Minizinc makes it easy to spell out a problem, try different ways to formulate the same constraint, and run the same model on some external data through lots of different solvers to see which one works best. It comes with an enormous constraint catalogue adapted to each solver.
Whether you then use PuLP, OR-tools, JuMP etc. (or even Minizinc itself) for the actual implementation is up to you; but I've found that it is hard to beat when I am at the prototyping stage.
However when I looked at this some years ago, I came across journal publications that found mixed integer program (MIP) solvers to be much faster than constraint solvers for many problems. I suspect that this was because MIP theory was much more well developed at the time and that commercial interests (airline scheduling, oil and gas, etc.) were driving impressive improvements in MIP solver technology (dominant players are IBM CPLEX, Gurobi and Xpress), whereas constraint programming remained more or less a niche domain in computer science.
Btw...Picat looks like it has similarities to Minizinc.
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).
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
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.
http://hakank.org/common_cp_models/ is a page which collects models that solve the same problem in different CP systems (and mostly with the same approach). It can be used to compare similarities and differences between systems, though one have to do the comparison oneself.
A long time ago (in 2012) I did a talk on comparing features in different CP systems mostly focused how "easy" - subjectively and IMHO - it was to learn the systems: http://hakank.org/constraint_programming/sweconsnet_talk_201...
The most succinct difference is (usually) a constraint solver is going to find a solution (or the best solution) while a DFS logic will attempt to enumerate all solutions.
For example, consider a geometric problem of placing a point on the plane according to constraints (such as left of line AB, above line CD, etc.) Assuming a solution exists, there might be a whole region of solutions (for example three lines might describe a triangle where any point inside the triangle is a solution).
A linear constraint solver is going to give you an answer of an arbitrary point in the triangle. It is not going to give you a stream of results "1.00,5.00; 1.01,5.02; 1.02,5.04; etc." If you want that you need to perturb some of the inputs to the solver to change the output. In other words there is no built-in combinatoric enumeration order.
In contrast, a depth first solver would output exactly that, because that's how it also views the problem internally - by enumerating options. It may be sophisticated in ruling out scanning parts of the space which can't be in the solution, but it can't avoid enumerating partial solutions which are part of a full solution because that's how the algorithm works. It would be the same as an implementation leaving arbitrary rows out of a table join in SQL - the algorithm depends, for correctness and completeness, on that not being done.
(Note again the distinction between leaving out partial solutions that are part of a full solution versus leaving out searching entire regions which can be ruled out of ever being a solution. So I'm not arguing that it has to brute force solutions I'm making the more nuanced argument that the "row count" is significant in data flow within a DFS logic engine in a way that is not even a concept within a linear constraint solver's data flow. Or to put it another way, within a linear constraint solver there's only ever "one row" but it is kind of fuzzy what the values of the columns are.)
However unlike a strictly linear constraint solver minizinc also supports either-or constraints so I don't know how much that changes the above. I would be interested to find out if MiniZinc tracks the combinatorics of multiple either-or constraints in the way that a Datalog or SQL would - I suspect it instead treats them all as interchangeable and indistinguishable rather than enumerable.
Another difference between constraint solvers and DFS logic is generally you can pick an arbitrary variable in a constraint solver and change it's value an recalculate the model. In a DFS logic you generally cannot do that; at most you could (at the implementation level not the user level) unbind and rebind the most recently bound variable, or unwind the stack and recalculate from an earlier point.
The hardest part is certainly making constraints that don't have any holes in them, and then making it fast. Making the MiniZinc solver faster than a search algorithm required a bit of knowledge about how the solver works.
I can imagine there are some problems that are well suited to this, and this would be a good tool to solve them, but it's certainly not the best way to solve every problem (yet, anyway).
When I model constraint satisfaction & optimization problems, I generally try to make linear models and define them using pulp in Python. The models are built by python programs; I feel using a dedicated domain-specific language is not so useful (you need general purpose computing to define problems, for example you need to read data that is necessary to build the model).
In the latter, my biggest use was to prototype how I’d solve a problem for my sister in her job (scheduling facilities maintenance in a way that didn’t interfere with planned experiments and tests, what maintenance work could be done and when to minimize conflicts with customer schedules). It worked as an example but couldn’t handle the full factors (well, my laptop and lack of experience optimizing models) and they continued relying on (mostly) human judgement (worked out well enough).
I also used it to make a soccer schedule. It worked better than my teammates attempt at making a scheduler from scratch (building both the solver and model). There are already systems for this that the league had available, it was more a “can I do this” challenge.
More important, to me, was learning about a class of solvers and what problems they were effective at solving. Even though I have no immediate need it expanded my knowledge so I know where to start in the future rather than (foolishly) starting from scratch. Or I can point others to it. I’ve seen many devs (myself at times too) reinvent the wheel because we don’t know what options are out there. I took the course to combat that behavior in myself and to better guide colleagues, plus it was fun.
(Apologies, on mobile. I have a few more paragraphs I could write but this is not the easiest entry mechanism for that.)
OptaPlanner uses metaheuristics and construction heuristics, java objects as input & output (not just arrays of integers and floating point numbers), constraints that can call any java code, supports multithreaded incremental solving, etc. It currently has no Minizinc adaptor or JSR-331 (a similar initiative) adaptor. If there's more demand for that, it would be considered.
The heuristics can be hierarchical permitting customized implementations, see 'IndomainHierarchical' here: http://jacopguide.osolpro.com/guideJaCoP.html#x1-820001
What's interesting about JaCoP in particular is because it has derivative, and Multivariate Interval Newton Method constraints. If you can model your problem in terms of 'flow', you'll eliminate the risk of calculating beyond INT_MAX, in case that's a concern. Reference: http://jacopguide.osolpro.com/guideJaCoP.html#x1-490005
And that's just JaCoP, there are many great constraint solvers out there.