Solutions to the 6 problems in the Discrete Optimisation course on Coursera. All problems are solved to the point of passing the assignment in a reasonable time (usually less than 1 hour to solve all of the problems in a single assignment). All code is written in Julia, with the help of its JuMP and Cbc libraries.
There are 6 problems in total, and the approaches I took to solve them are listed here:
A simple test assignment
Solved using a simple branch and bound algorithm, relaxing the integrality constraint on branching. Note that this is effectively the simplest possible MIP program.
This was solved using an iterative greedy approach. If we greedily colour, then re-order so that groups are together, then we can get the same or better colouring at each iteration. This is a very easy scalable approach to the problem (outlined here).
Solved using a simple 2-opt simulated annealing algorithm. This takes some time to run, but does generate adequate solutions after a few minutes of CPU time on a small machine.
I used a KMeans clustering algorithm to break the problem down into small neighbourhoods (the assumption being that far-away warehouse/customer pairs are unlikely to be good). Each neighbourhood is then solved and using the open source Cbc optimiser. Breaking the problem down into smaller problems is vital for solving this problem in a reasonable time (good solutions are generated in a couple of minutes of CPU time on my small machine for each problem).
I first used the Clarke-Wright savings heuristic (outlined here) to get a good initial guess at the solution. In the case that this produced too many vehicles, the shortest routes were reassigned to their nearest neighbours. A short random search swapping neighbours and moving neighbours between routes is then used to form the first feasible solution. Local search with three options (to move customers between routes, swap customers or to optimise individual routes as TSP problems) are then used to improve the solution using simulated annealing. The algorithm produces good solutions to all the problems in only a few seconds of CPU time on my small machine.