Hacker News Comments on
The University of Melbourne
Basic Modeling for Discrete Optimization
Hacker News Stories and CommentsAll the comments and stories posted to Hacker News that reference this url.
As others have said, using a combinatorial solver like Z3 (SMT solver) or MiniZinc (which is a modelling language and can interface to different types of solvers, including several constraint programming and mixed integer programming solvers, can be driven via minizicn-python) is probably the way to go. CPMpy is a new Python modelling framework that might also be of interest that interfaces to different solvers
If you have a lot of constraints that are on the bit representation, then it is more likely that an SMT solver is a better solution. If on the other hand more of your constraints are arithmetic and perhaps some structural constraints, then it might be interesting to look into other types of solvers. It all depends on the specifics of your problem instances.
There are a couple of Coursera courses for modelling with MiniZinc that are quite nice (https://www.coursera.org/learn/basic-modeling is the first one) that are useful if you want to learn more about how to think when doing combinatorial modelling. These are usefule even if you end up using some other tool or technology, as the mindset is similar.
There are a couple of very good coursera courses on modeling with MiniZinc, the first one being https://www.coursera.org/learn/basic-modeling
⬐ tra3Signed up. Much appreciated.
I am taking the Modelling series(https://www.coursera.org/learn/basic-modeling) and Discrete optimization(https://www.coursera.org/learn/discrete-optimization). Great way to get your feet wet in the world of NP-hard problems.
⬐ dowakinDiscrete optimization is the best course for me. It's really challenging one. I spend about a month for getting A score for all tasks - but it's rewarding experience.
I miss professor Pascal. I hope he will create a second course!⬐ hgouryI took watched some of the lectures and did a few exercises when I had a similar course at University, it was great indeed.
I'm glad to see the domain of constraint programming and operational research in general generate interest so I thought I would take the opportunity to share some links and resources I have found useful. Personally, I've spent most of my time on the routing (TSP, VRP, VRPTW) side of things using CP (OscaR-CP).
Discrete optimization and constraint programming can be a bit difficult to get into. There are two great free online courses on Coursera that do a good job at introducing the topic.
I don't remember the exact content of this course but I believe it covers the basics in a few different methodologies.
Basic Modeling for Discrete Optimization
This is a great course by Peter Stuckey that uses MiniZinc. The MiniZinc programming language is a great starting point that teaches you to think of solving discrete optimization problems only in terms of modelling the problem.
Håkan Kjellerstrands blog is another great resource
It contains hundreds of different models for a large variety of different solvers. Chances are that he has created a model for your solver for a similar problem.
Two books worth mentioning are:
Handbook of Constraint Programming
Principles of Constraint Programming
The OscaR library
My personal favorite. An OR framework written entirely in Scala. As such it's an absolute joy to work with and the internals are (relatively speaking) easier to understand.
Another extremely potent solver. Exclusively CP based.
An extremly lightweight CP solver, designed for educational purposed to expose how a CP solver works without obfuscating performance optimizations found in research/production solvers.
A solver agnostic constraint modelling languages, designed to interface a given optimization model with different solvers.
A few notable researches:
Pascal Van Hentenryck
Laurent Perron - OR-tools
Peter Stuckey - MiniZinc
Pierre Schaus - OscaR, Mini-CP
Renaud Hartert - OscaR
I also want to make a plug for the work of the Uppsala University optimization group
Especially the work of Pierre Flener, Gustav Björdal and Justin Pearson who I've had the pleasure to work with during my masters thesis on vehicle routing using CP.
There's a good MOOC on Coursera on applied discrete optimization that uses MiniZinc: https://www.coursera.org/learn/basic-modeling