Whenever MiniZinc, or constraint programming, comes up, I post this link to a programming challenge a friend gave me...14 years ago. I was learning J, and the challenge was me in J, her in javascript or php (she never completed the solution). Here's the link: https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl...
And a person I didn't know posted a solution using MiniZinc. That person happens to also be on HN, so whenever constraint programming comes up, or MiniZinc, I post this story, and Hakan shows up. You around, Hakan? :-)
Here's Hakan's page on the solution: http://www.hakank.org/minizinc/einav_puzzle.mzn
MiniZinc is high-level modeling language, before using it I'd suggest taking course https://www.coursera.org/learn/discrete-optimization where you could use/create different solvers.
Only after it makes sense to take https://www.coursera.org/learn/basic-modeling and https://www.coursera.org/learn/advanced-modeling courses.
If you want a quick start read really good tutorial on official website https://www.minizinc.org/doc-2.7.2/en/part_2_tutorial.html and play with examples at online playground https://play.disopt.com/ or locally installing MiniZincIDE.
I used MiniZinc extensively in my previous position, and have mixed feelings about it. As is stated in other comments, it works very well for specific small problems, but when the model gets complex it can become unwieldy.
We used it to create models of networked biological systems (e.g. the immune system, gene regulatory networks, etc.). The network topology was constructed from mined academic literature and then the model was constrained using data. The great thing about using MiniZinc was that it could propose multiple models with the same or similar “accuracy” to the data. You would then have an ensemble of models from which to make predictions (i.e. how does a drug affect the system).
We would have MiniZinc files that were 10s or 100s of MBs and would run for days. Sometimes they would be unsatisfiable within a few seconds, other times within hours. Many of the solvers are single threaded, and those that are multithreaded don’t seem to be much more efficient with more cores.
MiniZinc is very difficult to debug and the paradigm shift can be jarring coming from procedural languages. However, I am grateful it exists and for the work that many have put into it. Similar to the train yard comment, we used Python to construct the MiniZinc models and then submitted them to the solvers via the minizinc-python package which is well written and meek maintained.
As a not professional programmer, but mathematically inclined I can say I found modelling in MiniZinc crazily hard. I tried the Coursera class, put in the hours and failed. It took me back to some classes where everything I tried failed and the proper result felt so near what I was trying that it was hard to digest a better strategy the next time. It did give me a new feeling for complexity and model space reduction. Somewhere MiniZinc and other engines are super efficient, you just need to put the problem in the right form (and therein lies the catch).
I used Minizinc to come up with tiling patterns for a patio. I had m 2x2 tiles and n 3x2 tiles and wrote a model to generate patterns that had:
* a certain aspect ratio,
* rotational symmetry,
* no spots where four corners touch,
and a few other ad-hoc constraints that I can't remember exactly, to exclude certain sub-patterns.
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.
Related:
Constraint Solving with MiniZinc - https://news.ycombinator.com/item?id=18161145 - Oct 2018 (38 comments)
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)
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 code would be easier.
The Google OR-Tools Python API also might be easier if you're generating models dynamically. I wouldn't want to generate MiniZinc code...
Im sure this is useful but these languages (proof langs, constraints, etc) are always so difficult to parse or read
Adoption for these systems might be higher if they had a more readable syntax (and bonus if they could transpile down to source code you can tweak)
Also maybe I missed it on mobile, but I would love examples of the syntax and examples of application usage on the first page. Maybe this is useful to me! Who knows? That information should be easy to find
My goodness, a HN topic I can speak on with some level of expertise!
I developed and deployed a rail yard scheduling application based on MiniZinc which is being used daily in production at several sites by one of the largest rail network operators in Australia.
Like others here I had started out with the free coursera courses a couple of years prior and was really taken by the declarative nature of the language. When approached about the yard scheduling problem I thought it seemed like a good fit and was able to quickly generate a proof of concept. I spent the next 2 years iterating on it until it was able to handle all of the real world (and real-time) constraints.
The topology: - A yard has many tracks (~40 in our largest case) - A track has many track circuits (this reflects the underyling control system) - ~ 250 track circuits - A circuit can only be occupied by 1 train at a time - A train occupies many track circuits - This yard was a staging point for 2 unloading locations - Each unloading location had many loaders
The dynamics: - Trains entered the yard primarily for the purpose of proceeding to the unload and unloading - Most trains required 'provisioning' on certain tracks before or after unloading - Some trains required' shunting', making or breaking a consist into separate peices for repair or reconfiguration - Some trains required manual examination, meaning adjacent tracks must be vacant while the inspection took place - There are many routes trains can take (we pre-calculated these) - There were multiple train operators using the yard - Each operator had soft or hard constraints on where and how they would like their trains to operate - The primary objective function was meeting the agreed unloading time at the port and completing all maintenance and inspections - Secondary objectives were queuing times, route preferences
The implementation: - ~50k python codebase - Data read from 4 internal systems for maintenance requirements, schedules, etc - Telemetry from the train control system used to determine train location within the yard - Data was stored in python using attrs, cattrs and roundtripped to JSON - MiniZinc models were compiled on demand, this was a massive help in performance and flexibility - Frontend was a Streamlit app which displayed schedules using Altair/Vega-lite - The core 'solve' method was used in a variety of ways, you could reschedule a single trains, or many trains at once (the ideal), or a heuristic where trains were scheduled in dynamic batches (required for longer +24hr runs) - The frontend exposed a '1 click schedulers' which would bring in all the data and produce a feasible schedule very quickly (<1min) with a heuristic - Once the business was confident in the tool we had it running inside a container on an hourly basis to continually produce optimal schedules based on the latest available data which was the advertised to operators - Used Google OR-Tools as the backend solver which was by far the fastest - Trains were scheduled using 1minute time blocks
Reflection: This was an extremely challenging project for a lot of reasons, mainly because I was a 1 man team and trying to learn on a deadline, also this was during covid and I had nothing else to do so it became quite all consuming. I have since thought that if I could do it all again would the approach be different?
Of all the parts of the tech stack I enjoyed MiniZinc the most and would happily use it again. Modelling with constraints is not easy but there is a rock solid gaurantee that comes with it that pleases me greatly. As other people have said there is a lack of intermediate or advanced level "real world" tutorials which I completely agree with and am working on in my spare time.
I would say that things got a lot easier once I stopped trying to represent the entire model ahead of time in one minizinc file, and instead compiled models as required from the python side based on the data I was dealing with.
Python was great for the POC stage and horrendous once it got to a certain size. Alas a rewrite was never in the cards. We dealt with it by using type hints everywhere
Streamlit is absolutely not fit for purpose for anything beyond hello-world, at least at the time I was using it. Unfortunately I had no experience in frontends at all and just needed a way to expose the model to end users and display results so we made it work.
Altair/Vega-lite is a fantastic charting library which I would readily use again. Being able to produce standalone gantt-style train schedules complete with interaction was a major win for both end users and myself for debugging.
I have to duck off but love talking about this stuff, you can reach me at "justin dot rawlings at protonmail dot com" or jmjrawlings on github.
These things look neat! I can tell, being in the engineering industry for 20+ years that there's a lot of excitement and progress happening.
One thing I really wish there was more of though, was motivating examples that make sense in my world.
The comment "I used minizinc to try and generate levels for my puzzle game by encoding the rules." is a decent example.
I'll believe that sat-solvers are getting better and should be used more, but I feel there's a real dearth of motivating examples for those of us who live, eat, breathe and have no problem with the C/C++/systems engineering/high performance stuff. :)
edit:
Basically, I want a few dozen well written examples of things like (starting from "Solving Sudoku with SAT"):
https://codingnest.com/modern-sat-solvers-fast-neat-underuse...
It seems a significant amount of cleverness is required to model rules as the equations, before passing them off to the solver.
Constraint modelling is really neat. It only works well on a specific category of problems, but when it works it can feel almost like cheating. You don't actually do anything, you just restate the problem in code and the computer does the work for you.
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 :) )
How does this kind of constraint modeling compare with logic based approaches like Answer Set Programming (https://potassco.org)? Years ago, I got excited by the possibilities of ASP but it does not seem to have progressed much
Constraint programming with MiniZinc is great for some problems. There is a good Coursera class on MiniZinc. I also had a simple Python+MiniZinc example in my last Python book.
This is how you write a proper title: https://news.ycombinator.com/item?id=16194112
What exactly is "constraint modeling" and what is it used for?
Anything new here?
You forgot to tell us what it is.
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 degree where it's even remotely usable to solve real problems.
It's a really interesting tool, but one of the reasons we thought it might be useful for this problem is so that non-technical people could easily change the constraints and play with the costs for different operations. I don't think it's particularly good for that, at least in this problem domain.