Discrete Optimization at Coursera.org
This one was a really though course. Although it was though I really liked it.
First of all: the video lectures were not the same, which I was used to. The introduction of the course made me really laugh. Prof Hentenryck made the firs lecture interesting and it was a good motivation to dive into the course.
The lectures are available from the start, so if you have time and eventually prior knowledge you can just jump-start into the middle of learning. However there is a recommendation how one should watch the lecture and advance on the topics of dynamic programming, constraint programming, local search and mixed integer programming. And besides this, there were some new lectures introduced during the course to help the students understanding the concepts of greedy algorithms and to help them solve the homework.
Yes, there is a weekly homework, however weekly is again a recommendation. You can start on the assignments right after you joined — but without knowledge on the topic it won’t be fun. For almost every week you have an NP-hard problem which you have to solve to get a certificate. The rules of grading are visible on the site and I will not mention them, because they can vary from offering to offering. What will be common: you have to reach a defined amount of points from your assignments with eventually restriction of minimum number of optimum solutions (the ones worth 10 points).
For every assignment you get a handout about the problem description, a submitter and a simple solver application (which creates a feasible solution but that’s all, they do no optimization at all), and a good dataset to try your algorithm. And the submitter uses this dataset too to call your solver and send the results to the site. The handout defines the output format so you have only to print your results in the right way to the console. And you are not bound to Python in your optimization: you can use different languages (Java or C for example) or optimization tools (CHOCO, Gurobi and so on) — the only restriction is your solver has to print the result out to the console.
After your result of the problem is sent to the server it is evaluated. There are some margins defined and you get appropriate scores after your results:
- 3 points for a feasible solution
- 7 points for basic optimization
- 10 points for a very good optimization
Because these problems are NP-hard there are no correct solutions (only feasible naturally), so you do not have to have the ultimate problem solver algorithm backing you up because 7 points are easily reached, 10 require a bit more effort.
These were the weekly assignments of the offering I took:
- Knapsack problem
- Graph coloring
- Traveling Salesman Problem
- Warehouse Location Problem
- Vehicle Routing Problem
Besides these weekly assignments there are puzzle challenges where you can add some additional points to your result (however not every to get a distinction to your certificate). These are “simple” problems where the solution is OK or NOK. There are no optimal and less-optimal solutions like in the weekly homework.
Such puzzles are:
- N-Queens Problem
- All Interval Series
- Magic Series
- Magic Square
And as the solutions of the puzzles are either OK or wrong I’m thinking about to share some of my helper classes which validate the result of the algorithm. It is not the solution itself but you you can save eventually some time if you take the course in the future.
And for all problems there is a leader board too where you can compete with the other students: who has the best solution for a particular problem.
So if you are interested in optimization and want to learn something new and do some coding yourself, give it a try. Its fun every week and you can tweak your algorithms every time a bit to get a better solution.
For me, I’ll attend the next offering of the course too because this time I messed up a bit and did not optimized the warehouse location algorithm so I did not get a distinction. But in the next offering I could give another tool a try and I have my current algorithms if I get stuck.
Besides this: you can by a lousy T-shirt too if you feel so after solving the assignments.