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.