= Solution
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 is
$$
L(P)=\text{fixed cost}(P)+\sum_{j\in J}\min_{i\in M}c_{ij}.
$$
This 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 bounds
$$
\begin{aligned}
L(a=1,b=2)&=11+15+\min(19,20)+\min(23,28)=68,\\
L(a=1,b=3)&=11+13+\min(17,14)+\min(23,28)=61,\\
L(a=1,b=4)&=11+22+\min(17,14)+\min(19,20)=66.
\end{aligned}
$$
The first and third children cannot improve the <incumbent>. Expand $a=1,b=3$, the sole active bound below $64$. Its last two possible completions are
$$
\begin{aligned}
(a,b,c,d)=(1,3,2,4)&:\quad 11+13+17+28=69,\\
(a,b,c,d)=(1,3,4,2)&:\quad 11+13+23+14=61.
\end{aligned}
$$
Update 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, with
$$
\boxed{a\mapsto1,\quad b\mapsto3,\quad c\mapsto4,\quad d\mapsto2,
\qquad\text{minimum total cost}=61.}
$$
The 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.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-38-assignment-search.png]
{title=Completed best-bound assignment search, with the optimal branch highlighted}
Back to article page
