This five$-$part problem deals with an alternative integer programming formulation of the TSP:

min,${\displaystyle \underset{k}{\overset{?}{}}}{\displaystyle \underset{i}{\overset{?}{}}}{\displaystyle \underset{j\text{:}ji}{\overset{?}{}}}{c}_{i,j}{x}_{k,i,j}$

$s.t.{\displaystyle \underset{j=2}{\overset{n}{}}}{x}_{1,1,j}=1$

$,{\displaystyle \underset{k=2}{\overset{n}{}}}{\displaystyle \underset{j\text{:}ji}{\overset{?}{}}}{x}_{k,i,j}=1,$AAi$>1$

$,{\displaystyle \underset{i=2}{\overset{n}{}}}{x}_{n,i,1}=1$

$,{\displaystyle \underset{k=1}{\overset{n-1}{}}}{\displaystyle \underset{i\text{:}ij}{\overset{?}{}}}{x}_{k,i,j}=1,$AAj$>1$

$,{\displaystyle \underset{i\text{:}ij}{\overset{?}{}}}{x}_{k,i,j}={\displaystyle \underset{i\text{:}ij}{\overset{?}{}}}{x}_{k+1,j,i},$AAj,$k$

all variables are binary.

As in the Dantzig$-$Fulkerson$-$Johnson formulation, $n$ is the number of cities. But in this alternative formulation, the variable $x_{k,i,j}$ equals $1$ if the salesperson's $"k$ th transition" is from city $i$ to city $j$ and $0$ if it isn't.

a$.$ What do constraints $(1)$ and $(3)$ say?

b$.$ What do the constraints in $(2)$ and $(4)$ say?

c$.$ What do the constraints in $(5)$ say?

d$.$ Recall that in the Dantzig$-$Fulkerson$-$Johnson IP formulation, there are $n\frac{n-1}{2}$ variables and $n$ degree constraints, and in theory on the order of $2^n$ subtour elimination constraints $($but in practice typically far fewer$).$ What can be said about the number of variables and constraints in the alternative formulation? Here, there's no need to be excessively precise! Big$-O$ statements would be fine.

e$.$ Now suppose that the salesperson makes one transition per day, each transition takes place at the very beginning of the day, and each transition takes very little time relatively speaking, so that when the salesperson reaches their arrival city, they have plenty of time to do their business, check into their hotel, and then have a nice dinner. Let $y_k$ be a new variable that equals the number of the city in which the salesperson has dinner on day $k.$ Express $y_k$ in terms of the other variables. Under what circumstances might it be desirable to include the $y_k$ variables in the formulation?