HN Academy

The best online courses of Hacker News.

Hacker News Comments on
Discrete Optimization

Coursera · The University of Melbourne · 18 HN comments

HN Academy has aggregated all Hacker News stories and comments that mention Coursera's "Discrete Optimization" from The University of Melbourne.
Course Description

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming.

Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals.

This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

HN Academy Rankings
  • Ranked #6 this year (2024) · view
Provider Info
This course is offered by The University of Melbourne on the Coursera platform.
HN Academy may receive a referral commission when you make purchases on sites after clicking through links on this page. Most courses are available for free with the option to purchase a completion certificate.
See also: all Reddit discussions that mention this course at reddsera.com.

Hacker News Stories and Comments

All the comments and stories posted to Hacker News that reference this url.
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/

LunaSea
Many thanks for this very complete response!

It seems to be a niche topic so I didn't expect to find a resource that exactly matched.

i_don_t_know
I found a paper on compiling constraints for clp(fd) in the context of GNU Prolog: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30...
i_don_t_know
I found a paper on compiling constraints for clp(fd) in the context of GNU Prolog: https://pdf.sciencedirectassets.com/271869/1-s2.0-S074310660...
I have enjoyed these courses on Coursera. You can audit them for free.

Discrete Optimization https://www.coursera.org/learn/discrete-optimization

Solving Algorithms for Discrete Optimization https://www.coursera.org/learn/solving-algorithms-discrete-o...

The second course is the last part of a three part series. The first two parts are on modeling of problems with MiniZinc. They are also quite enjoyable.

https://sat-smt.codes/main.html is a good introduction to applying SMT to many kinds of problems.

https://rise4fun.com/ for all sorts of examples of what these sorts of algorithms can solve.

https://www.coursera.org/learn/discrete-optimization is a good introduction to constraint optimization, local search, linear programming, and mixed integer programming.

I quite liked "How to win a data science competition" (https://www.coursera.org/learn/competitive-data-science) where I learned a lot about validation strategies and machine learning on tabular data. The course has its own Kaggle competition.

I also really liked "Discrete optimization" (https://www.coursera.org/learn/discrete-optimization). At the time that I took it it also had a competitive element where you would solve optimization problems and there was a leader board comparing all the students in the current batch. That was when courses still started in batches and were free so the experience would probably no longer be the same, unfortunately.

light_hue_1
> I quite liked "How to win a data science competition

As a machine learning researcher I am on the one hand glad that folks are learning more about the topic. On the other hand, this is totally the wrong approach and it will teach you the wrong lessons.

The idea that you can just treat data as a uniform dump of tables and that grinding your way to high numbers is somehow worthwhile is simply terrible. The resulting systems won't work well in the real world and they produce horrific explanations of what is going on. This class teaches you not just the wrong tools, like boosting, it teaches you the wrong mental model.

I really can't think of a worse introduction to ML than this class. Even not knowing anything would actually be better.

jackallis
ok - what is the alternative?
samvher
Interesting. I definitely would not recommend this course as an only course in machine learning or indeed as an introduction, and I see where you’re coming from with the wrong mental models. I can’t be sure that I do have the right ones but I have taken a number of other courses as well and my sense is they’re ok.

My main takeaway from the course was definitely not that just grinding away for higher numbers is the right thing to do (but it might be a necessary evil in a competition context). The key thing I learned here was much more about paying very close attention that your validation strategy and your testing strategy are compatible because there are many ways you can mess it up, making your models valid in-sample only. Most of the other things I had done before were also more around SVMs and neural networks and getting some experience with decision tree based algorithms was interesting.

https://www.coursera.org/learn/discrete-optimization

> This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

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.
dowakin
Discrete 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!

hgoury
I took watched some of the lectures and did a few exercises when I had a similar course at University, it was great indeed.
Mar 15, 2020 · cerved on Employee Scheduling
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.

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.
yoshimiagava
@dunkelheit, thank you for the link to the course. I'll give it a try!
LP is also covered in the Discrete Optimization course on Coursera:

https://www.coursera.org/learn/discrete-optimization

> Group Theory

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.

> 5).Topology(cup = donut)

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.

If you find this area fascinating, and I do, I can't recommend this cousera course enough: https://www.coursera.org/learn/discrete-optimization
hartror
+1 Fantastic course.
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

timClicks
Also of interest perhaps is a podcast episode from Software Engineering Radio with Bruce Momjian, who maintains the PostgreSQL query planner: http://www.se-radio.net/2018/06/se-radio-episode-328-bruce-m...
Tostino
Just listened to the podcast, really good listen which explains the basics really well. Highly recommend.

Thanks for the link. Wasn't aware of this podcast before.

anarazel
He does not maintain the postgresql planner. He's a PostgreSQL developer, but he has not focused on the planner for at least a decade.

Edit: Grammar.

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.

sidcool
Thanks for the detailed response. Very helpful
acutesoftware
Good answer.

I don't have a strong maths background, (had to relearn quite a bit), but found the coursera course to be really useful (and a lot of fun)

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...

excessi0n
Computer Networks is definitely the best MOOC I ever took. I hope they bring it back.
robertely
Computer Networks looks great it's a shame they pulled it down.
jamestimmins
Take a look at https://lagunita.stanford.edu/courses/Engineering/Networking.... Haven't taken either, but Stanford typically puts out pretty good MOOCs.
weber111
Lectures are great. Material is at a solid undergrad level (should be suitable for someone with 1-2yrs of CS background). No programming assignments, so I would go look at Phil Levis's website to find the "regular" course website and do the programming assignments from there.
davidgl
I LOVED discrete optimisation
eeZah7Ux
Prof. Dan Boneh's Cryptography I is really good.

Compared to many other MOOCs, it provides solid foundations while being easy to follow.

https://www.coursera.org/learn/crypto

Though I did not successfully complete it, this course was very interesting and informative: https://www.coursera.org/learn/discrete-optimization
HN Academy is an independent project and is not operated by Y Combinator, Coursera, edX, or any of the universities and other institutions providing courses.
~ yaj@
;laksdfhjdhksalkfj more things
yahnd.com ~ Privacy Policy ~
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.