: Consider the following instance of ATSP

c_ij	0	1	2	3	4	5	6	7	8	9
0	1000	22	11	21	25	30	27	22	25	25
1	16	1000	13	19	18	24	25	26	22	29
2	24	21	1000	21	20	26	30	28	26	23
3	20	12	13	1000	24	23	25	30	30	23
4	18	10	20	15	1000	29	24	28	23	22
5	25	14	22	14	23	1000	12	21	12	19
6	19	14	13	12	23	10	1000	12	11	16
7	11	23	15	14	15	10	14	1000	22	21
8	11	18	23	19	13	25	17	21	1000	15
9	19	24	16	20	19	12	22	14	20	1000

1. Model and solve the problem using Excel solver without subtour elimination constraints. (You can also use other solvers like GAMS, Gurobi, CPLEX to solve this part)
2. Choose the subtour in your solution which does not contain the depot. Which subtour elimination constraints can be used to eliminate this subtours obtained in part (a)? Write at least two constraints for this specific subtour.
3. Apply the nearest neighbor heuristic to obtain a feasible solution to the problem. In this heuristic, create a tour starting from the depot (node 0) and visiting the nearest unvisited node at each iteration until you visit all the nodes. When all nodes are visited, complete the tour by returning to the depot.
4. What is your information about the optimal value of the problem: what are the lower and upper bounds obtained in the previous parts?