1. Consider the Symmetric Travelling Salesperson problem with the distance data from Ulysses trips in the Odyssey. Retrieve the distance data from the slides available in Moodle. Multiply each entry in the distance table by a different random number between 1 and 2 (e.g., uniformly distributed). Use computer generated random numbers. Include a copy of your distance matrix in your report. Solve the above STSP instance starting from a 1-Tree relaxation and adding cuts. You may use Python/Gurobi, Cplex, GAMS, XPress or Excel. 2. Repeat the second part of Question 1 above starting from a 2-matching relaxation. Compare the number of cuts you had to add with those in Question 1. 3. Find feasible tours using the nearest neighbor and greedy feasible heuristics discussed in class. How good are these tours with respect to the optimal tours? 4. Turn the Ulysses distance matrix into an asymmetric one by randomly changing distances. Report your distance matrix. Solve the LP relaxations of the asymmetric TSP for the instance you created a. only using assignment constraints, b. using assignment + MTZ constraints c. using assignment + connectivity constraints. Report the lower bounds in each case as well as the CPU usage. What are your observations? 5. With reference to Q4, solve part b and c as integer optimization problems using your favorite integer solver. Report the CPU usage and number of cuts used and/or number of nodes explored in both cases. What are your observations?