Solution of Bin Packing Instances in Falkenauer T Class: Not So Hard

Abstract

In this work, the Bin Packing combinatorial optimization problem is studied from the practical side. The focus is on the Falkenauer T benchmark class, which is a collection of 80 problem instances that are considered hard to handle algorithmically. Contrary to this widely accepted view, we show that the instances of this benchmark class can be solved relatively easily, without applying any sophisticated methods like metaheuristics. A new algorithm is proposed, which can operate in two modes: either using backtrack or local search to find optimal packing. In theory, both operating modes are guaranteed to find a solution. Computational results show that all instances of the Falkenauer T benchmark class can be solved in a total of 1.18 s and 2.39 s with the two operating modes alone, or 0.2 s when running in parallel.

1. Introduction

Bin Packing ($BP$) is a classical problem of combinatorial optimization. It can be introduced as follows. Given n items with sizes $p_1,p_2,\dots ,p_n$ (positive rational numbers between 0 and 1), the task is to pack them into the minimum number of unit-capacity bins, not exceeding the bin capacity. The problem is well known to be NP-hard (see, e.g., [1,2,3]), and has many applications in a large number of areas including industry, transportation, and everyday life. Johnson’s thesis [4] on bin packing is one of the early works that launched the whole area of approximation algorithms. These algorithms run in polynomial time; the goal is to find optimal or near-optimal solutions.

Depending on the nature of an application, an offline or online solution is required. In the current work, we consider the offline case, where all items of the actual problem instance are known before starting the packing procedure.

Bin Packing has a rich literature. The first paper published in this area was likely the paper by Ullman [5].

1.1. Logistics and Bin Packing

Bin Packing is closely related to logistics, as in many cases, Bin Packing appears as a certain sub-problem of some more complex logistic problems.

The efficient packing of items into bins is one of the most important challenges in many logistic corporations and is a critical issue for reducing storage costs or improving vehicle space allocation. The work of Romero et al. [6] focuses on the following issues: the existence of heterogeneous bins, considering not only three-dimensional but also one- and two-dimensional instances of the problem, requirements for item–bin associations, and delivery priorities. These features have been tested, as well as the ability of the proposed treatment to solve real-world oriented instances.

Murdivien and Um [7] demonstrated how a Deep Reinforcement Learning model can effectively address the real-time sequential 3D Bin Packing problem. The results show that the presented approach is promising for tackling complex logistical challenges in dynamic settings.

Crainic et al. [8] considered a capacity planning problem, arising in the context of supply-chain management. A new problem is introduced, of determining the quantity of capacity units (also called bins) of different types to secure for the next period of activity, given the uncertainty on future needs in terms of demand for loads (items) to be moved or stored, and the availability and costs of capacity for these movements or storage activities. A new model is introduced, and a metaheuristic to solve it, while extensive numerical experiments show the efficiency of the methodology.

There is a huge number of connections between Bin Packing and logistics; see, e.g., the further recent publications [9,10,11].

We now briefly review what kind of algorithms have been considered to solve the Bin Packing problem.

1.2. Approximation Algorithms

The famous First Fit algorithm (abbreviated as FF) is one of the most popular approximation algorithms; it packs the items into the bins arranged in a preliminarily fixed order. The next item is always packed into the first bin where it fits. For $FF$, it holds that $FF\left(I\right)\le 1.7·OPT\left(I\right)$ for any instance I, where $FF\left(I\right)$ and $OPT\left(I\right)$ mean the number of bins used by FF and by an optimal algorithm, respectively; see [12,13]. If we sort the items in non-increasing order before applying FF, we obtain First Fit Decreasing (FFD) for which it holds that $FFD\left(L\right)\le 11/9·OPT\left(L\right)+6/9$ where both the multiplicative and additive constants are tight [14,15]. Similar classical algorithms are Best Fit (BF), its ordered version Best Fit Decreasing, and others.

1.3. Exact Methods

An algorithm is said to be exact if it provides the optimal solution for each instance (but there is no requirement on its running time, which can be very large).

There are many different types of exact algorithms based on dynamic programming, LP-relaxation and some kind of post-processing, branch-and-bound, and constraint programming method. Since Bin Packing is NP-hard, the exact methods are usually able to provide an optimal solution within reasonable time only for relatively small inputs; see the review on this issue by Delorme et al. [16].

One good example for exact algorithms is by Belov and Scheithauer [17], which is a branch-and-price algorithm capable of solving a wide range of instances.

1.4. Metaheuristics

Many kinds of metaheuristic approaches have been tried for Bin Packing. Such algorithms are the genetic algorithm (GA), particle swarm optimization, tabu search, variable neighborhood search, etc. These algorithms usually generate suboptimal solutions, but in many cases, they are able to find an optimal solution. We briefly list some metaheuristics below.

Falkenauer [18] proposed the so-called grouping genetic algorithm for solving BP instances. He also introduced two benchmark types, the Falkenauer U class and the Falkenauer T class. We deal with the latter one in this article.

There are also hybrid algorithms, e.g., [19]. Borgulya [20] introduces a very efficient hybrid evolutionary algorithm, solving 1615 benchmark problems, and in $99.7\%$ of these instances, the solutions are optimal. On the hard28 test set, this algorithm outperforms the earlier heuristics, finding the optimal solution for all 28 instances.

The P-SAWMBS algorithm by Fleszar and Charalambous [21] is also worth mentioning. P-SAWMBS is a variable neighborhood search (VNS) variant and is very efficient, as shown also in the paper of Borgulya [20]. After creating an initial packing, P-SAWMBS performs a series of perturbations to improve the initial solution. The number of such perturbations is at most 2000. It finds all optimal solutions for the Falkenauer T instances (and is also efficient for other classes, but in this paper, we are interested in the Falkenauer T class only).

The algorithm CNS_BP by Buljubašič and Vasquez [22] uses a consistent neighborhood search to solve the one-dimensional Bin Packing problem, where tabu search is incorporated. It is notable for solving more benchmark instances to optimality than other heuristic approaches at the time of its publication.

1.5. Some Recent Publications

Bin Packing and other combinatorial optimization problems are often solved with machine learning algorithms. In [23], the authors propose a novel method called machine learning enhanced ant colony optimization (MLACO) to efficiently generate multiple high-quality solutions from a sub-problem. The experimental results on a special type of the Bin Packing problem show that MLACO works well compared to several state-of-the-art methods. Then, it is incorporated into a branch-and-price algorithm, which leads to a significant reduction in solution time.

In [24], a special version of Bin Packing is considered, where the items have both weights and colors; the objective is to minimize the total number of fragments into which the color classes are split. Lower bounds and heuristic algorithms are introduced. In more detail, a bounding procedure is applied, then the relation between this problem and the classical Bin Packing problem is discussed, a heuristic method and a Tabu Search approach is introduced, and these are examined on a large benchmark of instances.

In [25], a related problem is solved by an optimization algorithm known as off-policy proximal policy optimization (PPO), where the hyperparameters of PPO are optimized by an artificial bee colony (ABC) algorithm for optimal performance.

In [26], the One-Dimensional Cutting Stock Problem is considered, which is closely related to Bin Packing. In the paper, the standard problem is extended with additional constraints that are generally neglected in scientific literature, although relevant in many industrial applications. Accordingly, the standard objective function is also modified. To solve the problem, a Simulated Annealing-based heuristic is proposed, which exploits a specific neighbor search. The heuristic is tested on many problem instances, and compared also to a solution provided by a commercial software.

1.6. A “New” Paradigm

In [27], the authors proposed applying a new kind of paradigm. First, we try to obtain the optimal solution for the instance with a greedy-type method. If it is successful, we are finished. If not, we apply some more sophisticated method (which is not treated in the paper). It turned out in [27] that in spite of the fact that Bin Packing is NP-hard, many instances can be solved optimally, and very easily. Two benchmark instances are considered in [27]; we will introduce these two and other benchmark instances in the next subsection. In the case of the Schwerin class, there are 200 instances, and all instances are solved optimally by the proposed greedy algorithm. For the Falkenauer U class, the results are a little weaker (this input class is harder to solve), but still more than 91% of the instances are solved optimally very quickly with another greedy algorithm.

1.7. Bin Packing Benchmarks

A wide collection of benchmark problems are listed on the homepage of Operations Research Group Bologna [28]. These instances can be used to compare algorithms to each other. We only list the benchmark classes; the interested reader can find them on the homepage. We introduce in detail only those classes that are most important to us in our present research.

• Falkenauer [18]—two classes, with 80 instances in each. The first class, Falkenauer U, is divided into four subclasses (20 instances in each), where the number of items is $n=120$, $n=250$, $n=500$, and $n=1000$, respectively. In each subclass, the item sizes are uniformly distributed between 20 and 100, and the bin capacity is $S=150$. The authors proposed a simple greedy-type algorithm to solve these instances in [27].

  The instances of the second class, Falkenauer T, include items that have to be assigned to the bins in triplets (three items per bin) in any optimal packing, where n is 60 or 120 or 249 or 501, and the bin capacity is $S=1000$. Here, again, there are 80 instances. We will focus on these instances in the present paper.

• Scholl [29]—1210 instances in total.

• Wäscher [30]—17 instances in total only, but they are considered some of the most difficult ones.

• Schwerin [31]—divided into two sets, Schwerin 1 and Schwerin 2, of $100+100$ instances. In [27], all these are solved optimally with a greedy algorithm.

• Schoenfield_Hard28 [32]—as its name indicates, these are “hard” instances, difficult to solve optimally, with 28 instances in total.

• More benchmarks: There are three further classes on the Unibo homepage, Randomly Generated Instances, in total 3840 instances, the Augmented Non-IRUP and Augmented IRUP Instances, in total 500 instances, and the GI Instances, in total 240 instances.

The total number of instances listed on the homepage [28] is 6195. The items in each instance are listed in decreasing order of their sizes, and we shall also assume the same in all our further discussion.

Lower Bounds

There are several lower bounds for Bin Packing. The simplest one is to sum up all item sizes, divide by the bin capacity, and round it up. Another simple lower bound is the number of items bigger than the bin capacity. There are also further ones; see [33,34].

Lower bounds are useful in the sense that if the result of the algorithm matches a lower bound, then it is sure that the given solution is already optimal.

1.8. The Falkenauer T Class

There are $4\times 20$ (altogether 80) instances in the Falkenauer T class. The bin capacity is $S=1000$, and the item sizes are between $S/4$ and $S/2$. In this way, the class presents instances of a restricted problem, which is still NP-hard in general.

In the Falkenauer_t_60 subclass, there are 60 items in each instance, and there are 20 instances of this type. Each instance is generated so that the items can be packed into 20 bins. If the items are packed into 20 bins, there are exactly three items in each bin; we call them “good triplets”.

Let us recall that the well-known decision problem 3-Partition has $3n$ positive integers $a_1,\dots ,a_{3n}$ as an input, and the question is whether they can be split into n triplets, all having the same sum. It is assumed that all $a_i$ are strictly between $S/4$ and $S/2$, where $a_1+\dots +a_{3n}=n·S$. This is a fundamental algorithmic problem known to be NP-hard in the strong sense. As one can see, the Falkenauer_t_60 class includes problems for the search version of 3-Partition.

1.8.1. ABC 3-Partition

A special version of 3-Partition is the following. Let there be three sets X, Y and Z, each of them containing n items. The total size of the items is $n·S$. The problem is to decide whether the items can be put into n bins, exactly one X-item, one Y-item, and one Z-item in each bin, with their sum just equal to S. This special case of 3-Partition is still NP-hard.

Let us return to the Falkenauer T instances. Based on the explanation above, one may think that packing the items in this benchmark class is hard. The goal of the present paper is to show that it is not so hard.

1.8.2. Rainbow Matching

We mention here a further problem, which is highly relevant in connection with the Falkenauer T class. Given a graph G and a color assignment on its edges, a graph $H\subset G$ is called a rainbow subgraph if the edges of H are assigned to mutually distinct colors. The literature on rainbow subgraphs is very rich; see, e.g., the surveys [35,36,37] and the very recent manuscript [38] as starting points from which a large part of the theory can be traced back. Further valuable references on rainbow matchings are given in [39].

From our point of view, the issue of rainbow matchings—and, more specifically, rainbow perfect matchings—are of great importance. Recall that a matching is a set of mutually vertex-disjoint edges, and a perfect matching is one that covers the entire vertex set. The problem of deciding whether a given edge-colored graph containing a rainbow matching of size at least k, where k is also part of the input, is NP-complete. What is more, the optimization version asking for the largest k that admits a rainbow matching of size k is not only NP-hard but also APX-hard, even when restricted to properly edge-colored paths or certain classes of trees/forests [40]. Informally saying, it means that the optimum cannot be approximated within a multiplicative constant arbitrarily close to 1. (From below, the cited paper gives a polynomial-time algorithm with approximation ratio $2/3-ϵ$ on a general input.)

The effectiveness of greedy-type algorithms was also studied, and asymptotic formulas for their expected behavior were proven in [41]. The paper exhibits a table especially for the case of $n/2$ colors in graphs of order n, which exactly corresponds to the rainbow perfect matching problem. It turns out that in sparse random graphs with randomly assigned colors, the greedy algorithm covers only a small proportion of vertices with a rainbow matching. For instance, when the average degree is 5, the greedy procedure covers less than 60% of the vertices, and even a more advanced tuning of the greedy algorithm reaches just a bit more than 72%. In this respect, it may be kind of a surprise that our implementation performs so well on the Falkenauer T instances.

Sufficient conditions on the existence of a rainbow matching either assume that each color occurs on a relatively large number of edges (see, e.g., [42,43]), or else the minimum degree is high (see, e.g., [44]), which both are again conditions not satisfied in our Falkenauer T instances.

Summarizing briefly, although the area includes a large number of papers, to the best of our knowledge, even the algorithmic works deal with theoretical issues only, rather than presenting practical solutions.

1.9. Overview of Current Work

In the current work, we focus on the Falkenauer T benchmark class. This is generally considered harder than the Falkenauer U class. Our goal is to prove that the Falkenauer T instances can be solved efficiently and fast. A new algorithm is proposed with the following key features and results.

• The algorithm is applicable to the Falkenauer T problem instances and also any other problem instances where a set of acceptable triplets for bin content can be determined a priori.

• The algorithm can operate in two modes: backtracking method and local search method. No metaheuristics or other sophisticated methods are used.

• In theory, a solution is guaranteed if exists for the given inputs, in either operating mode. However, the number of steps may grow exponentially.

• Despite the theoretical worst-case scenario, in practice, all the targeted Falkenauer T problem instances could be solved in relatively few steps, resulting in 1–2 s of total computational time for each operating mode.

The rest of the paper is organized as follows. Section 2 provides an introduction to the general idea behind the proposed algorithm, with graphical representation, and an example for the solution procedure. Section 3 describes the algorithm in detail. Computational results are discussed in Section 4, and the conclusions are in Section 5. Appendix A contains the result tables obtained for the Falkenauer T benchmark class, for each operation mode of the proposed algorithm.

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, 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·S$; hence, fewer than 20 bins are insufficient. It is stated in [18] that the optimum is 20, 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,\dots ,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.

Let us consider the scenario where item 22 is packed as the largest item in the 20-th bin. At this point, 20 of the 60 items are already packed. More precisely, we already packed into each bin the biggest item among the three to be packed there; we refer to them as A-items or big items. To obtain good triplets, each A-item has to be supplemented with a B-item (medium item) and a C-item (small item). Naturally, “big ≥ medium ≥ small” holds in each bin, but it may happen that the size of a medium item equals that of the big or small item in its bin. It may also happen that the small item of one bin is bigger than the medium item of another bin.

Having chosen the 20 A-items, there remain 40 items unpacked. We look for those item pairs which just fill the bins. We can realize that there are not too many options. Below, we will list all possibilities. Starting with the first bin, the size of its A-item is 475; hence, the remaining room is 525. So, the appropriate item pairs are the following: $(270,255)$, $(269,256)$, $(267,258)$, $(265,260)$, and $(264,261)$, that is, only five options.

This analysis is easily carried out for each of the 20 A-items; the results obtained for the current scenario are shown in Table 1. The index and size of each A-item are given in the first and second columns. The row continues with all appropriate item pairs—more precisely their sizes, taking medium first—that fit into the bin and make it completely filled. Many items occur as medium in a row and small in another row. On the other hand, 369, for instance, is only a B-item, whereas 251 is only a C-item.

2.1. Matrix Representation

The information collected in Table 1 can also conveniently be expressed via matrix representation, as shown in Figure 1. The rows and columns are indexed with the sizes of the medium (B) and small (C) items, respectively. The entry in cell (B,C) tells the index of the A-item together with which the corresponding pair forms a good triplet. Notice, however, that $s_{16}=s_{17}=396$ holds. For this reason, entry 16 in a cell means both 16 and 17. (Of course, rows 16 and 17 in Table 1 are identical, except their item indices in the first column.) There are repeated C-item sizes in the instance, too, namely 260, 258, and 251, but they do not cause coincidence in the values of the matrix entries.

2.2. Graph Representation

We can associate the colored table shown in Figure 1 with an edge-colored graph. The vertices are the B-items and C-items, each occurring once; in the present scenario, the vertex set is $\{20,\dots ,60\}\setminus \left\{22\right\}$. Edge $(b,c)$ is labeled with color i if the entry in the b-th row and c-th column of Figure 1 is i. In this way, an edge may have more than one color; for instance, the edge belonging to the item pair $(334,270)$ has both colors 16 and 17. In order to avoid double colors, we can introduce parallel edges. In our case, we take two edges connecting the vertices of items 334 and 270, assigning color 16 to one of those edges, and color 17 to the other.

The graph under consideration has 40 vertices and 97 edges (108 nonzero entries, $2\times 17$ of them in doubled columns, which yield 17 edges instead of 34, but 6 other entries have to be counted twice as they represent both colors 16 and 17), with an edge coloring that uses 20 colors. The top of Figure 2 shows the subgraph formed by the edges assigned to color 1 (blue) and color 2 (red). These two colors span a bipartite graph; we present this more convenient drawing. Let us note that it is not an induced subgraph because $(270,262)$ and $(275,257)$ are edges of color 3; moreover, the doubled $(275,260)$ is of color 4.

A closely related alternative is to view the matrix representation as the adjacency matrix of a colored bipartite graph. We give an illustration at the bottom of Figure 2, namely the subgraph formed by the edges of colors 1 through 5. The isolated vertex 264 is included with the intention to keep the vertex order in the column labeling unbroken, as given on the top of Figure 1. In the non-bipartite representation, the higher 265 and lower 265 vertices would be identical.

Comparing the two parts of the figure, one can also observe that an increase in the number of colors may make the situation substantially more complicated.

Recall from graph theory that a perfect matching is a collection of mutually disjoint edges whose union is the entire vertex set. Moreover, “rainbow subgraph” in an edge-colored graph means a subgraph in which no color occurs more than once on the edges.

Observation 3.

Having fixed the A-items, the solutions of the scenario are in one-to-one correspondence with the rainbow perfect matchings of the associated graph.

Proof. 

A solution means that the set of B-items and C-items is split into pairs, and each pair is assigned to a distinct A-item. Denoting by G the associated graph, an item pair can form a good triplet with some A-item if and only if the corresponding vertex pair is an edge in G. Hence, a partition of items into pairs such that each pair can be extended to a good triplet is equivalent to a perfect matching in G. Finally, the “rainbow” condition means that distinct edges of a perfect matching are coupled with distinct A-items. □

In this way, searching for a solution of a given scenario is an instance of the rainbow matching search problem on graphs, which is also NP-hard, as discussed in Section 1.8.2.

In the matrix representation. it means that we have an $m_1\times m_2$ matrix with $m_1\ge n$ rows and $m_2\ge n$ columns, and entries of mutually distinct values have to be selected in such a way that no row or column contains more than one selected element. We shall refer to this task as the colorful assignment problem.

2.3. Two-Phase Algorithm for Colorful Assignment

We call two entries in the matrix independent if they are in different rows and columns. An assignment is independent if it contains mutually distinct colors, and the chosen elements are all independent.

In the first phase, we try to find independent positions of different colors, as many as possible, in a greedy way. First, let us count how many times a color appears in the table. Now, the appearances of the colors are as follows:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	22
7	7	5	6	4	4	6	8	8	5	6	8	6	6	6	6		3	5	2

Since the values 16 and 17 are in the same places, let us take an average for them. Then, the appearances of the colors are as follows:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	22
7	7	5	6	4	4	6	8	8	5	6	8	6	6	6	3	3	3	5	2

2.3.1. First Phase of Packing

This is a greedy procedure. In each step, we choose a number, and equivalently an edge of G, from some color class. We require that the chosen set must be independent. When selecting the next element, let us choose the one for which in its row and in its column, there is the smallest number of edges from the other colors. More precisely, we use the following steps:

• (1). Choose a color class for which color appears as little as possible (ties are broken arbitrarily). Then, from this color, let us choose the edge for which in its row or in its column, there is the lowest number of edges with other colors.

• (2). Having chosen an edge, we delete its row and its column, and all edges from the same color. Then, go to (1).

Here is a possible result of executing the first phase. The first choice in (1) is the color class 22, as there are only 2 edges in this color.

In the case of edge (339,300), in its column, there is 1 more edge, and in its row, there are 5 edges, for 6 edges in total. In the case of edge (334,305), in its column, there are 2 edges, in its row there are 6 edges, and in total, there are 8 edges. Then, let us choose the edge (339,300). To continue, let us suppose that we obtain the next assignment. It is possible to choose 18 edges instead of 20 in this way. So far, we have not been able to choose edges from the color classes 12 and 13. See Figure 3.

In the second phase, we will try to increase the cardinality of the assignment. We try to add an edge of color 12, and then an edge of color 13 (if possible).

2.3.2. Second Phase of Packing

Assume that $k=18$ colors have been selected, and we try to extend this to $k+1$ colors.

• (a). Choose a missing color, say color 12. Scan the edges of this color, and determine whether one of them can be added. In the positive case, go to the next missing color.

• (b). Select a new edge. If it is in conflict with a member of the matching, remove the latter, replacing it with one of the same color, and repeat until all conflicts are eliminated. If this procedure ends with an extended matching, the phase is successful; otherwise, a rainbow perfect matching does not exist. Similarly to the first phase, the selection trial is performed greedily, always intending to create the fewest possible conflicts (none, one, or two in the worst case).

In the present case, we obtain the following procedure:

• Select 12 from the independent column of 251.

• Delete 14 from row 340.

• Choose 14 from row 333.

No new conflict arises; hence, the size of rainbow matching has been increased from 18 to 19. These local improvement steps and the new solution are shown in Figure 4.

The local search can now be conducted again.

• Choose 14 from the independent column of row 339.

• Omit the conflicting 22 in its row, and also the conflicting 2 in its column near the bottom.

• Select the other 2 in row 269, which is conflict-free.

• Select the other (unique) 22 in row 334.

• Remove the conflicting 15 in the same row.

• Select 15 from row 319.

No new conflict arises; hence, the size of rainbow matching has been increased from 19 to 20 and the final solution has been reached.

3. Algorithm Description

Although the illustration given in Section 2 shows how the algorithm may operate in general, the actual algorithm implementation requires a precise representation of decisions and sequencing of events in the search procedure.

The goal of this section is to provide a detailed description of the algorithmic implementation.

3.1. Overview of the Algorithm

The input of the algorithm consists of N items of positive weights each, the sum of which is ${\displaystyle \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\ge b\ge c$ and $a+b+c=S$ for some constant 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 ${\displaystyle \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 \mathrm{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\left(g\right)$ 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\left(g\right)=0$, and over-depleted if $L\left(g\right)<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)=\left\{\begin{array}{cc}min\left\{L\right(a),L(b),L(c\left)\right\}\hfill & \mathrm{if}a>b>c,\hfill \\ min\{\lfloor {\displaystyle \frac{L\left(a\right)}{2}}\rfloor ,L\left(c\right)\}\hfill & \mathrm{if}a=b>c,\hfill \\ min\{L\left(a\right),\lfloor {\displaystyle \frac{L\left(b\right)}{2}}\rfloor \}\hfill & \mathrm{if}a>b=c,\hfill \\ \lfloor {\displaystyle \frac{L\left(a\right)}{3}}\rfloor \hfill & \mathrm{if}a=b=c.\hfill \end{array}\right.$

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.

3.2. Pre-Processing Phase

In the pre-processing phase, the problem instance is simplified by adding triplets that must appear in all solutions.

This phase has corresponding steps from Section 2, since its purpose is to decrease input size using trivial decisions, making subsequent phases faster.

The following rules are established:

• If an item group g is a member of only one available triplet $(a,b,c)$, that triplet is added $M(a,b,c)$ times. This should deplete item group g; otherwise, the problem has no solution.

• If $M(a,b,c)=0$ for an available triplet, that is excluded from the set of available triplets.

These rules are repeatedly applied as long as possible. Each application may trigger the other rule to be further applicable.

Finally, if $L\left(g\right)=0$ for an item group or $M(a,b,c)=0$ for a triplet, it is permanently excluded from further calculations. It is possible that all item groups and triplets are excluded, which means that the solution is found in the pre-processing phase.

3.3. A-Set Fixing Phase

The goal in this phase is to choose and fix the A-set of triplets. The A-set is the descending-ordered list of a from each triplet $(a,b,c)$ used in the solution to be constructed. Each item group may appear multiple times in the A-set.

Recalling the example from Section 2, this phase is responsible for fixing the layout of the rainbow matching table, although the matching representation is not used in this description. A fixed A-set of triplets represents the exact row and column numbers, cell contents and colors, but not the chosen cells of the table.

First, for each item group g, we calculate upper bounds $U_A\left(g\right)$ and $U_{BC}\left(g\right)$ for how many times an item group can be used in a solution in the role of $g=a$, and the role of $g=b$ or $g=c$, respectively:

$U_A\left(g\right)=\sum _{(a,b,c):g=a}M(a,b,c),$

$U_{BC}\left(g\right)=\left(\sum _{(a,b,c):g=b}M(a,b,c)\right)+\left(\sum _{(a,b,c):g=c}M(a,b,c)\right).$

The following observations can be made:

1. Item group g must be in the A-set at least $max\{L\left(g\right)-U_{BC}\left(g\right),0\}$ times.

2. Item group g can be in the A-set at most $min\{L\left(g\right),U_A\left(g\right)\}$ times.

By choosing the cardinality of each item group g according to these lower and upper bounds, and keeping in mind that an A-set has exactly ${\displaystyle \frac{N}{3}}$ elements, possible A-sets are enumerated in reversed lexicographical order. Therefore, looking at the largest group g with a different cardinality in two A-sets, the A-set with the larger cardinality for g is enumerated first.

The algorithm is allowed to return to this second phase to move to the next A-set in the enumeration. This is the case, for example, when the current A-set turns out to be infeasible during the branching phase. The total number of A-sets can be enormous, so the next A-set is generated only when needed.

3.4. 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\left(g\right)$ and $L_{bc}\left(g\right)$ be the number of remaining items in these two groups. Note that $L_a\left(g\right)+L_{bc}\left(g\right)=L\left(g\right)$ and these groups are well defined, since the A-set is fixed.

In the beginning of the main loop, $U_A\left(g\right)$ is updated for each a-group and $U_{BC}\left(g\right)$ is updated for each bc-group, according to the current collection and available triplets. Let $U\left(g\right)$ denote $U_A\left(g\right)$ if g is an a-group, and $U_{BC}\left(g\right)$ if g is a bc-group.

The following rules are established:

• If $L\left(g\right)>U\left(g\right)$ for any group g, then the current branch is impossible to complete.

• If $L\left(g\right)=U\left(g\right)$ 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 ${\displaystyle \frac{L\left(g\right)}{U\left(g\right)}}$ 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\left(g\right)=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.

3.5. Operation Modes of the Branching Phase

The branching phase can be operated in two ways, corresponding to whether the algorithm is using the backtracking or the local search method.

If the backtracking method is used, the branching phase is performed as previously described, with no modifications. If the A-set is impossible to complete, the algorithm returns to the second phase to choose the next A-set, and the branching phase is repeated. Therefore, this operation mode is guaranteed to provide a feasible solution for the problem instance, if one exists.

If the local search method is used, the branching phase is performed with the following modifications. There is no backtracking when the current branch is proven impossible to complete by $L\left(g\right)>U\left(g\right)$. Instead, the branching phase is finished if there are no more triplets with $M(a,b,c)>0$. Branching steps can be performed, but they are never backtracked. The purpose of this method is to include as many triplets in the current collection as possible.

3.6. Local Search Phase

If the local search mode is used, the solution is usually not complete, but also cannot be naturally continued. The purpose of the local search phase is to improve the current solution by adding and removing triplets.

This phase corresponds to the local improvements in the rainbow matching problem where a good matching has been already found, and we seek to improve it by removing and adding cells.

However, to systematically explore all possible options, the representation of possible steps is different here.

From this point, the A-set and the distinction of a-groups and bc-groups are ignored. Instead, simply item groups are considered, which contain all items of the same weight. This effectively allows the change of the A-set during the search—note that in the illustration, there were no such operations.

The algorithm is also allowed to over-deplete an item group g by adding more triplets into the solution than a group g allows. Such collections can be fixed later by removing other triplets.

We define a priority between collections as follows.

• Collections with lower total over-depletion are prioritized. The total over-depletion is defined as follows:

  $\left|\sum _{g:L\left(g\right)<0}L\left(g\right)\right|.$

  A solution with zero over-depletion is called feasible.

• If there is tie, collections with more triplets are prioritized.

• If there is still a tie, the larger $L\left(g\right)$ is prioritized, where g is the largest item group that differs.

The main, outer loop of the local search consists of replacing a single, feasible collection with a new one with more triplets. At the beginning of the local search phase, this feasible collection is the one returned by the branching phase. This outer loop is repeated until a solution is found.

Within the outer loop, a set of collections and its subset of visited collections is maintained. At the beginning of the outer loop iteration, the set has a single element, called starting collection, and it is not visited. Then, an inner loop is performed which expands the set of collections as follows.

• Pick the non-visited collection with the highest priority, and mark it as visited. This will be the current collection, and it is now investigated.

• If the current collection is feasible and has more triplets than the starting collection, the inside loop stops.

• If the current collection is feasible but does not have more triplets than the starting collection, then additional collections are generated by adding any single triplet to the current collection.

• If the current collection is infeasible, then additional collections are generated by removing any single triplet from the current collection, where only triplets using an over-depleted group are considered.

Note that the set of collections is reset each time the inner loop stops and an improved, feasible collection is found. Theoretically, this local search could explore all collections, so finding a solution is guaranteed if one exists.

3.7. Analysis of the Algorithm

The computational complexity of the proposed algorithm is summarized in Table 2.

The pre-processing and A-set fixing phases are fast, as well as the branching phase in case of the local search method. In these cases, each candidate triplet is only put once into the current collection and is never removed. Note that the number of A-sets grows exponentially, but these are enumerated only on demand.

The branching phase requires exponential time in the worst case, since basically a binary search tree is explored, which contains all possible collections with the given A-set. No state is visited twice. The tree contains all possible constructions for a given A-set, and if none exists, it backtracks to the next A-set. Therefore, finding a solution is guaranteed if one exists.

The local search phase is used only by the local search method. Each node in the search tree represents one (feasible or infeasible) collection. Using the defined step, any other collection is reachable. The number of nodes can grow exponentially, but the bookkeeping of explored nodes prevents the same collection from being evaluated more than once. Therefore, although at the cost of exponential time and memory usage, finding a solution is also theoretically guaranteed if one exists.

The algorithm can be directly applied to any Bin Packing problem where each bin is supposed to be filled by triplets that can be determined a priori. This could possibly mean further problem instances than investigated. Also, most of the algorithmic steps could be applied to arbitrary tuples instead of triplets, but this is a possible direction of future research and is out of scope of the current work.

4. Results and Discussion

The algorithm was implemented in C++ language. It was run twice for each Falkenauer T problem instance: once using the backtracking method and once using the local search method. The computer used for these runs is a Dell 5440 Laptop with Intel i5-1335U CPU, 16 GB RAM, and Ubuntu 22.04.5 LTS operating system.

The source code of the algorithm, the program inputs which are the Falkenauer T problem instances, and the obtained results are all included in the Supplementary Materials. The following result tables can also be found in Appendix A of this paper.

• Table A1 shows some common data;

• Table A2 shows the results of the backtracking method;

• Table A3 shows the results of the local search method.

All results except the precise running times are reproducible using the source code, since the algorithm does not make any random or even pseudo-random decisions. Also, the algorithm is performed on a single thread of execution.

There was no need to set timeouts or memory limits, because the algorithm was completed very fast for both methods and all problem instances. Details are shown in the following subsections and Appendix A.

4.1. Pre-Processing and A-Sets

The pre-processing phase found from 0 to 2 triplets in most of the problem instances, and exactly zero in 31 instances. In two cases, for $N=60$, $i=2$ and $i=11$, it found 20 triplets, which means that these instances could be solved by the simple rules of the pre-processing phase. No alternative solutions may exist for these two instances, and no later phases were needed. This shows that pre-processing has some usefulness in more than half of the instances, and is sometimes sufficient to solve the small instances alone.

The number of possible A-sets indicates that a complete enumeration is manageable only for the smaller instances. For $N=60$, the number ranges from 1 to 91; for $N=120$, it ranges from 3 to 14,288; for $N=249$, it ranges from 95 to $6.70\times {10}^9$; and for $N=501$, it ranges from $1.93\times {10}^9$ to $6.54\times {10}^{14}$. Therefore, it would be impractical to investigate all possible A-sets for large examples, but fortunately, that was found to not be necessary.

4.2. Backtracking Method

The backtracking method finished all 80 problem instances in $1.18$ s. There were two instances which turned out to be difficult: for $N=501$, $i=0$, the runtime was $0.56$ s, and for $i=19$, the runtime was $0.54$ s. Notably, the other 78 problem instances required 78 ms altogether.

Regarding the A-set fixing phase, it should be noted that the only problem instances for which the very first A-set was found to be infeasible were all from the smallest class, $N=60$. Even in this class, at most 10 A-sets were investigated, in two instances. For all the bigger instances, the backtracking method did not need to ever backtrack to the selection of an alternative A-set. This suggests that an arbitrary A-set is very likely to be feasible.

The number of backtracking events required is small most of the time, but has a steep jump for the two difficult instances. In decreasing order, the top 5 numbers of backtracking events were 66,975, 65,916, 299, 102, 42. Most of the time, the number of backtracking events was one-digit, and was zero in exactly 24 instances, two of which were already solved in the pre-processing phase. That is more than a quarter of all instances. In contrast, there is a considerable number of branching steps: at least 157 when $N=501$, and at least 73 when $N=249$. This suggests that the heuristic rule for selecting the triplet at the branching step works effectively in most of the time. However, there are still cases where a wrong decision drives the algorithm into a very long branch, as happened for the two difficult instances.

Let us take a closer look on what might cause a long branch. The most notorious instance was $N=501$, $i=0$, requiring $0.56$ s, almost half of the total runtime. The branching phase made a total of 3,655,375 steps, where a step can be the addition of a triplet, the exclusion of a triplet from further additions, or a branching step containing the binary decision of applying or excluding the same triplet. There were 66,975 branching steps which were eventually backtracked. If we take a look at how the solution was constructed, it only contains four unsuccessful branches, consecutively after each other. After 144 triplets already in the collection, there were four trials that involved adding triplets $(394,312,294)$, $(393,312,295)$, $(392,312,296)$, and $(390,312,298)$, but none of them worked. Afterwards, the construction continued by adding $(364,324,312)$. It seems that according to the heuristic rule for selecting the next branch, only the fifth option for using up item 312 turned out to be feasible. The first four unsuccessful attempts consumed 806,382, 1,122,151, 1,990,333, and 1,623,949 steps, respectively, so each wrong decision was quite significant.

Such wrong choices seem very hard to predict. The effect of long branches may be mitigated by slightly changing the procedure of choosing the next branch, and/or trying multiple branches simultaneously.

4.3. Local Search Method

The local search method finished all 80 instances in $2.39$ s. Here, the branching phase is used to put as many triplets into the current collection as we can, but no backtracking is ever made. This is apparent from the number of branching steps that are similar to the backtracking phase.

It should be noted that the local search method relaxes the A-sets. In the rainbow matching representation, that relaxation would mean altering the triplets along the color dimension, as well as the row and column dimensions. This relaxation generally allows more options for the algorithm to choose from. Also, it was found to be necessary, since the very first A-set is not always feasible in the $N=60$ class.

As already found without the local search method, two instances were solved by the pre-processing phase, and an additional 22 instances were solved in the branching phase without backtracking. These same instances had already been solved by the time the local search phase started.

In the rest of the instances, at least 2 and at most 13 passes are needed. This is the number of times a larger collection is found, and the local search phase is effectively restarted. In other words, this is the number of iterations in the outer loop of the local search phase.

The total number of iterations in the inner loop is at most 1396 for the case $N=501$, $i=17$. This single instance required more than half of the total runtime, $1.39$ s. It required 3 passes, a distance of 55 steps (putting a triplet in and out) and 1396 collection investigations (which is the number of iterations in the inner loop). This means that only three additional triplets (9 items) were missing after the greedy construction of the branching phase, but a lot of work was required to fix this collection. The high number of collection investigations is what drives the computational time. To potentially improve this result, one could consider another rule for choosing the next collection to investigate. It seems very hard to predict which instance requires more computational time.

The top 10 total numbers of iterations in the inner loop are 1396, 836, 607, 571, 445, 407, 392, 348, 188, and 160. It is notable that only two of the top ten are from the $N=501$ class, one is from the $N=249$ class, four are from the $N=120$ class and three are from the $N=60$ class. In fact, one of the instances with 13 passes was the $N=60$, $i=12$ instance.

These observations suggest that the size of the problem instance is not strongly related to the expected number of algorithmic steps the local search method requires. Moreover, the two notorious instances, $N=501$, $i=0$ and $i=19$ were solved effortlessly using the local search method, with only 21 and 22 inner loop iterations. This suggests that whether a particular solution method finds a single problem instance difficult, it is an arbitrary phenomenon for that method itself, and another method may solve the same problem instance easily.

If we compare the results of the backtracking method and the local search method, it can be seen that the local search method was faster in 22 of the 80 instances. If the two methods are running in parallel until either finds the solution for a problem instance, all 80 instances can be solved in $0.101$ s, which is roughly $0.203$ s of the total computational time on the two threads of execution.

4.4. Comparison with Literature Examples

The hybrid evolutionary algorithm (HEA) by Borgulya [20] could solve the instances of the Falkenauer T class in an average of 1.89 s. While it is not the fastest available option for problems like the Falkenauer T class, and optimality is not guaranteed due to its metaheuristic nature, the algorithm is effective at solving a very wide range of Bin Packing problems, most notably the hard28 class. Our proposed algorithm is not directly applicable to such a general range of problems, but it is rather tailored for triplets and therefore much faster for the Falkenauer T class.

Another notable base of comparison is the heuristic algorithm P-SAWMBS by Fleszar and Charalambous [21]. This very efficient heuristic is reported to optimally solve the Falkenauer T class in less than 0.01 s per instance. Our proposed algorithm, on the other hand, theoretically guarantees convergence and finding the optimal solution if one exists, and operates without sophisticated heuristics. It uses at most 1396 collection investigations in the local search method for the hardest problem instance, compared to the maximum of 2000 perturbations used by P-SAWMBS throughout the class.

The algorithm by Belov and Scheithauer [17] is an exact branch-and-price method, which was shown by Delorme et al. to be the best among 15 exact methods [16]. Although the algorithm could solve all 80 instances, only 57 were finished in one minute, and the average time required was 24.7 s. This is much higher than the running times of the proposed algorithmic method. Note that, on the other hand, the algorithm by Belov and Scheithauer is designed to solve arbitrary Bin Packing instances, while our proposed method is specifically designed for Falkenauer-type instances.

Another approach is the algorithm CNS_BP by Buljubašič and Vasquez [22], which uses a neighborhood search for solving the one-dimensional Bin Packing problem. This is also reviewed by Borgulya [20] as one of the best methods. The running time of CNS_BP was 0.09 s on average for the Falkenauer T class, which is a bit higher than for our approach. Note that CNS_BP is also designed for a wider class of problems, and is basically a heuristic method.

Notably, although these methods could solve all instances in the Falkenauer T class, none of the algorithms mentioned by Borgulya [20] was able to solve all 1615 instances from various benchmarks. We are currently unaware of more recent results.

5. Conclusions

In our work, an algorithm was proposed to solve the Falkenauer T problem instances. The algorithm can be operated using two modes: the backtracking method and the local search method.

The backtracking method uses a simple heuristic to choose the next triplet into the collection as part of its branching step. This turned out very effective, as the number of backtracking events is much lower than the actual branching steps. With the exception of two $N=501$ instances, all were solved very fast, but altogether, the 80 instances were solved in less than $1.18$ s.

The local search method was half as fast on average, using $2.39$ s in total, but was able to easily solve the problem instances the backtracking method had trouble with. If the two methods were running in parallel, all instances were solvable in $0.203$ s of the total computational time.

These findings suggest that the instances of the Falkenauer T problem class can be solved very fast using some heuristics and algorithmic principles like pre-processing certain decisions, backtracking and/or local improvements.

An observed limitation of this approach is that some instances could turn out to be exceptionally hard, relative to others of the same size. This seems hard to predict. However, each such hard instance was eventually easy for the other method. This suggest that a possible future direction of research is exploring variants of this algorithm that can even be run simultaneously, resulting in a more robust framework. Other heuristics for choosing nodes to explore in the algorithm may also turn out to be faster. The algorithm can also be applied or adapted to other Bin Packing problem instances.

Author Contributions

Conceptualization, G.D. and Z.T.; methodology, software, validation, A.É.; formal analysis, investigation, resources, data curation: all authors; writing—original draft preparation, G.D., Z.T. and A.É.; writing—review and editing, visualization, supervision: all authors. All authors have read and agreed to the published version of the manuscript.

Informed Consent Statement

Not applicable.

Data Availability Statement

Data are contained within the article and Supplementary Materials.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. Matrix representation for the scenario involving [Forumla omitted. See PDF.].

Figure 2. Bipartite graph representation of a few color classes. Top: colors 1 and 2; bottom: colors 1–5; see text.

Figure 3. Improved matching, obtained using the local improvements.

Figure 4. Solution with 19 triplets, obtained by local improvements.

Table 1

Sizes of (B,C)-item pairs forming good triplets, assuming that $s_{22}$ is an A-item.

A-Item Index	A-Item Size	Possible Pairs of B-Item and C-Item
1	475	(270,255)	(269,256)	(267,258)	(265,260)	(264,261)
2	473	(275,252)	(270,257)	(269,258)	(267,260)	(265,262)
3	468	(280,252)	(277,255)	(275,257)	(270,262)	(267,265)
4	465	(280,255)	(277,258)	(275,260)	(270,265)
5	462	(282,256)	(280,258)	(277,261)
6	447	(302,251)	(297,256)	(289,264)
7	444	(305,251)	(304,252)	(302,254)	(300,256)	(289,267)
8	426	(319,255)	(314,260)	(313,261)	(307,267)	(305,269)	(304,270)	(297,277)
9	423	(319,258)	(313,264)	(308,269)	(307,270)	(302,275)	(300,277)	(297,280)
10	412	(334,254)	(333,255)	(319,269)	(313,275)	(308,280)
11	411	(334,255)	(333,256)	(319,270)	(314,275)	(307,282)	(300,289)
12	409	(340,251)	(339,252)	(334,257)	(333,258)	(314,277)	(302,289)
13	403	(340,257)	(339,258)	(333,264)	(308,289)	(300,297)
14	402	(347,251)	(340,258)	(334,264)	(333,265)
15	399	(347,254)	(340,261)	(339,262)	(334,267)	(319,282)	(304,297)
16	396	(347,257)	(340,264)	(339,265)	(334,270)	(307,297)	(304,300)
17	396	(347,257)	(340,264)	(339,265)	(334,270)	(307,297)	(304,300)
18	382	(366,252)	(361,257)	(314,304)	(313,305)
19	376	(369,255)	(366,258)	(347,277)	(319,305)
22	361	(339,300)	(334,305)

Table 2

Computational complexity of each phase of the algorithm.

Operation Mode	Backtrack Method	Local Search Method
Pre-processing phase	Polynomial
A-set fixing phase	Polynomial
Branching phase	Exponential time	Polynomial
Local search phase	N/A	Exponential time and memory

Supplementary Materials

The following supporting information can be downloaded at https://www.mdpi.com/article/10.3390/a18020115/s1. Source codes for both operation methods of the proposed algorithm, the Falkenauer T problem instance set, and the obtained results are attached as Supplementary Materials.

References

1. Coffmann, E.G.; Garey, M.R.; Johnson, D.S. Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems; Hochbaum, D. PWS Publishing: Boston, MA, USA, 1997.

2. Coffman, E.G., Jr.; Csirik, J.; Galambos, G.; Martello, S.; Vigo, D. Bin packing approximation algorithms: Survey and classification. Handbook of Combinatorial Optimization; Pardalos, P.M.; Du, D.-Z.; Graham, R.L. Springer: New York, NY, USA, 2013; [DOI: https://dx.doi.org/10.1007/978-1-4419-7997-1_35]

3. Garey, M.R.; Johnson, D.S. Computer and Intractability: A Guide to the Theory of NP-Completeness; Freeman: New York, NY, USA, 1979.

4. Johnson, D.S. Near-Optimal Bin Packing Algorithms. Ph.D. Thesis; MIT: Cambridge, MA, USA, 1973.

5. Ullman, J.D. The Performance of a Memory Allocation Algorithm; Technical Report 100 Princeton University: Princeton, NJ, USA, 1971.

6. Romero, S.V.; Osaba, E.; Villar-Rodriguez, E.; Asla, A. Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach. arXiv; 2023; arXiv: 2308.02787

7. Murdivien, S.A.; Um, J. BoxStacker: Deep Reinforcement Learning for 3D Bin Packing Problem in Virtual Environment of Logistics Systems. Sensors; 2023; 23, 6928. [DOI: https://dx.doi.org/10.3390/s23156928]

8. Crainic, T.G.; Gobbato, L.; Perboli, G.; Rei, W. Logistics capacity planning: A stochastic bin packing formulation and a progressive hedging meta-heuristic. Eur. J. Oper. Res.; 2016; 253, pp. 404-417. [DOI: https://dx.doi.org/10.1016/j.ejor.2016.02.040]

9. Moura, A.; Pinto, T.; Alves, C.; Valério de Carvalho, J. A Matheuristic Approach to the Integration of Three-Dimensional Bin Packing Problem and Vehicle Routing Problem with Simultaneous Delivery and Pickup. Mathematics; 2023; 11, 713. [DOI: https://dx.doi.org/10.3390/math11030713]

10. Pantoja-Benavides, G.; Giraldo, D.; Montes, A.; García, A.; Rodríguez, C.; Marín, C.; Álvarez-Martínez, D. Comprehensive Review of Robotized Freight Packing. Logistics; 2024; 8, 69. [DOI: https://dx.doi.org/10.3390/logistics8030069]

11. Yang, Y.; Xiao, M.; Li, W. Semi-Online Algorithms for the Hierarchical Extensible Bin-Packing Problem and Early Work Problem. Computation; 2024; 12, 68. [DOI: https://dx.doi.org/10.3390/computation12040068]

12. Dosa, G.; Sgall, J. First Fit bin packing: A tight analysis. Proceedings of the 30th Anniversary Symposium on Theoretical Aspects of Computer Science (STACS2013), LIPIcs 3; Kiel, Germany, 27 February–2 March 2013; Schloss Dagstuhl: Wadern, Germany, 2013; pp. 538-549. [DOI: https://dx.doi.org/10.4230/LIPIcs.STACS.2013.538]

13. Dosa, G.; Sgall, J. Optimal Analysis of Best Fit Bin Packing. Proceedings of the ICALP 2014; Copenhagen, Denmark, 8–11 July 2014; Esparza, J.; Fraigniaud, P.; Husfeldt, T.; Koutsoupias, E. Part I; Lecture Notes in Computer Sciences Springer: Berlin/Heidelberg, Germany, 2014; Volume 8572, pp. 429-441. [DOI: https://dx.doi.org/10.1007/978-3-662-43948-7_36]

14. Dosa, G. The tight bound of First Fit Decreasing bin-packing algorithm is FFD(I) ≤ 11/9 ≤ OPT(I) + 6/9. Proceedings of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE); Hangzhou, China, 7–9 April 2007; Lecture Notes in Computer Sciences Volume 4614, pp. 1-11. [DOI: https://dx.doi.org/10.1007/978-3-540-74450-4_1]

15. Dosa, G.; Li, R.; Han, X.; Tuza, Z. Tight absolute bound for First Fit Decreasing bin-packing: FFD(L) ≤ 11/9·OPT(L) + 6/9. Theor. Comput. Sci.; 2013; 510, pp. 13-61. [DOI: https://dx.doi.org/10.1016/j.tcs.2013.09.007]

16. Delorme, M.; Iori, M.; Martello, S. Bin Packing and Cutting Stock Problems: Mathematical Models and Exact Algorithms. Eur. J. Operational Res.; 2016; 255, pp. 1-20. [DOI: https://dx.doi.org/10.1016/j.ejor.2016.04.030]

17. Belov, G.; Scheithauer, G. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur. J. Oper. Res.; 2006; 171, pp. 85-106. [DOI: https://dx.doi.org/10.1016/j.ejor.2004.08.036]

18. Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. J. Heuristics; 1996; 2, 1996. [DOI: https://dx.doi.org/10.1007/BF00226291]

19. Alvim, A.C.F.; Ribeiro, C.C.; Glover, F.; Aloise, D.J. A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem. J. Heuristics; 2004; 10, pp. 205-229. [DOI: https://dx.doi.org/10.1023/B:HEUR.0000026267.44673.ed]

20. Borgulya, I. A hybrid evolutionary algorithm for the offline Bin Packing Problem. Cent. Eur. J. Oper.; 2021; 29, pp. 425-445. [DOI: https://dx.doi.org/10.1007/s10100-020-00695-5]

21. Fleszar, K.; Charalambous, C. Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. Eur. J. Oper. Res.; 2011; 210, pp. 176-184. [DOI: https://dx.doi.org/10.1016/j.ejor.2010.11.004]

22. Buljubašić, M.; Vasquez, M. Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing. Comput. Oper. Res.; 2016; 76, pp. 12-21. [DOI: https://dx.doi.org/10.1016/j.cor.2016.06.009]

23. Xu, H.; Shen, Y.; Sun, Y.; Li, X. Machine Learning-Enhanced Ant Colony Optimization for Column Generation. Proceedings of the GECCO ’24: Proceedings of the Genetic and Evolutionary Computation Conference; Melbourne, VIC, Australia, 14–18 July 2024; pp. 1073-1081. [DOI: https://dx.doi.org/10.1145/3638529.3654043]

24. Barkel, M.; Delorme, M.; Malaguti, E.; Monaci, M. Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation. Eur. J. Oper. Res.; 2025; 320, pp. 57-68. [DOI: https://dx.doi.org/10.1016/j.ejor.2024.08.007]

25. Merikhipour, M.; Khanmohammadidoustani, S.; Abbasi, M. Transportation mode detection through spatial attention-based transductive long short-term memory and off-policy feature selection. Expert Syst. Appl.; 2025; 267, 126196. [DOI: https://dx.doi.org/10.1016/j.eswa.2024.126196]

26. Bertolini, M.; Mezzogori, D.; Zammori, F. Hybrid heuristic for the one-dimensional cutting stock problem with usable leftovers and additional operating constraints. Int. J. Ind. Eng. Comput.; 2024; 15, pp. 149-170. [DOI: https://dx.doi.org/10.5267/j.ijiec.2023.10.006]

27. Ábrahám, G.; Dósa, G.; Dulai, T.; Tuza, Z.; Werner-Stark, Á. Efficient Pre-Solve Algorithms for the Schwerin and Falkenauer_U Bin Packing Benchmark Problems for Getting Optimal Solutions with High Probability. Mathematics; 2021; 9, 1540. [DOI: https://dx.doi.org/10.3390/math9131540]

28. Bin Packing Benchmarks of Homepage Unibo. Available online: https://site.unibo.it/operations-research/en/research/bpplib-a-bin-packing-problem-library (accessed on 18 February 2025).

29. Scholl, A.; Klein, R.; Jürgens, C. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res.; 1997; 24, pp. 627-645. [DOI: https://dx.doi.org/10.1016/S0305-0548(96)00082-2]

30. Wäscher, G.; Gau, T. Heuristics for the integer one-dimensional cutting stock problem: A computational study. OR Spectr.; 1996; 18, pp. 131-144. [DOI: https://dx.doi.org/10.1007/BF01539705]

31. Schwerin, P.; Wäscher, G. The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. Int. Trans. Oper. Res.; 1997; 4, pp. 377-389.

32. Schoenfield, J.E. Fast, Exact Solution of Open Bin Packing Problems Without Linear Programming; Technical Report US Army Space and Missile Defense Command: Huntsville, AL, USA, 2002.

33. Martello, S.; Toth, P. Lower bounds and reduction procedures for the bin packing problem. Discret. Appl. Math.; 1990; 28, pp. 59-70. [DOI: https://dx.doi.org/10.1016/0166-218X(90)90094-S]

34. Fekete, S.; Schepers, J. New classes of fast lower bounds for bin packing problems. Math. Program.; 2001; 91, pp. 11-31. [DOI: https://dx.doi.org/10.1007/s101070100243]

35. Kano, M.; Li, X. Monochromatic and heterochromatic subgraphs in edge-colored graphs—A survey. Graphs Comb.; 2008; 24, pp. 237-263. [DOI: https://dx.doi.org/10.1007/s00373-008-0789-5]

36. Fujita, S.; Magnant, C.; Mao, Y.; Ozeki, K. Rainbow generalizations of Ramsey theory—A dynamic survey. Theory Appl. Graphs; 2014; 0, 1. [DOI: https://dx.doi.org/10.20429/tag.2014.000101]

37. Chen, H. Long rainbow paths and rainbow cycles in edge colored graphs—A survey. Appl. Math. Comput.; 2018; 317, pp. 187-192. [DOI: https://dx.doi.org/10.1016/j.amc.2017.09.005]

38. Caro, Y.; Tuza, Z. Monochromatic graph decompositions and monochromatic piercing inspired by anti-Ramsey colorings. arXiv; 2025; arXiv: 2501.09342

39. Saito, S.; Matsumoto, N.; Wu, W. Rainbow perfect and near-perfect matchings in complete graphs with edges colored by circular distance. Theory Appl. Graphs; 2022; 9, 9. [DOI: https://dx.doi.org/10.20429/tag.2022.090109]

40. Le, V.B.; Pfender, F. Complexity results for rainbow matchings. Theor. Comput. Sci.; 2014; 524, pp. 27-33. [DOI: https://dx.doi.org/10.1016/j.tcs.2013.12.013]

41. Bennett, P.; Cooper, C.; Frieze, A. Rainbow greedy matching algorithms. Optimization, Discrete Mathematics and Applications to Data Sciences; Nikeghbali, A.; Pardalos, P.M.; Rassias, M.T. Springer Optimization and Its Applications Springer: Cham, Switzerland, 2025; Volume 220, pp. 33-50. [DOI: https://dx.doi.org/10.1007/978-3-031-78369-2_3]

42. Gao, P.; Ramadurai, R.; Wanless, I.M.; Wormald, N. Full rainbow matchings in graphs and hypergraphs. Comb. Probab. Comput.; 2021; 30, pp. 762-780. [DOI: https://dx.doi.org/10.1017/S0963548320000620]

43. Correia, D.M.; Pokrovskiy, A.; Sudakov, B. Short proofs of rainbow matchings results. Int. Math. Res. Not.; 2023; 14, pp. 12441-12476. [DOI: https://dx.doi.org/10.1093/imrn/rnac180]

44. Cano, P.; Perarnau, G.; Serra, O. Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree. Electron. Notes Discret. Math.; 2017; 61, pp. 199-205. [DOI: https://dx.doi.org/10.1016/j.endm.2017.06.039]