The formulation is given BEFORE the problem

Consider the following region with $6$ cities and the travel distances shown:

Assumption: It is possible to travel directly between all nodes without going through another

node $($i$.$e$.,$ there are direct links from $1$ to $6$ of $24$ distance units, from $1$ to $4$ of $22$ distance units,

etc., that are not shown$).$

$$

TSP Exact Solution Approach

The Traveling Salesman Problem seeks to create a minimum cost $($distance$,$ travel time$)$ route

that visits each customer $($node$)$ in a given set exactly once. The following formulation has been

proposed to solve the problem:

a$)$ Find the solution that will be given by this formulation for the given network of $6$

cities.

b$)$ Does this solution provide a satisfactory traveling salesman tour through the nodes in

the network? If not, design a new constraint that will "cut$-$out" the current solution

and solve again.

c$)$ Does this solution provide a satisfactory traveling salesman tour through the nodes in

the network? If not, design a new constraint that will "cut$-$out" the current solution

and solve again.

d$)$ What happens to the solution cost as we add more constraints?

e$)$ Provide the optimal TSP$.($You can simply write the sequence in which customers are

visited; e$.$g$.1234561$

TSP Heuristic Solution Approaches

a$)$ Solve the TSP problem above using a heuristic of your choice. Provide a pseudo$-$code of

your heuristic and show your work. You can do this by hand. No need to write a

computer code.

b$)$ What is the quality of the solution you developed?