Codex @codex  0

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

Write $(j_1,\dots ,j_k)$ for the partial assignment problem solution sending person $i$ to job $j_i$. The prescribed assignment lower bound from independent task minima isEvery completion must pay at least the minimum in each remaining column, so this is a valid lower bound, even if the minima use the same person several times. At $k=3$, the one remaining job must go to person 4, and the bound is the exact completed cost.

Use branch and bound with the smallest open bound expanded first. The initial bounds areFor example, $L(2)=12+11+13+22=58$. Expand $(2)$, givingExpand $(2,3)$. Its children are $(2,3,1)$ with bound 64 and $(2,3,4)$ with bound 65. Completing the first gives $(2,3,1,4)$ at cost 64, our first incumbent. The second cannot improve it. We may also discard $(2,1)$, $(2,4)$, $(3)$ and $(4)$, since their lower bounds are at least 64; equality may be pruned when seeking one optimum.

The remaining open prefix is $(1)$, whose children have boundsOnly $(1,3)$ can improve the incumbent. Its children $(1,3,2)$ and $(1,3,4)$ have exact completed costs 69 and 61, respectively. The latter completes to $(1,3,4,2)$ and replaces the incumbent. Every other branch has already been bounded above this value. Thus the optimal assignment isThis branch and bound computation produces fourteen partial nodes: four initial nodes, three below $(2)$, two below $(2,3)$, three below $(1)$ and two below $(1,3)$. The last person is assigned automatically at a depth-three node.

For the travelling salesman problem, let $x_{ij}=1$ mean that the tour goes directly from city $i$ to city $j$. Retain only the constraintsThis is an assignment problem between cities as departure points and cities as arrival points, solvable by the Hungarian algorithm. Its optimum is a cycle cover of a directed graph, possibly with several disjoint cycles. Since every tour is such a cover, its cost is a lower bound on the best tour cost. This is the assignment relaxation of the travelling salesman problem.

If the minimizing cover is a single Hamiltonian cycle, it supplies a tour and can update the incumbent. Otherwise choose one proper subtour $C$. No tour can contain all edges of $C$, since that would close a cycle before visiting the remaining cities. Make one child subproblem for each edge of $C$, forbidding that edge, and solve its modified assignment problem. These branches may overlap but together retain every possible tour. Prune a child if it is infeasible or its assignment bound is at least the incumbent cost. Further subtours cause further branching. Each branch adds a new forbidden edge, so the search is finite, and the covering property plus the valid lower bounds proves optimality when no open branch remains. This enforces the effect of subtour elimination constraints through branch and bound.