# Solution of Bin Packing Instances in Falkenauer T Class: Not So Hard
## 3 Algorithm Description
### Overview of the Algorithm  
The input of the algorithm consists of \(N\) items of positive weights each, the sum of which is \(\frac{N}{3}S\) for some positive constant \(S\). Items with the same weight are considered identical by the algorithm. Identical items together form an _item group_. A _triplet_ is of the form \((a,b,c)\), where \(a,b,c\) are item groups, \(a\geq b\geq c\) and \(a+b+c=S\) for some constant  
Figure 4: Solution with 19 triplets, obtained by local improvements.  
\(S\). Here, \(S\) denotes the bin capacity that a triplet must exactly fill. A _collection_ of triplets is a list of triplets which disregards order, and may contain the same triplet multiple times. A _solution_ is a collection of \(\frac{N}{3}\) triplets, where the occurrence of each item group matches the weight distribution of the \(N\) items of the problem instance. The output of the algorithm is a solution, if one exists.  
For the Falkenauer T instance set, \(S=1000\) and \(a,b,c\in Z\), and \(N\in\{60,120,249,501\}\). Note that \(a=b>c\) or \(a>b=c\) are possible, but \(a=b=c\) is not, although the algorithm can handle all of these situations.  
At specific points of the algorithm, a current collection of triplets is maintained which represents a partially constructed solution. For such points, denote by \(L(g)\) the number of items in group \(g\) from the original \(N\) items, minus the number of times \(g\) occurs in the current collection. An item group \(g\) becomes _depleted_ if \(L(g)=0\), and _over-depleted_ if \(L(g)<0\). If any group is over-depleted, the current collection cannot be completed into a solution solely by adding new triplets into it.  
Denote by \(M(a,b,c)\) the _maximum usage_ of a triplet, defined as the maximum number of times that triplet can be chosen into the current collection without over-depleting any item group. It can be calculated as follows:  
\[M(a,b,c)=\begin{cases}\min\{L(a),L(b),L(c)\}&\text{if $a>b>c$,}\\ \min\{\lfloor\frac{L(a)}{2}\rfloor,L(c)\}&\text{if $a=b>c$,}\\ \min\{L(a),\lfloor\frac{L(b)}{2}\rfloor\}&\text{if $a>b=c$,}\\ \lfloor\frac{L(a)}{3}\rfloor&\text{if $a=b=c$.}\end{cases}\]  
In the description, the set of _available triplets_ is also referred to, which means all triplets with \(M(a,b,c)>0\), except that the algorithm is allowed to further exclude triplets as a branching decision.  
The algorithm is separated into four phases.  
1. Pre-processing phase.
2. A-set fixing phase.
3. Branching phase.
4. Local search phase.  
Note that the first and second phases from Section 2 are further divided. This is for the sake of better explaining the algorithm implementation. The pre-processing, A-set fixing, and branching phases explain the formal steps of the first phase. The local search phase corresponds to the second phase.  
The algorithm can be operated in the following two modes.  
* Backtracking method: The branching phase uses backtrack until a solution is found. In this method, the local search phase is skipped.
* Local search method: The branching phase provides a collection of triplets, which is improved into a solution by the local search phase.