# Solution of Bin Packing Instances in Falkenauer T Class: Not So Hard
## 2 Illustration of Solving an Instance  
In this section, we explain how our algorithms work, using an illustrative example. * The instance is Falkenauer_t60_01, which means that \(N=60\) items are involved, and the index of the instance in the class is \(i=1\). * It is known in advance that these 60 items can be packed into 20 bins, although the algorithm does not use this information. * In the optimal solution, there are exactly three items--forming a so-called \"good triplet\"--in each bin, and all bins are completely filled. * The solution is shown in two phases. In the first phase, based on the structural properties of the instance, we apply a greedy algorithm to fill as many bins with good triplets as possible. * It may happen that all 20 bins are successfully filled in the first phase. In this case, we are finished. Otherwise, in the second phase, we try to pack all 20 bins. * We propose two operating modes for the second phase, which are two distinct versions of the algorithm. These are detailed in Section 3. The first mode is a simple backtrack, and the second mode is a local search. Although the step-number of the algorithm can theoretically be exponential, it happens that both operating modes find the solution quickly for all Falkenauer T instances. After this general description, as an illustrative example, we explain how the instance Falkenauer_t60_01 can be solved. Recall that in this instance, there are 60 items, and packing into 20 bins is searched for. The items in non-increasing order are 475, 473, 468, 465, 462, 447, 444, 426, 423, 412, 411, 409, 403, 402, 399, 396, 396, 382, 376, 369, 366, 361, 347, 340, 339, 334, 333, 319, 314, 313, 308, 307, 305, 304, 302, 300, 297, 289, 282, 280, 277, 275, 270, 269, 267, 265, 264, 262, 261, 260, 260, 258, 257, 256, 255, 254, 252, 251, and 251. Let the size of item \(i\) be denoted by \(s_{i}\). The bin capacity is given as \(S=1000\), and one can see that the total size of all items is just \(20\cdot S\); hence, fewer than 20 bins are insufficient. It is stated in [18] that the optimum is20, but in fact, we did not need this information, since our algorithm finally succeeded in packing the items into 20 bins. Generally speaking, the instances in the Falkenauer_t60 class have 60 items, the bin capacity is \(S=1000\), and the size of each item is between 250 and 491, hence between \(S/4\) and \(S/2\). Any four items have a sum more than \(S=1000\). The items fit into 20 bins if and only if there are exactly three items in each bin and the total size of the three items in each bin is exactly \(S=1000\). Restricting attention to the instance Falkenauer_t60_01, we are going to give several simple observations that will help to establish our algorithm. Let us call a packing _good_ if all the items fit into 20 bins. **Observation 1**: _No two of the first \(19\) items can be packed into a common bin._  
Proof. : The smallest sum of pairs obtained from \(s_{1},\ldots,s_{19}\) together with the overall smallest item \(s_{60}\) yields \(s_{18}+s_{19}+s_{60}=382+376+251=1009>1000\). Hence, no good triplet can contain any two of the first \(19\) items. Observation 1 helps a lot in the good packing, as it is much easier to find two appropriate items to pack into a bin where the third item is already fixed, and now the subset of available items from which we can choose is significantly smaller. The next observation concerns the biggest items in the 20-th bin. **Observation 2**: _The biggest item in the \(20\)-th bin is one from \(\{s_{20},s_{21},s_{22},s_{23},s_{24},s_{25}\}\)._  
Proof. : Since \(s_{26}+s_{27}+s_{28}=334+333+319=986<C\), this means that if the 26-th (or later) item is the biggest in a bin, then with any two further items, the total size would be too small for a good triplet. These six possible cases are to be investigated one by one. If such a case provides an optimal solution, i.e., the items turn out to fit into 20 bins, then the other options need not be considered. We call these cases _scenarios_.