Reference no: EM133218280

Question 1. Provide an Integer Programming formulation of the Travelling Salesman Prob- lem (TSP). Explain the meaning of all parameters, variables, and constraints and show how the formulation prevents subtours.

Question 2. Demonstrate whether the Travelling Salesman problem is unimodular. State the significance of your answer.

Question 3. Explain how you would use a greedy heuristic to produce a solution to the TSP. State one advantage and one disadvantage of a greedy heuristic.

Question 4. Explain how you would use simulated annealing to produce a solution to the TSP. Include in your answer a definition of the cost function, neighbourhood and start- ing solution and state any parameters that are required. State one advantage and one disadvantage of simulated annealing.