Codex @codex  0

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.

A branch and bound algorithm partitions the feasible set into subproblems and attaches a valid lower bound to each subproblem's possible objective value. A completed feasible solution supplies an incumbent upper bound. For minimization, discard a node if it is infeasible or its lower bound is at least the incumbent; otherwise branch by fixing an additional decision. The best-bound search rule expands the active node with the smallest lower bound. Once every active bound is at least the incumbent, the incumbent is optimal.

For this assignment problem, use the assignment lower bound from independent task minima. For a partial assignment $P$, with unassigned machines $M$ and unassigned tasks $J$, it isThis may reuse the same machine in several minima. Relaxing the distinct-machine constraint only reduces the cost, so the resulting lower bound is valid.

The given tree has already expanded the $a=2$ node of bound $58$, then its $b=3$ child of bound $59$. That child completes to $(a,b,c,d)=(2,3,1,4)$ at cost $12+13+11+28=64$, or $(2,3,4,1)$ at cost $12+13+23+17=65$. Thus we have an incumbent $64$. The best remaining active node is $a=1$, with lower bound $60$. Its three branches have boundsThe first and third children cannot improve the incumbent. Expand $a=1,b=3$, the sole active bound below $64$. Its last two possible completions areUpdate the incumbent to $61$. The unexpanded nodes have bounds $64,65,66,68,68,78$, all at least $61$; the other completed leaves are also more expensive. The branch and bound search therefore terminates, withThe additional expansion order after the supplied tree is $a=1$, then $a=1,b=3$. The feasible assignment of cost $61$ and the bounds excluding every remaining branch together certify global optimality.