H. Mittelmann                     APM523                             Fall 2017


                               ===========
                               TSP Project
                               ===========


In this first project you look at a very famous and important combinatorial
optimization problem, the traveling salesperson problem. Files needed are in
http://plato.asu.edu/APM523/TSP/
Solve AMPL problems by websubmission to neos-server.org (Gurobi, SCIP, etc)

Look at the old assignment TSP.pdf. Proceed as outlined there except instead
of the 10-city problem (just exercise for you) consider the smallest problem in TSPLIB
https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

This is a problem with GEO data (longitude/latitude, GPS). Find from the
enclosed file tsp.pdf how to generate the distance matrix.
Find a way to generate a map of the locations and save it. 
Make a guess for the optimal tour. Then use the map to manually 
mark the optimal tour (obtained through NEOS-Concorde submission). 

For the generation of the distance matrix you need to know how to make all its
elements integer. You round down (towards zero) all real numbers to the next
integer. In some languages this is done with the NINT function. Use that or
program it in the language of your choice.

(a) First eliminate all subtours (using tsp.mod) and then  eliminate the ones 
that do occur for the model tsp1.mod. Document what you did. Submit to
NEOS-MILP-SCIP-AMPL.

(b) Frequently TSPs are not symmetric. Give examples! To consider a "meaningful"
ATSP related to the given TSP take into account that a "beeline" travel is only possible in the air.
There is a prevailing westerly wind on the northern hemisphere. Assume that on
all legs of this flight that have an orientation towards the west, the distance 
gets longer by 10% and shorter by 10% in the other cases.

You need a method to solve ATSPs. It is possible to transform ATSPs to TSPs of
twice the size. Find out from the file atsp2tsp.pdf how to do that and 
compute with NEOS submission the "length" and order of the windy tour.

(c) What you computed in (b) is not really the length of the windy tour. Why?
Compute the actual length of the optimal tour.

Hand in your files and report by email in a single file with your name in the
file name. Avoid any file names anywhere that are not contiguous.

due date: 8/30 6PM