MiniZinc: free and open-source constraint modeling language • Hacker News Board

Re: MiniZinc: free and open-source constraint modeling language

#31

Post by afpx » Sun, Jan 21, 2018, 1:07 PM UTC

sevensor wrote: post #21

jsjolen wrote: post #20

A constraint solver typically works by: 1. Having a finite set of variables with a finite set of possible values 2. Having a finite set of propagators which are monotonic on variables (that is, it either reduces the amount of possible values for a variable or does not (it never adds). 3. A space describing a full set of variables and propagators 4. A way of reducing the amount of values when all propagators have hit…

So what differentiates the solvers then? Is it in how they apply the propagators? I'm interested because I naively wrote the exact loop you just posted, trying to solve a very hard problem. I spent ages trying different heuristics, but I knew I was floundering. Then I discovered Z3, which solves the problem in a tiny fraction of the time. It seems like pure magic, and I'm keen to understand how it works.

I haven’t used all the different solver engines, and I haven’t kept up with the field, but many years ago I had a license to IBM ILOG CPLEX, and it was interesting how much faster it was than some others. Gurobi is also very fast (I think they were started by the people who sold ILOG CPLEX to IBM), but haven’t benchmarked it vs CPLEX.

Re: MiniZinc: free and open-source constraint modeling language

#32

Post by verifex » Sun, Jan 21, 2018, 2:02 PM UTC

I've never heard of constraint programming languages before, and I kind of wish I had, because I recently had a problem where I needed to sequence a bunch of elements based on a lot of arbitrary rules. Sequencing based on one rule was easy, but applying all simultaneously was a huge PITA, and resulted in much headaches; this tool looks like it could have solved the problem quickly. Definitely putting this in my bookmark tool-set for future use.

Re: MiniZinc: free and open-source constraint modeling language

#33

Post by jahewson » Sun, Jan 21, 2018, 5:35 PM UTC

crimsonalucard wrote: post #28

jahewson wrote: post #26

Earlier quoted context omitted.

“Constraint Programming” refers, for the most part, to the solving of finite-domain problems via backtracking and constraint propagation and is typically concerned with performing a complete, global search of the solution space. https://en.m.wikipedia.org/wiki/Constraint_satisfaction

I like this answer. However, by solution space do you mean domain space?

Yes, sorry, the search space.

Re: MiniZinc: free and open-source constraint modeling language

#34

Post by sevensor » Sun, Jan 21, 2018, 8:25 PM UTC

afpx wrote: post #31

sevensor wrote: post #21

Earlier quoted context omitted.

So what differentiates the solvers then? Is it in how they apply the propagators? I'm interested because I naively wrote the exact loop you just posted, trying to solve a very hard problem. I spent ages trying different heuristics, but I knew I was floundering. Then I discovered Z3, which solves the problem in a tiny fraction of the time. It seems like pure magic, and I'm keen to understand how it works.

I haven’t used all the different solver engines, and I haven’t kept up with the field, but many years ago I had a license to IBM ILOG CPLEX, and it was interesting how much faster it was than some others. Gurobi is also very fast (I think they were started by the people who sold ILOG CPLEX to IBM), but haven’t benchmarked it vs CPLEX.

So I haven't looked deeply into the capabilities of Gurobi and CPLEX, but I was under the impression that they focus on integer linear programming. How do they do with problems for which finding a feasible solution is very difficult?