MiniZinc • Hacker News Board

Re: MiniZinc

#21

Post by 0cf8612b2e1e » Fri, Jul 21, 2023, 8:36 PM UTC

aidos wrote: post #14

jpnelson wrote: post #10

I wrote a thesis on using constraint satisfaction with minizinc to solve the genome edit distance problem: https://github.com/jpnelson/genome-edit/blob/master/thesis.p... My takeaway: modeling problems in minizinc correctly is exceptionally difficult for non-trivial problems. You can model it correctly, but you'll likely still need to add additional "constraints" that improve the performance of the solver to the degr…

Is that a minizinc thing or a solver thing in general?

I have only ever used Z3, but you might be onto something. Modeling problems is really challenging. It does not help that if you search for documentation or guidance there one two types of resources: beginner Sudoku or primary literature academic papers discussing the minutia of optimization properties with so much jargon.

Re: MiniZinc

#22

Post by xtagon » Fri, Jul 21, 2023, 8:39 PM UTC

ShadowBanThis01 wrote: post #16

You forgot to tell us what it is.

The first two paragraphs of the home page say what it is:

MiniZinc is a free and open-source constraint modeling language.

You can use MiniZinc to model constraint satisfaction and optimization problems in a high-level, solver-independent way, taking advantage of a large library of pre-defined constraints. Your model is then compiled into FlatZinc, a solver input language that is understood by a wide range of solvers.

Re: MiniZinc

#23

Post by mattnewport » Fri, Jul 21, 2023, 8:41 PM UTC

I can recommend this course and its sequels on Coursera to anyone interested in learning MiniZinc: https://www.coursera.org/learn/basic-modeling

I enjoyed the courses and learning the techniques through the exercises but I still haven't really found a good application to a problem I need to solve for work or side projects.

Re: MiniZinc

#24

Post by zellyn » Fri, Jul 21, 2023, 8:43 PM UTC

jpnelson wrote: post #10

I wrote a thesis on using constraint satisfaction with minizinc to solve the genome edit distance problem: https://github.com/jpnelson/genome-edit/blob/master/thesis.p... My takeaway: modeling problems in minizinc correctly is exceptionally difficult for non-trivial problems. You can model it correctly, but you'll likely still need to add additional "constraints" that improve the performance of the solver to the degr…

Do I understand correctly that this kind of constraint satisfaction is more complex than just turning things into a bunch of SAT clauses? Otherwise (and admittedly without a deep understanding of genomics or solvers), I would be surprised if constraint satisfaction were the best approach for edit distance…

Once you added domain-specific performance-oriented constraints, did you find this to be a useful and viable approach to the problem?

Re: MiniZinc

#25

Post by wsdookadr » Fri, Jul 21, 2023, 8:45 PM UTC

TimTheTinker wrote: post #20

I once tried to use MiniZinc as a back-end for a school timetabling app I was working on, and came away with the impression that the OptaPlanner Java API would be a lot easier to use. (Although unlike solvers, OptaPlanner uses heuristic algorithms -- simulated annealing, etc.) Maybe it's just that formally expressing a set of constraints doesn't come naturally to me. I'm sure with a lot of practice, writing MiniZinc…

That an algorithm is heuristic does not preclude it from being provably correct. It precludes it from being optimal!

The goal of an heuristic algorithm is to produce a near-optimal or approximate solution in a reasonable amount of time. From here, some heuristics have more or less theory behind them and that theory shows what sort of properties the solution has.

[1] https://optimization.cbe.cornell.edu/index.php?title=Heurist...

[2] https://en.wikipedia.org/wiki/Heuristic_(computer_science)

Re: MiniZinc

#26

Post by sirwhinesalot » Fri, Jul 21, 2023, 8:48 PM UTC

zellyn wrote: post #24

jpnelson wrote: post #10

I wrote a thesis on using constraint satisfaction with minizinc to solve the genome edit distance problem: https://github.com/jpnelson/genome-edit/blob/master/thesis.p... My takeaway: modeling problems in minizinc correctly is exceptionally difficult for non-trivial problems. You can model it correctly, but you'll likely still need to add additional "constraints" that improve the performance of the solver to the degr…

Do I understand correctly that this kind of constraint satisfaction is more complex than just turning things into a bunch of SAT clauses? Otherwise (and admittedly without a deep understanding of genomics or solvers), I would be surprised if constraint satisfaction were the best approach for edit distance… Once you added domain-specific performance-oriented constraints, did you find this to be a useful and viable app…

MiniZinc is just a modeling language, you can throw the problem at different solvers. You can use SAT solvers (assuming you have some wrapper that translates FlatZinc to CNF), CP solvers (can be SAT-based underneath or use different algorithms like MAC), SMT solvers (SAT Modulo Theories like Arithmetic), MIP solvers (usually Simplex + Branch & Bound)...

Re: MiniZinc

#27

Post by WJW » Fri, Jul 21, 2023, 9:08 PM UTC

ShadowBanThis01 wrote: post #16

You forgot to tell us what it is.

You forgot to look up the trivially googleable term (or to read TFA) before deciding to post.

Re: MiniZinc

#28

Post by dang » Fri, Jul 21, 2023, 9:56 PM UTC

MiniZinc: free and open-source constraint modeling language - https://news.ycombinator.com/item?id=16194112 - Jan 2018 (33 comments)

Solving Problems with MiniZinc - https://news.ycombinator.com/item?id=15530630 - Oct 2017 (15 comments)

Problem Solving with MiniZinc - https://news.ycombinator.com/item?id=14062281 - April 2017 (1 comment)

Clojure to MiniZinc - https://news.ycombinator.com/item?id=10042958 - Aug 2015 (4 comments)

Constraint programming and The MiniZinc Challenge (2013) - https://news.ycombinator.com/item?id=7863946 - June 2014 (1 comment)

Re: MiniZinc

#29

Post by surfsvammel » Fri, Jul 21, 2023, 10:08 PM UTC

Forgive my ignorance, but what kinds of problems are constraint solving good for?

Can I specify a list of statements, constraints, prioritisations and the have it solve it for the best possible solution? Is that it? If so, I need it to figure out my optimal workout schedule given a handful of constraints (a problem I’ve been thinking about since I started university twenty years ago :) )

Re: MiniZinc

#30

Post by nextaccountic » Fri, Jul 21, 2023, 10:14 PM UTC

surfsvammel wrote: post #29

Forgive my ignorance, but what kinds of problems are constraint solving good for? Can I specify a list of statements, constraints, prioritisations and the have it solve it for the best possible solution? Is that it? If so, I need it to figure out my optimal workout schedule given a handful of constraints (a problem I’ve been thinking about since I started university twenty years ago :) )

GUI layout can be done by solving constraints, like in Cassowary, which is used in iOS and has implementations in many languages

> Can I specify a list of statements, constraints, prioritisations and the have it solve it for the best possible solution? Is that it? If so, I need it to figure out my optimal workout schedule given a handful of constraints (a problem I’ve been thinking about since I started university twenty years ago :) )

Yes!