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