Traveling Salesman Problem - Discrete Optimization Assignment

Discrete Optimization Assignment Traveling Salesman Problem 1 Problem Statement In this assignment you will design an algorithm to solve a fundamental problem faced by every traveling salesperson aptly named The Traveling Salesman Problem TSP All traveling salespeople start from their home travel to several cities to sell their goods and complete the day by returning home To minimize their costs traveling salespeople strive to visit all of the cities using the shortest total travel distance This amounts to finding a visitation order of all of the cities that minimizes the sum of distances traveled when moving from one city to another Figure 1 illustrates a small TSP and a feasible solution to that problem The cities are labeled from 04 4 Instructions Edit solverpy and modify the solve itinput data function to solve the optimization problem described above The function argument input data contains the problem data in the format described above The return value of solve it is a solution to the problem in the output format described above Your solve it implementation can be tested with the command python solverpy datainputFileName You should limit the solve it method to terminate within 5 hours otherwise the submission will not be eligible for full credit You may choose to implement your solver directly in python or modify the solve it function to call an external application Resources You will find several traveling salesman problem instances in the data directory pro vided with the handout Handin Run submitpy with the command python submitpy Follow the instructions to apply your solve it method on the various assignment parts You can submit multiple times and your grade will be the best of all submissions However it may take several minutes before your assignment is graded please be patient You can track the status of your submission on the feedback section of the assignment website Grading Infeasible solutions ie those that do not conform to the output format or violate problem constraints will receive 0 points Feasible solutions will receive at least 3 points Feasible solutions passing a low quality bar will receive at least 7 points and solutions meeting a high quality bar will receive all 10 points The grading feedback indicates how much your solution must improve to receive a higher grade Collaboration Rules In all assignments we encourage collaboration and the exchange of ideas on the discussion forums However please refrain from the following 1 Posting code or pseudocode related to the assignments 2 Using code which is not your own 3 Posting or sharing problem solutions Discussion of solution quality ie objective value and algorithm performance ie run time is allowed and the assignment leader board is designed to encourage such discussions Warnings 1 It is recommended you do not modify the data directory Modifying the files in the data directory risks making your assignment submissions incorrect 2 You cannot rename the solverpy file or the solve it method 3 Be careful when using global variables in your implementation The solve it method will be run repeatedly and it is your job to clear the global data between runs 4 solverpy must remain in the same directory as submitpy 3 5 Technical Requirements You will need to have python 279 or 35 at least installed on your system installation instruc tions httpwwwpythonorgdownloads 4