AMS 467/667, Spring 2020, HW1: Hello MIP World
Due: Thursday, February 20, 9AM
This is a very short exercise, meant to give everyone a quick hands-on experience with a commercial LP/MIP solver. As a preliminary step, you will need to download and install the Gurobi solver with an academic license (unless you are working on a JHU server that has Gurobi already installed).
On this assignment you are welcome to get help from fellow students and friends. Two students, working together, can turn in a single paper. I recommend this -- it is more fun to work in a team!
To begin, download Gurobi's example code tsp.py implementing the TSP MIP process we covered in class on February 6. (If you prefer to work with Java, please download instead tsp.java; or tsp_c.c if you program in C.)
This code works with randomly generated instances. To get a feeling for the code, the assignment is to modify it to read a TSP distance matrix from a file, such as the following 10-point example.
0 63 0 25 39 0 19 66 22 0 41 22 16 38 0 15 48 11 12 26 0 80 57 19 77 35 63 0 13 53 15 10 30 34 29 0 25 55 37 17 33 26 23 24 0 50 28 26 47 19 36 44 40 49 0The travel cost from each city to itself is set to 0; these are the 0 values at the end of each data line. For city 2, the travel cost to city 1 is 63. For city 3, the travel cost to city 1 is 25 and the cost to city 2 is 39. And so on.
For the assignment, use your code to solve the following 50-point example.
This example gives the Google Maps travel distances between 50 landmarks in the USA; in 2015 it was widely discussed in the popular press (often with the note that finding the optimal tour is impossible for modern computing systems).
You should submit (by email) your code and the output (and running time) for the 50-point test.
For extra credit, modify the code to use Gurobi's LP solver rather than the MIP solver, combining the connect loop (from February 6) and the depth-first-search branch-and-bound outline (from Feburary 13).