# Solution of Bin Packing Instances in Falkenauer T Class: Not So Hard
## 3 Algorithm Description
### Branching Phase  
Regarding the example in Section 2, this phase is responsible for choosing the cells in the rainbow matching table, using backtrack if necessary.  
The input of the branching phase is a fixed A-set. A branching procedure is performed, which improves a collection of triplets step by step. The algorithm uses the following two kinds of steps:  
* Add a triplet \((a,b,c)\) to the current collection once.  
* Remove a triplet \((a,b,c)\) from the set of available triplets, preventing it from being added later.  
The branching phase has a main loop, which performs the two kinds of steps on a collection of triplets until either no guaranteed steps can be made, or the current branch is proven to be impossible to complete. In the former case, the loop is concluded with a branching step. In the latter case, the solution is backtracked to the last branching step. The main loop of the branching phase is now described.  
Each item group \(g\) is logically split into the _a-group_ and _bc-group_ according to whether the items are to be used in the A-set or not. Let \(L_{a}(g)\) and \(L_{bc}(g)\) be the number of remaining items in these two groups. Note that \(L_{a}(g)+L_{bc}(g)=L(g)\) and these groups are well defined, since the A-set is fixed.  
In the beginning of the main loop, \(U_{A}(g)\) is updated for each a-group and \(U_{BC}(g)\) is updated for each bc-group, according to the current collection and available triplets. Let \(U(g)\) denote \(U_{A}(g)\) if \(g\) is an a-group, and \(U_{BC}(g)\) if \(g\) is a bc-group.  
The following rules are established:  
* If \(L(g)>U(g)\) for any group \(g\), then the current branch is impossible to complete.
* If \(L(g)=U(g)\) for any group \(g\), then all triplets \((a,b,c)\) containing \(g\) are added \(M(a,b,c)\) times into the solution.
* If \(M(a,b,c)=0\) for any triplet, then it is removed from the set of available triplets. These rules are applied repeatedly as long as possible. If a new triplet is added to the current collection, the current loop is finished and restarted. If none of the rules is applicable, then a branching triplet \((a,b,c)\) is chosen, and the two branches consist of the two kinds of steps for that triplet, i.e., adding it once to the current collection, or removing it from the set of available triplets. The branching phase always chooses the adding step first. The removing step is only executed if the backtrack returns to this point.  
The branching triplet \((a,b,c)\) is chosen using the following heuristic rule. Rather than choosing the triplet itself, an item group \(g\) is chosen that most likely needs the available triplets it is part of.  
1. Among item groups \(g\), choose the one for which \(\frac{L(g)}{U(g)}\) is the largest.
2. If there is a tie, the a-group \(g\) is preferred over the bc-group \(g\).
3. If there is still a tie, the largest \(g\) is chosen.
4. Among triplets \((a,b,c)\) for which \(g\in\{a,b,c\}\), choose the one for which \(M(a,b,c)\) is largest.
5. If there is a tie, the larger \(a\) is chosen.
6. If there is still a tie, the larger \(b\) is chosen. The loop is finished and restarted. This main loop is repeated until either of the following occurs:  
* \(L(g)=0\) for all item groups \(g\). This means that a solution is found.
* The current branch is impossible to complete and there are no branching steps to backtrack to. This means that the current A-set is impossible to solve.