#36 overallEvergreen
Discrete Optimization
Coursera
12 recommenders · 12 threads · recommended in 7 years, 2014–2023 · score 15.0
Coursera MOOC on discrete optimization taught by Pascal Van Hentenryck, covering constraint programming, mixed integer programming, local search and related techniques, with problem sets solved in any programming language.
Commenters call it an engaging, problem-driven introduction to discrete optimization with an enthusiastic instructor and a clear practical focus.
Algorithms & Data Structuresintermediatefreeinteractive MOOC#discrete optimization#constraint programming#mixed integer programming#local search#van hentenryck
Recommendations by year
20062026
If anyone is interested in learning more about MIP and other discrete optimization topics, there is a great MOOC on coursera (link: https://www.coursera.org/learn/discrete-optimization/). Lectures are quite engaging, delivered by enthusiastic and a bit eccentric prof. Van Hentenryck. Also there are no stupid quizzes, just 5 problems (with 6-8 instances each, ranging from comparatively small to huge) that you need to solve (in any programming language) in order to pass. The only drawback is significant investment of time it requires.
Also, you can learn fundamental, intermediate and even advanced topics on CS without a formal degree via MOOCs, like the ones offered by Coursera - some of them taught by professors from universities that you may not even have the money/time/grades to get in for a formal degree.
I was thinking about attending to a CS undergrad course some time ago, but since I'm full-time employed at a very big ("unicorn") startup - an opportunity too good to be wasted -, I opted to take some classes on advanced topics such as Discrete Optimization and Automata theory on Coursera . It has been the best use of my spare time ever.
I really enjoyed Discrete Optimization, Pascal Van Hentenryck, Coursera. [1] I did it in 2013 and it looks like it's changed a little: vehicle routing seems a good, practical topic right now. Optimizing systems is one of my favorite pleasures, so this course was great for me.
[1] https://www.coursera.org/learn/discrete-optimization
Three Coursera MOOCs I particularly enjoyed:
* Discrete Optimization: almost entirely problem-driven, very challenging and entertaining prof; https://www.coursera.org/learn/discrete-optimization
* Crypto I: very deep, thorough and crystal clear explanations; https://www.coursera.org/learn/crypto
* Computer Networks: excellent overall course covering a wide variety of topics; https://www.coursera.org/instructor/~517478, https://www.youtube.com/playlist?list=PLfgkuLYEOvGMWvHRgFAcj...
I took the second edition of Grossman's course and it was very good. Kickzales's Introduction to Program Design was also good as was Pascal Van Hentenryck's Discrete Optimization - his enthusiasm is infectious.
Odersky himself is teaching Functional Programming in Scala later this month, and I'm looking forward to that.
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.
SICP contains a chapter on non-deterministic programming that’s similar to how Prolog executes: https://mitp-content-server.mit.edu/books/content/sectbyfn/b...
There’s also a chapter on logic programming but it doesn’t quite work the same way as Prolog: https://mitp-content-server.mit.edu/books/content/sectbyfn/b...
Peter Norvig has a couple of chapters (11,12) on how to implement Prolog in his book PAIP. He also has a chapter (17) on constraint satisfaction but IIRC it’s not integrated into his Prolog system: https://github.com/norvig/paip-lisp
Many real Prolog implementations are based on the WAM. For an excellent introduction to the WAM look at: http://wambook.sourceforge.net/
I don’t have books or papers on implementing constraints and how to integrate them with Prolog. But here are two great classes on Coursera that explain how constraints and constraint propagation work. You can audit them for free:
Discrete Optimization by Hentenryck https://www.coursera.org/learn/discrete-optimization
Solving Algorithms for Discrete Optimization by Lee and Stuckey https://www.coursera.org/learn/solving-algorithms-discrete-o...
I believe constraints are typically integrated into Prolog through attributed variables: https://www.metalevel.at/prolog/attributedvariables
But I don’t really know how that works. Markus Triska has a few papers on constraint solvers for SWI Prolog on his webpage. He can probably give you more and better pointers: https://www.metalevel.at/
I've completed and can recommend all of these if the topics are of interest to you:
https://www.coursera.org/learn/basic-modeling
https://www.coursera.org/specializations/algorithms
https://www.coursera.org/learn/discrete-optimization
https://www.coursera.org/learn/programming-languages
I'm still working my way through this one but it's been good so far:
https://www.coursera.org/specializations/data-structures-alg...
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.
Discrete Optimization
https://www.coursera.org/learn/discrete-optimization
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
https://www.coursera.org/learn/basic-modeling
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
http://www.hakank.org/
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
Other solvers/frameworks:
The OscaR library
https://bitbucket.org/oscarlib/oscar/wiki/Home
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.
GeCode
https://www.gecode.org/
Another extremely potent solver. Exclusively CP based.
Mini-CP
https://minicp.readthedocs.io/en/latest/
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.
MiniZinc
https://www.minizinc.org/
A solver agnostic constraint modelling languages, designed to interface a given optimization model with different solvers.
A few notable researches:
Phil Kilby
Pascal Van Hentenryck
Paul Shaw
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
http://www.it.uu.se/research/group/optimisation/
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.
Take a course on discrete optimization. There's one on Coursera.
Convex optimization is also useful if you care about optimizing convex functions. Which I bet you do.
i still have a copy of Fraleigh -- a first course in abstract algebra. not sure if it is the best, but it did the job.
I really enjoyed the two real analysis & functional analysis courses when i attended university, but alas, the reading material for these courses were notes produced by each lecturer, they're not available as published books.
i recall covering the material for "cup = donut" style results in an algebraic topology course, i think in 3rd or 4th year, after first being drilled with 2-3 years of pure math including real analysis, including lots of basic stuff about topological spaces, continuous and smooth functions, measure theory, some abstract algebra, etc.
3). Probability 4). Statistics
MacKay's "Information Theory, Inference, and Learning Algorithms" is a great read: http://www.inference.org.uk/itila/book.html
5). Optimization
Sign up for this course: https://www.coursera.org/learn/discrete-optimization
edit:
you didn't mention PDE, but i still have a copy of Evans -- partial differential equations serving as a monitor stand. you probably want to have 3 years of pure math including linear algebra, lots of real analysis & some differential equations under your belt first.
Maybe of interest - postgres planner documentation
https://www.postgresql.org/docs/current/planner-optimizer.ht...
Genetic query optimiser: https://www.postgresql.org/docs/current/geqo.html
postgres has a number of hooks, which can be used to override the default behaviour. In particular, there are a bunch of hooks that can be used to install a custom query planner. https://github.com/AmatanHead/psql-hooks/blob/master/Readme....
more generally, ignoring database query optimisation specifically, if you are interested in learning about discrete optimisation techniques, I recommend this course: https://www.coursera.org/learn/discrete-optimization
Coursera has a great course on discrete optimization [1] where I have learned and used or-tools. They are rather nice, but the documentation is half done (basically code is the best documentation) and some interfaces are not compatible with others. I ended up forking or-tools for my own use and tweaking many unexposed internals. I guess it's extremely difficult to implement generic optimization solver, so I won't complain, but be prepared it's not out-of-the-box thing (I doubt there is any).
[1] https://www.coursera.org/course/optimization
Interesting. I don't think that would be my first choices of study.
If you want to know more about how constraint programming works under the hood, I can recommend the coursera course Solving algorithms for Discrete Optimization, in particular weeks 1 and 2 for constraint programming. https://www.coursera.org/learn/solving-algorithms-discrete-o...
I'm a Ph.D. student in operations research (OR). My suggestion would be to first build a strong foundation in linear programming. This will introduce you to the notion of duality, which is heavily emphasized in many mathematical programming courses. Here's a good open source book on linear programming written by Jon Lee, the current editor of Mathematical Programming A: https://github.com/jon77lee/JLee_LinearOptimizationBook
Then I'd suggest studying more general methods for continuous and convex optimization. The book I see mentioned a lot is Convex Optimization by Boyd and Vandenberghe, although we didn't use this in our coursework. Instead, we used a lot of the material presented here: http://mitmgmtfaculty.mit.edu/rfreund/educationalactivities/
If you read the above (or any other two books on linear programming and convex optimization), you'll probably have a better idea of what you want to study next and how you want to go about it. The next natural step would be to study combinatorial (i.e., integer or mixed-integer) optimization. (Jon Lee has another book on this subject; I've also heard good things about the Schrijver book.)
It's also not a bad idea to start getting familiar with the tools people use to solve mathematical programs in practice. The theory you'll learn to solve linear programs is different from the theory for general convex problems, and similarly for mixed-integer programs. As such, there are various "solvers" that are used to solve various problem types. Because of this, there are a lot of frameworks that are used to develop general mathematical programs, which can then interface with these solvers in a generic way. For example, Pyomo is a modeling language based in Python, and JuMP is a modeling language based in Julia.
If you want a general introduction to discrete optimization in a course format, you should take this class on Coursera (https://www.coursera.org/learn/discrete-optimization). It's a fantastic introduction to operations research in general, and it will give you a good intuition of the types of problems you encounter in the field as well as the various techniques that are used to solve them. (Full disclosure: Pascal is my adviser.)
Let me know if you have any more questions. I recently became a moderator of /r/OperationsResearch on Reddit and love the idea of having a larger community that can answer questions like yours. Operations research seems somewhat overshadowed by machine learning at the moment (at least in popular culture), but they truly go hand-in-hand. I'm somewhat surprised that a lot of useful techniques from OR are not heavily discussed by machine learning practitioners. Both fields are, fundamentally, trying to solve difficult optimization problems.
You can take a look at Discrete Optimization course on Coursera: https://www.coursera.org/course/optimization
The next session will start March 4th 2014.