Coursera: Discrete Optimization
I recently took the first iteration of the university of Melbourne course on discrete optimization taught by Pascal van Hentenryck on Coursera.
The format of the course differs in some ways from that of other courses on Coursera in that it is completely open. All lecture videos and assignments are available from the start, programming assignments can be done in any order and solutions for each assignment can be submitted until the end of the course, allowing students to follow their own plan of study and revisit earlier assignments to try new techniques.
The lecture videos are split into three categories: constraint programming, local search and linear programming / integer programming, introducing a diverse set of techniques such as dynamic programming, branch and bound, simulated annealing, tabu search, the simplex algorithm and more to tackle many kinds of optimization problems.
Each programming assignment consists of 6-8 problem instances of varying size with the goal of finding an optimal or close to optimal solution to one of the following NP-hard optimization problems:
- Knapsack problem
- Graph coloring problem
- Traveling salesman problem
- Warehouse location problem
- Vehicle routing problem
A key aspect of the course is that very little hand holding is provided as to specific ways to approach the individual assignments. Additionally, problem instances vary greatly in size and structure, meaning an algorithm that works well on one instance of a particular problem might not yield good results or take too long to run on another.
While this has easily been the most challenging and time consuming course I have taken, going from having no prior exposure to the subject of discrete optimization to submitting some of the top five solutions on the leaderboard was an incredibly rewarding experience.
Professor van Hentenrycks energy and ability to communicate his excitement and fascination for the subject matter are truly outstanding and his ability to explain even complex concepts in a simple and humorous way is rare indeed. I would recommend this course to anyone with an interest in the subject, or just to see the unique learning experience open online courses offer.