 Solution

Use the minimization form in this part. Treat every diagonal arc as forbidden, not as a zero-cost loop. The assignment relaxation of the travelling salesman problem requires one incoming and one outgoing arc at each city but permits several disjoint directed cycles. Its optimum is a lower bound on the tour optimum.

At the root chooseFor every allowed arc, $u_i+v_j\le c_{ij}$. Their total is seven. The assignmentuses only tight arcs and has cost $1+1+1+2+2=7$. The minimization certificate from part (c) therefore provesIt is not a tour, because it has a three-cycle and a two-cycle.

Branch on the two-cycle. Every five-city tour omits at least one of $3\to 4$ and $4\to 3$, so the children $x_{34}=0$ and $x_{43}=0$ cover every possible tour. They may overlap, which does not invalidate the bounds.

For the child $x_{34}=0$, useThese satisfy $u_i+v_j\le c_{ij}$ on every allowed arc of that child and sum to ten. The tourhas cost $1+1+3+2+3=10$ and uses tight arcs, certifying that the child assignment bound is exactly ten.

For the child $x_{43}=0$, interchange the roles of cities three and four in those potentials. Its lower bound is again ten, attained bywith cost $3+2+3+1+1=10$. Thus both first-level assignment optima are already tours.

There is a useful direct interpretation of the improved bound. Split the cities into $A=\{1,2,5\}$ and $B=\{3,4\}$. A forbidden arc of the two-cycle forces an assignment arc from $B$ to $A$, and balance forces at least one from $A$ to $B$. Relative to the root potentials, each crossing arc has reduced cost $3-3/2=3/2$, so any child assignment costs at least $7+2(3/2)=10$.

The first branching therefore completes the search: each child's lower bound equals a feasible tour value. Hence