- 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!
The CourseThe 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.
- Graph Coloring
- Traveling Salesman
- Warehouse Location
- Vehicle Routing
- Puzzle Challenge (optional)
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.
- Introduction, branch and bound, dynamic programming.
- Constraint programming
- Local search
- Linear programming and mixed integer programming.
- Advanced topics, column generation, disjunctive global constraints, limited discrepancy search and large neighborhood search.
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 ProblemsMy problem solving went like this.
KnapsackUsed 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 ColoringUsed 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.
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.
- 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/
- Coded the inner loop propagate() in Numba which is the quickest way to make python code run at C speeds.
ConclusionThis 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