My Journey

[Originally posted here]

Like many people, this is not the first time I take Discrete Optimization.

I stumbled upon this course in 2013 and found it very interesting. I finished Knapsack without much problem and felt pretty good about myself. Then Graph Coloring beat me. My homegrown CP solver had serious bugs: I probably missed something important in the lecture. I thought to myself, "This is problem 2 and I'm already in deep s**t?!" Between a full-time job and a 9-month-old baby, I painfully realized that I could never finish it. I felt defeated, no, humiliated.

In 2014, I quickly dismissed the idea of taking this course again because I was way too busy to spare the amount of effort needed for this course.

This year, I made sure that I had the time for this course and started my journey of redemption.

Let me state my problem first:

minimize the amount of effort I spend 

subject to getting 10s for all problems that count toward the final grade 

As you can immediately see, I won't touch Set Cover although it looks really interesting. And I won't work towards improving my leader board position or program running time once I've passed 10-point line for that problem.

Naturally my weapon of choice is Local Search (LS). ("If you want guarantee, buy a toaster." has become my favorite Clint Eastwood quote.) And my programming language is C++. (Starting with Python was one of the mistakes I made in 2013.)

Now here is a laundry list of what worked for me for each assignment. You can skip it if you are not interested in technical details:

• Knapsack
• Dynamic Programming for smaller problems and Branch-and-Bound for larger ones;
• Just follow the lectures as the solution has been "spoon-fed" to you.
• Graph Coloring
• The \sum 2 * |B| * |C| - |C|^2 objective from the lecture + Tabu Search (TS) worked like magic;
• I got all 10s just by running it a bit longer.
• Traveling Salesman
• k-Opt neighbourhood as described in the lecture + Simulated Annealing (SA) for most of problems; 
• For the infamous Problem 6, 2-Opt + Guided Fast Local Search (GFLS) for the win!
• I tried k-Opt + TS first but couldn't get it to work;
• For some problems I needed to tune the k (in k-Opt) and SA parameters (starting temperature, annealing speed) more carefully to pass the 10-point line;
• I also tried a simple CP model but couldn't get it to work on even the smallest problem;
• I also tried Large Neighbourhood Search with an MIP model which rearrange a small part of the whole tour; it worked for some mid-sized problems but not enough to tackle Problem 6;
• TSP Problem 6 was the last problem I ever cracked; I'm going to buy myself a T-shirt to celebrate.
• Facility Location
• Large Neighbourhood Search (LNS) with a Mixed Integer Programming (MIP) model of adjacent facilities of a random facility and their current customers worked amazingly;
• I tried simple neighbourhoods (reassignment, swap and open/close facility) + SA first but couldn't cross the 10-point line for the two harder problems (5 & 7, I think);
• Inspired by Graph Coloring, I tried to enlarge the neighbourhood by allowing infeasible moves and penalizing constraint violation but couldn't get it to work;
• I'm impressed with SA's ability to turn weak neighbourhoods into something usable.
• Vehicle Routing
• LNS + an MIP model of two random vehicles did the trick again; for smaller problems, simple neighbourhoods (reassignment, swap and k-Opt) + SA worked too;
• I figured out an interesting way to break symmetry in my MIP model, which I shared in the forum;
• As noted by many fellow students, the bars for this assignment seemed to be lower than previous ones; maybe to give us a little break? :)

Because of my choice of LS, most of my solvers are written from scratch so I don't have much experience with general purpose tools. But I do want to say a few words on tools. 

I don't quite understand the rationale of not recommending some good tools (to reduce the search space, if you will) but it did make it harder for me to try MIP and CP. From my limited experience, Gurobi is great for MIP and Google or-tools is good for CP. Both of them have a clean API and are well-documented, which means they are very easy to learn. The only problem I had was that I only had a limited license for Gurobi which limits the size of the problems to 2000 variables and 2000 constraints. However, it wasn't so bad because LNS worked really well.

In contrast, I wasted a lot of time on CBC. I'm sure an expert user can use CBC much better than I did but I just didn't have the time (or patience). It's a shame that I didn't have the chance to use or-tools, or CP in general, since most of the assignments don't seem to have very complex constraints. But next time I need to solve a problem with CP, I know where to start.

I couldn't have done it without the following:

• My fellow students Andrew, Lukas, Nils, Adriel and others for sharing their successes and failures on the Discussion Forums;
• Assignment Visualization tool is extremely useful for discovering problem structures that you have previously missed. As a concrete example, one of the insights I got from visualizing VRP led me to a better greedy solver that halved the cost of Problem 5, thus giving the subsequent LS solver much better starting point.

Finally, I want to thank Prof. van Hentenryck and TAs for creating such a fantastic course! It was super challenging but once you climb it, you'll get to a beautiful spot!

Now let me have a Duchesse de Bourgogne beer with some of my favorite Neuhaus chocolate. I earned it. :)

To my fellow students: Succes! Bonne chance! Viel glück!