Branch and bound ununderstandable example Good evening! I had an example of the branch and bound algorithm method in combinatorial optimization which I didn't understand. I don't know if I do not master the basis or if the teacher did mistakes.
Let be a matrix $m*n$ displaying the allocation costs fo $m$ workers to $n$ tasks.


*

*One worker can only be allocated to one task.

*$M_{ij}$ is the allocation cost of worker $i$ to task $j$.


The allocation problem consists to minimize the final cost.
\begin{array}{|c|cccc|}
\hline
& 1 & 2 & 3 & 4\\
\hline
1 & 8 & 3 &1 & 5\\
2 & 11 & 7 & 1 & 6\\
3 & 7 & 8 & 6 & 8\\
4 & 11 & 6 & 4 & 9\\
\hline 
\end{array}
There is at least $n!$ allocations. But enumerating them is a too time consuming solution
We notice that $task_1$ allocation costs at least $16$ :


*

*$task_2\ge3$

*$task_3\ge1$

*$task_4\ge5$


As far as the $task_1\ge7$ the sum is at least $16$ (But shouldn't we say that this is the case for any first allocation?)
We can start separating the root in $4$ branches showing how w can allocate $task_1$ to $worker_1$ with a limit of $9+\max A_{i1}=8 + 6 + 1 + 6=21$ (which I don't understand, it should have been 8+3+1+6=18, no?)
Therfore it will be for the first round $node_1=\sum_{i=1}^{4}(9+task_i)$ whose graph is the following:



*

*I don't understand why the "1->1" arrow has a cost of 21. To my mind it should have been $8$ + 3+1+5 = 17

*I don't understand why the cost grows on the following node as far as we said that we had a limit. (I haded the arrow on the sedges from the second row of node to the third myself, I'm not sure about them).

*I don't understand why we developed the first node as far as we
developed the most expensive node.
Considering the same problem but an allocation on the workers :

I better understand the method, we would therefore develop the last node, but not yet the cost results.

When they allocate $task_1$ to $worker_k$, they delete column $1$, since $task_1$ cannot be assigned twice, and row $k$, since $worker_k$ cannot be given two tasks. Thus, after $task_1$ is assigned to $worker_1$, the matrix is reduced to this:
$$\begin{array}{|c|cccc|} \hline
&2&3&4\\ \hline
2&7&1&6\\
3&8&6&8\\
4&6&4&9\\ \hline
\end{array}$$
Then they take the cheapest remaining allocation cost of each task: $6$ for $task_2$, $1$ for $task_3$, and $6$ for $task_4$. These are then added to the allocation cost of $8$ for $task_1$ to get $8+6+1+6=21$.
Then they allocate $task_1$ to $worker_2$, and the matrix is reduced instead to this:
$$\begin{array}{|c|cccc|} \hline
&2&3&4\\ \hline
1&3&1&5\\
3&8&6&8\\
4&6&4&9\\ \hline
\end{array}$$
The minimum allocation costs for $task_1,task_2$, and $task_3$ are now $3,1$, and $5$, so the total is $11+3+1+5=20$.
The labels in the three nodes below the $1\to 1$ node seem to be partly incorrect: the costs make sense, but not the numbers preceding the costs. Say that we assign $task_1$ to $worker_1$ and $task_2$ to $worker_2$; that already has an allocation cost of $8+7=15$, and the matrix is now reduced to this:
$$\begin{array}{|c|cccc|} \hline
&3&4\\ \hline
3&6&8\\
4&4&9\\ \hline
\end{array}$$
The minimum-cost allocation of $task_3$ is to $worker_4$, with a cost of $4$, and the minimum-cost allocation of $task_4$ is to $worker_3$, with a cost of $8$. The total cost of the allocation is $15+4+8=27$, as stated in the node, and the allocation is feasible, since each task was allocated to a different worker.
Suppose that we assign $task_1$ to $worker_1$ and $task_2$ to $worker_3$; the cost so far is $8+8=16$, and the matrix is reduced to this:
$$\begin{array}{|c|cccc|} \hline
&3&4\\ \hline
2&1&6\\
4&4&9\\ \hline
\end{array}$$
The minimum-cost allocation of $task_3$ is to $worker_2$, with a cost of $1$, and the minimum-cost allocation of $task_4$ is also to $worker_2$, with a cost of $6$. The total cost of the allocation is $16+1+6=23$, as stated in the node, but the allocation is infeasible, since $worker_3$ was given two tasks.
