1) An IE student in TEDU is planning to ask some questions to the instructors before the final exams. He does not have too much time therefore he is planning to minimize the duration he spends while going from one instructor to the other. He first found the shortest distances between the entrance and the offices of the instructors as given in following table (distance values are symmetric). Instructor 1 Instructor 2 Instructor 3 Instructor 4 Entrance Instructor 1 20 Instructor 2 Instructor 3 22 2 26 30 4 10 5 9 8 a) Write the mathematical model for the symmetric TSP model without subtour elimination constraints. Explicitly specify the sets, parameters, and decision variables in your model. Let 0 indicate the entrance and the numbers 1,2,3, and 4 indicate the offices of instructors 1,2,3, and 4, respectively. b) Find a lower bound for the total distance using the minimum spanning r-tree problem where r is node 0. c) Find a solution for this problem using Christofides heuristic. What is the visiting order to the instructors? d) Obtain a feasible solution to the problem using nearest neighbor heuristic, that is, starting from the entrance, you always visit the nearest instructor which does not create a subtour. e) Write a specific subtour breaking which breaks the subtour 0-4-2-0. 2) CuppyCakesFactory is planning to start production in a new site (denoted by node 0) to satisfy the demand of four patisserie shops (denoted by nodes 1, 2, 3, and 4) of the factory. A number of vehicles will be rented for the transportation of the daily products to the patisseries. According to the contract, the daily rental cost of each vehicle is 10 TL. In order to deliver the products on time, at most two patisseries can be visited in each route. After completing its service, each truck should return to production site. It is also known that the 3rd and 4th patisseries are the largest two patisseries, therefore a single vehicle's capacity is not enough to supply the total demand of these two patisseries in a single route; in other words, a route going to both patisseries 3 and 4 is infeasible. The cost of transportation for each vehicle is 1 TL/km in each site. The following table gives the symmetric distances between the candidate sites and patisseries in kilometers. dij 1 2 3 4 10 20 10 22 18 12 17 16 19 20 a) Determine the feasible routes and calculate the total cost of each route. b) Write a mathematical model explicitly which minimizes the total cost of transportation of the daily products to the patisseries. Explicitly specify the sets, parameters, and decision variables in your model. c) Solve your model with any solver and report the optimal solution