4 ms·

Solving Problems with MiniZinc

56 points by vinchuco 9y ago

oerpli 9y 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.
- CJefferson 9y 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).
- vinchuco 9y 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 http://eclipseclp.org but I can't yet assert if they are comparable or if the statement is accurate.
vog 9y ago
How does MiniZinc compare to other modelling languages, such as Pyomo? http://www.pyomo.org/ http://www.pyomo.org/
- leethargo 9y 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 9y 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?
- jsjolen 9y ago
  Constraint programming is used. One (very cool) instance of constraint programming occurs at Ericsson through the Unison project http://unison-code.github.io/ http://unison-code.github.io/ .
- Someone 9y ago
  Autolayout in iOS and Mac OS (https://developer.apple.com/library/content/documentation/UserExperience/Conceptual/AutolayoutPG/index.html https://developer.apple.com/library/content/documentation/Us...) uses the Cassowary constraint solver (https://en.wikipedia.org/wiki/Cassowary_(software) https://en.wikipedia.org/wiki/Cassowary_(software) ) to layout GUI elements.
jlgray 9y 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 9y ago
  My understanding was that there are many solvers that you can use. Do they all backtrack?
  - jsjolen 9y 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.
  - CJefferson 9y 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 9y 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 9y 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 https://homes.cs.washington.edu/~bodik/ucb/cs294fa12.html [2]: https://emina.github.io/rosette/ https://emina.github.io/rosette/
- vinchuco 9y ago
  Thank you!

56 points by vinchuco 9y 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.

CJefferson 9y 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).
vinchuco 9y 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 http://eclipseclp.org but I can't yet assert if they are comparable or if the statement is accurate.

vog 9y ago

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

leethargo 9y 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 9y 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?

jsjolen 9y ago
Constraint programming is used. One (very cool) instance of constraint programming occurs at Ericsson through the Unison project http://unison-code.github.io/ http://unison-code.github.io/ .
Someone 9y ago
Autolayout in iOS and Mac OS (https://developer.apple.com/library/content/documentation/UserExperience/Conceptual/AutolayoutPG/index.html https://developer.apple.com/library/content/documentation/Us...) uses the Cassowary constraint solver (https://en.wikipedia.org/wiki/Cassowary_(software) https://en.wikipedia.org/wiki/Cassowary_(software) ) to layout GUI elements.

jlgray 9y 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 9y ago
My understanding was that there are many solvers that you can use. Do they all backtrack?
- jsjolen 9y 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.
- CJefferson 9y 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 9y 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 9y 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 https://homes.cs.washington.edu/~bodik/ucb/cs294fa12.html [2]: https://emina.github.io/rosette/ https://emina.github.io/rosette/

vinchuco 9y ago
Thank you!