Solving Problems with MiniZinc | Hacker News Reader

Solving Problems with MiniZinc

blog.jpalardy.com

56 pointsvinchuco15 comments

I attended a similar course and talked with other students about their solutions and what difficulties they encountered.

From what I've seen I had the impression that MiniZinc had some problems, i.e. it has some unexpected behavior, such as: - reordering constraints changes performance - reordering constraints may change results/feasibility of a problem

For quick prototyping it was nice though.

Reordering constraints changing performance is basically impossible to avoid for constraint systems, because we are very bad at predicting which constraints should be considered first -- well, you can always apply some normalisation pass which at least hides the problem from users.

Reording causing changes in feasibility of a problem is a MAJOR bug, and I hoped they reported it. The constraint system I work on (Minion and Essence', a competitor to MiniZinc), has (AFAIK) never had such a bug in any release (they come up occasionally during development, but we have serious tests specially designed to detect that kind of problem).

For constraints x>=0 and x=0, switch the order for a performance improvement. This shows solvers have preferences. MZ chooses the solver based on reasons.

MZ seems to work beautifully for simple/modular examples. A professor suggested this one instead (for performance, popularity): http://eclipseclp.org but I can't yet assert if they are comparable or if the statement is accurate.

Another great resource for learning constraint programming is CS294 "Programming Synthesis for Everyone" [1]. It focuses on using Racket and Rosette [2] to synthesize programs.

[1]: https://homes.cs.washington.edu/~bodik/ucb/cs294fa12.html

[2]: https://emina.github.io/rosette/

Thank you!

I used MiniZinc on the capacitated vehicle routing problem in a combinatorial optimization project course a couple of years ago, and really enjoyed it.

The sweet spot for MiniZinc is in investigating a problem and prototyping a solution. I would say it takes 10-20 hours to get a workable understanding of the language and paradigm, plus or minus your previous experience.

However, MiniZinc is built on backtracking, which scales poorly to real world instances of np-hard problems.

My understanding was that there are many solvers that you can use. Do they all backtrack?

The goal of a constraint solver is to bind (constrain) all of the defined variables to a single value which satisfies the constraints put upon that variable.

This is in essence traversing through a search tree (through DFS) and finding a valid end-node.

This means that when we find an invalid end-node (for example by running out of possible values for a variable) then we must in some way go back up the search tree.

There are several different ways of doing this.

Short answer: Yes, we must backtrack somehow.

In some vague sense, any solver for an NP-complete problem, must either backtrack, or keep accumulating information and possibly exhaust memory. In practice every practical solver I know of for NP-complete problems backtracks.

Now, they often do all kinds of other clever things on top (learning, restarts, parallelisation, heuristics), but when the going gets tough, there is a lot of backtracking.

You can always use MiniZinc (or any other CP solver) to make a "large neighborhood search" where you do local optimization over subproblems, feeding subproblems into the constraint solver. As far as I know, this is one of the most successful approaches for big problems.

Constraint programming is a fascinating area that I loved at university. There have been a few times where I've thought it would be a useful way to solve a problem since, but brute force always won through. Is anyone out there using it in anger? If so, in what sort of spaces / companies?

Constraint programming is used.

One (very cool) instance of constraint programming occurs at Ericsson through the Unison project http://unison-code.github.io/ .

Autolayout in iOS and Mac OS (https://developer.apple.com/library/content/documentation/Us...) uses the Cassowary constraint solver (https://en.wikipedia.org/wiki/Cassowary_(software) ) to layout GUI elements.

How does MiniZinc compare to other modelling languages, such as Pyomo? http://www.pyomo.org/

MiniZinc is a language for "constraint programming" with a focus on discrete decision problems, and supporting many "global constraints", such as "alldifferent".

Pyomo uses "algebraic notation" for so-called mathematical programming models. This starts out with continuous variables and linear constraints ("linear programming"), but nonlinear constraints and discrete variables are also supported.

Of course, there is a lot of overlap in functionality. Sorry for the specific vocab.

Reply on news.ycombinator.com