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$).$

Min${\displaystyle \underset{\text{i}\text{i}\text{n}\text{N}}{\overset{?}{}}}{\displaystyle \underset{\text{j}\text{i}\text{n}\text{N}}{\overset{?}{}}}{c}_{ij}{x}_{ij}$

$s.t.$: ${\displaystyle \underset{\text{i}\text{i}\text{n}\text{N}}{\overset{?}{}}},ij{x}_{ij}=1,$AAjinN

${\displaystyle \underset{\text{j}\text{i}\text{n}\text{N}}{\overset{?}{}}},ji{x}_{ij}=1,$AAiinN

$x_{ij}in\{0,1\},$AAiinN,jinN

Given:

N: set of customers to be visited

$c_{ij}$ : cost $($e$.$g$.$ distance$)$ to travel from customer

i to customer $j$

D Decision variables

$x_{ij}$:$1$ if customer $j$ is visited after customer $i$;$0$

otherwise

Q$1$: 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$