Discrete Optimization Course Finished

I recently finished Pascal Van Hentenryck's Discrete Optimization online course.

The course differed from other tertiary courses and MOOCs I had taken in the past in several ways.

• It started with the video on the right instead of the dry introductions I was used to in math and computing courses. 
• The format of the course was to solve several instances of one NP-hard problem per week.
• Little guidance were given. Students were left to choose from the methods give in lectures.
• There were no quizzes!

Discrete Optimization as the name suggests is about optimizing things that take on discrete (whole number) and usually positive values. That is much of the real world. e.g. items in a knapsack, cities on a route, vehicles in a delivery schedule, so it is widely applicable. e.g. The introductory video told us that Australia spends 10-20% of GDP on logistics, and logistics is made up of discrete things like numbers of packages and vehicles, so discrete optimization is useful.

The Course

The basic ideas of the course were to:

• Learn the main techniques of discrete optimization. 
• Basics: e.g. randomization, greedy search, dynamic programming, branch and bound.
• Constraint programming
• Local search
• Mixed integer programming
• Solve a series of problems using any of the techniques learned in combination or alternative methods.
• Knapsack
• Graph Coloring
• Traveling Salesman
• Warehouse Location
• Vehicle Routing
• Puzzle Challenge (optional)

In the words of the Course Syllabus

The course has an open format.  At the start of the course all of the assignments and lectures are available and each student is free to design their own plan of study and proceed at their own pace.  The assessments in the course consist of five programming assignments and one extra credit assignment.  In the programming assignments, students experience the challenges of real world optimization problems such as selecting the most profitable locations of retail stores (warehouse location) and the design of package delivery routes (vehicle routing).   

This sounded practical on one hand, after all I usually want to learn how to solve real world problems in computer courses. On the other hand it does not make it clear how to start. 

Lacking a plan, I watched all the lectures then started solving the problems. This was probably about the worst way to do the course. Later on I noticed there was as study guide that gave a good way of doing the course. Oh well.

I watched about 40 lectures that contained some deep insights and lots of practical advice about discrete optimization.

1. Introduction, branch and bound, dynamic programming.
2. Constraint programming
3. Local search
4. Linear programming and mixed integer programming.
5. Advanced topics, column generation, disjunctive global constraints, limited discrepancy search and large neighborhood search.

Then I started on the problem sets.

The problem sets were in increasing order of difficulty and each set contained instances that were in increasing size and therefore difficulty. The size was important as all the problems were NP-hard which means roughly that they have no known exact solutions that run faster than a^n where a > 1.0 and n is the size of the problem (e.g. number of cities in the travelling salesman problem).

Solving the Problems

My problem solving went like this.

Knapsack

 Used branch and bound. Spent a lot of time getting tight bounds using a technique that was something like a genetic algorithm and developed a special data structure for it (a fixed size sorted deque). Spent way too much time on this.

Graph Coloring

Used local search. Spent time developing efficient moves and more time developing metaheuristics. Learnt why my original metaheuristic that I took so long to develop is not in wide use. Spent too much time on this.

Traveling Salesman

Used local search. Spent time developing a visualization and moves. Spent most of my time tuning well-known metaheuristics and experimenting with search strategies. Learnt why my original search strategies are not in wide use.

Warehouse Location

Used a MIP solution. Spent most of my time getting scip working and formulating the MIP problems.

Vehicle Routing

Had run out of time when I started this. Sorted vehicle trips by angle with warehouse, jiggled them back to feasibility and ran my TSP solution on each vehicle trip.

Puzzle Challenge 

Had hours left when I started this so I used whatever method came in to my head first.

e.g. For the N queens problem, I could remember MIP, local search and constraint programming solutions. Constraint propagation seemed the most natural way to do it so I wrote a simple python script for a constraint based solution. This script was too slow to get a high score (valid solution for high N) so I made a few improvements.

1. Randomized the order of searching rows for new queens as searching every column in increasing row order is very slow. I didn't have time to figure out what a good order was but random seemed unlikely to be bad, and it wasn't/
2. Coded the inner loop propagate() in  Numba which is the quickest way to make python code run at C speeds.

With those improvements my script could solve for about 900 queens but no more because it was recursive and had reached a python call depth limit. I didn't have time to convert it from a recursive to iterative so I stopped there.

 Conclusion

This seemed like a good way to learn. I went about it an inefficient way but I learned first hand why the best methods don't work like the ones I invented myself. I also got to see

• what was important for each method. e.g. tight bounds for branch and bound, efficient moves for local search
• what scales to large N. e.g. not my TSP local search
• how much time is involved learning the packages that can be used for discrete optimization, e.g. scip

You can read other students' comments on the course here.