Solving Problems with MiniZinc

http://blog.jpalardy.com/posts/problem-solving-with-minizinc/

by vinchuco • 9 years ago

56 15 9 years ago

blog.jpalardy.com

oerpli• 9 years ago

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.

CJefferson2• 9 years ago

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).

vinchuco2• 9 years ago

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.

vog• 9 years ago

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

leethargo• 9 years ago

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.

cmdkeen• 9 years ago

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?

jsjolen2• 9 years ago

Constraint programming is used.

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

Someone• 9 years ago

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.

jlgray• 9 years ago

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.

gjem97• 9 years ago

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

jsjolen2• 9 years ago

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.

CJefferson2• 9 years ago

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.

lambdadmitry• 9 years ago

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.

kasbah• 9 years ago

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/

vinchuco2• 9 years ago

Thank you!

Solving Problems with MiniZinc

Related Stories