News for hackers. Stuff that matters.
Re:Solving Problems with MiniZinc by oerpli on Monday October 23, 2017 @05:41AM (#15531904)
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.

Re:Solving Problems with MiniZinc by CJefferson on Monday October 23, 2017 @06:03AM (#15531982)
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).

Re:Solving Problems with MiniZinc by vinchuco on Monday October 23, 2017 @07:30AM (#15532346)
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.

Re:Solving Problems with MiniZinc by kasbah on Monday October 23, 2017 @12:43PM (#15534526)
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/

Re:Solving Problems with MiniZinc by vinchuco on Tuesday October 24, 2017 @02:39AM (#15539683)
Thank you!
Re:Solving Problems with MiniZinc by jlgray on Monday October 23, 2017 @07:40AM (#15532387)
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.

Re:Solving Problems with MiniZinc by lambdadmitry on Tuesday October 24, 2017 @10:13AM (#15541653)
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.
Re:Solving Problems with MiniZinc by gjem97 on Monday October 23, 2017 @09:46AM (#15533097)
My understanding was that there are many solvers that you can use. Do they all backtrack?
Re:Solving Problems with MiniZinc by jsjolen on Monday October 23, 2017 @10:59AM (#15533639)
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.

Re:Solving Problems with MiniZinc by CJefferson on Monday October 23, 2017 @11:12AM (#15533752)
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.

Re:Solving Problems with MiniZinc by cmdkeen on Monday October 23, 2017 @06:53AM (#15532173)
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?
Re:Solving Problems with MiniZinc by Someone on Monday October 23, 2017 @11:52AM (#15534073)
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.
Re:Solving Problems with MiniZinc by jsjolen on Monday October 23, 2017 @11:01AM (#15533663)
Constraint programming is used.

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

Re:Solving Problems with MiniZinc by vog on Monday October 23, 2017 @05:53AM (#15531947)
How does MiniZinc compare to other modelling languages, such as Pyomo? http://www.pyomo.org/
Re:Solving Problems with MiniZinc by leethargo on Monday October 23, 2017 @06:19AM (#15532040)
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.