Exploring the Bin Packing Problem

Using heuristics and optimization solvers for variants of BPP

Introduction

The goal of this project is to explore how heuristics and commercial optimization solvers like Gurobi can be used to find solutions of varying optimality to combinatorial NP-hard problems in the presence of time or computational constraints. For this class of problems, finding optimal solutions is often unrealistic, and, depending on your application, a reasonably good solution in a short amount of time may be preferred. This post takes a practical approach to solving the bin-packing problem and analyzes the pros and cons of employing either a heuristic or an optimization solver.

Background

The bin packing problem consists of packing items of varying sizes into a finite number of bins of fixed capacity. The objective is to minimize the number of bins used to pack all the items.

Example bpp instance with bin capacity 9 taken from SCIP documentation

Applications of the bin packing problem are wide ranging and include loading trucks, scheduling tasks, manufacturing items from resources, and placing files of specified sizes into memory. There are many variations of the problem. Items may be packed by weight or price. Items may be fragmented and packed separately for a certain cost. When packed together, items may occupy less space such as the case in VM (virtual machine) packing. The most common variations of the bin packing problem:

• Knapsack
• 1-Dimensional Bin Packing
• Cutting Stock Problem
• Variable Size Bin Packing Problem (VSBPP)
• 2-Dimensional Bin Packing Problem

This report will focus on the 1-dimensional bin packing problem with containers of fixed size.

If you’ve read Wikipedia, then you know that this is a combinatorial NP-Hard problem; however, deciding if a collection of items will fit into a some finite number of bins is strongly NP-complete. In fact, for each fixed bin B, the decision problem is solvable in polynomial time [1].

Solutions to the bin packing problem can be approximated by algorithms. Algorithm performance is measured by an approximation ratio called the worst-case ratio. For a given list of items L, the number A(L) denotes the number of bins used when algorithm A is applied to list L, while OPT(L) denotes the the optimum number for this list. The worst case performance ratio is defined as A(L) / OPT(L) [1].

Algorithms are classified as being either an online or offline heuristic. In online heuristics, items arrive in order and a decision must be made on where (or if ) to pack an item. The algorithm has no knowledge of the next item or whether there even will be a next item. In some variants, the cost of packing an item may also not be known until the item is packed. An example of an online heuristic is the First-Fit algorithm in which an item is placed in the first bin that can fit the item, only opening a new bin if no bins are found. According to Békési and Galambos in 2012, no online algorithm can have an approximation ratio smaller than 248/161 [2].

Offline heuristics on the other hand have knowledge of the complete list of items before execution. They have the advantage of being able to modify the list of items. For example, the First-Fit-Decreasing algorithm sorts the list of items in decreasing weight before determining how to pack each item. Offline algorithms have improved approximation guarantees over their online counterparts but do so at the cost of increased time complexity i.e. the time required to sort the list.

The bin packing problem can also be modeled as a mixed integer program with possible linear relaxations. Optimization solvers can be used to find solutions and calculate best lower bounds i.e. minimum number of bins required to pack all items. The most popular and powerful optimization solver is Gurobi. Other non-commercial, open source tools exist such as SCIP MatLab, and CBC. SCIP offer similar functionality but often provide slower, less optimal solutions. Both Gurobi and SCIP offer easy-to-use Python APIs. Optimization solvers typically outperform heuristics with respect to optimality; however, they do so with added complexity and increased runtimes. Read here for Gurobi’s latest performance benchmarks compared to its non-commerical competition.

Implementations

Mixed Integer Program

Given a list of n items with weight wᵢ and an unlimited number of bins of capacity c, the 1-dimensional bin packing problem with a fixed bin capacity can be modeled as a mixed integer program by introducing binary variables xᵢⱼ and yᵢ .

Figure 1: 1-D BPP with fixed bin capcity modeled as mixed integer program

Here UB is the upper bound for the total number of bins required to pack all n items, and for simplicity can be set to UB = n i.e. the worst case scenario where each item is packed in its own bin.

Using Gurobi Python API, we can implement the above MIP and solve for the n_bins required to pack the list of n items.

Figure 2: Gurobi BPP MIP implementation

After solving the optimization problem, the bin assignment for each item can be determined by iterating through each binary variable in the matrix x. The same MIP can be implemented using SCIP. Below is the SCIP implementation.

Figure 3: SCIP BPP MIP implementation

Heuristics

Since linear programs are offline by nature, meaning that the model is implemented by knowing the exact number of bins that need to be packed, I decided to focus on offline heuristics. There are many different offline heuristics. The simplest and most common are:

• First-Fit Decreasing
• Best-Fit Decreasing
• Worst-Fit Decreasing

I implemented and generated results for all three, but will focus on FFD. As descibed earlier, the First-Fit algorithm searches the bins in order and places the item in the first bin that can accomodate it, only opening a new bin in the event that no bins are found. FFD implements this same algorithm; however, it first sorts the list of items in decreasing order.

The FFD algorithm can be implemented with a time complexity of O(n log n ). Sorting n items is an n log n operation. Finding the first bin that can pack an item is also an n log n operation if the bins are stored in a self-balancing binary search tree. For my implementation, I simply store the bins in a list resulting in O(n²) runtime.

Figure 4: FFD Python implementation with O(n²) time complexity

Heuristics as a Starting Solution for MIP

So far in this post, I have shown how to model, implement, and solve the bin packing problem as a MIP with two optimization solvers i.e. Gurobi and SCIP. We have also seen how to use offline heuristics such as FFD, BFD, and WFD to approximate the optimal solution with some worse-case performance ratio.

These two methods can be used together in a complementary approach. Specifically, we can employ a heuristic such as FFD to quickly find a good solution to the problem and pass this as the starting point for the optimization solver. The optimization solver can then either prove optimality or improve on the initial solution. The advantage of this approach is that the solver does not need to solve the problem from scratch.

Figure 5: Passing starting solution to Gurobi

In Figure 5, a listbin_for_item is used to initialize the matrix x of binary variables in the Gurobi model. We can create the listbin_for_itemby using the FFD Python implementation from Figure 4. Putting it all together, we have the following code.

Figure 6: MIP with intial solution from FFD heuristic

By using the FFD heuristic, we are not only able to pass an initial solution to Gurobi, but we can also specify a tighter upper bound to the model thus reducing the number of variables added and constraints of the model. MIPGap , SolutionLimit , and TimeLimit are Gurobi model parameters that can be tuned to alter the behavior of the Gurobi optimizer. I’ll described how these can be used in more detail in the Discussion section.

Results

All results were generated using bin packing benchmarks from BPPLIB. The library contains benchmarks for both bin packing and cutting stock problems. Here is a list of the benchmarks: Falkenauer, Scholl, Wäscher, Schwerin, Schoenfield_Hard28, Randomly Generated Instances, Augmented Non IRUP and Augmented IRUP Instances, and GI Instances. I focused on the following:

• Falkenauer
• Scholl
• Wäscher
• Schwerin
• GI (Irnich BPP)

FFD vs Gurobi vs. Gurobi + Heuristic Runtimes

To compare the runtimes of FFD heuristic to Gurboi, I first solved every instance of the benchmarks using the FFD heuristic. Then, I solved the instances using Gurobi and set the BestObjStop model parameter to the n_bins from the FFD solution plus some small decimal value. This instructs the Gurobi model to stop solving solutions as soon as a solution is found with the same optimality that the FFD solution achieved. Lastly, I re-solved the Gurobi model; however, this time, I provided the FFD solution as the intial solution to the Gurobi model as shown in Figure 5. For the purpose of this experiment, I also specified a TimitLimit equal to 5 seconds for the Gurobi model.

In the graphs below, FFD is displayed in green, Gurobi in blue, and Gurobi with an FFD initial solution in red.

Figure 7: FFD vs Gurobi vs. Gurobi + Heuristic Runtimes

Optimality of FFD

Using the solutions from the prior experiment, I plotted the optimality of the FFD solution against that of the optimal solution provided by the benchmarks from BBPLIB.

Figure 8: n_bins for FFD vs Optimal Solution

FFD vs Gurobi Optimality

In this experiment, I increased the TimeLimit to 5 minutes and removed BestObjStop parameters from the Gurobi model. I again provided the initial solution to Gurobi; however, this time I set theSolutionLimit to 3 — the idea being to stop the Gurobi model after either 5 minutes or after 3 solutions have been found that improved upon the initial solution provided by the FFD heuristic.

Figure 9: n_bins for Gurobi vs FFD vs Optimal Solution

Discussion

Analyzing the Results

As expected, the FFD algorithm finds a solution much quicker than Gurobi. Figure 7 clearly shows that any offline heuristic, even one implemented with quadratic time complexity, will execute faster than an optimization approach. For some benchmarks such as Faulkenaur_T , Gurobi fails to find a solution with the same number of bins as the FFD algorithm in the 5 second time limit. For the Irnich benchmark, Gurobi continues running way past the 5 second time limit. The reason for this is that Gurobi only performs the termination checks at certain points in the execution. For the instances of the Irnich benchmark, Gurobi has not even begun evaluating solutions when it finally stops executing after 30 seconds.

Now, this time limit approach isn’t particularly interesting as the speed at which Gurobi finds solutions is determinant on many factors one of which being the number of threads used. My MacBook reliably supports 8. Gurobi allows as many as 120. Also, Gurobi performs many computations before it attempts to find solutions. It evaluates feasibility heuristics of its own to find upper and lower bounds, and performs root relaxation and other presolve computations.

The time spent doing feasibility heuristics can be avoided by using the Heuristicparameter. Gurobi recommends the Method parameter as means of speeding up the presolve time. PreSolve and PrePass can also be used to tune the aggressiveness of the presolve computations. All of these choices come at a cost. Limiting the presolve and heuristics parameters often means limiting the effectiveness of Gurobi to move the best bound i.e. determine what is an optimal solution. For this reason, I left all parameters to their default values in order to get a sense of the time comparison between a heuristic and the recommended settings for Gurobi.

From Figure 7, we can also see that providing an initial solution to Gurobi resulted in a much quicker runtime. Again, this isn’t very surprising since in this experiment Gurobi was told to stop as soon as a solution of the same optimality of the FFD solution was found. Since the FFD solution was provided as an initial solution, Gurobi simply stopped after it finished performing the feasibility heuristics and presolve computations.

In Figure 8, FFD finds relatively optimal solutions. In fact, it is known that there always exists at least one ordering of items for which a First-Fit heuristic will produce an optimal solution [1]. For someScholl1instances, a decreasing list of items results in FF finding an optimal solution. We can surmise that for a simple heuristic such as FFD, optimality is largely predicated on the triviality of the problem. As the problems become more complex, FFD solutions prove to be less optimal. For theFaulkenaur_T benchmark, some FFD solutions have a MIP Gap over 10%. For many applications, this level of optimality may be unacceptable.

In the final experiment, the goal was to show that given the time to perform computations, Gurobi will outperform heuristic solutions. In this experiment, I utilized the MIPFocus parameter. This parameter controls the solution strategy of Gurobi. Since I was using the good solution found by FFD as an initial solution for my model, I set this parameter to MIPFocus=2 . The reasoning being that since I already have a good, feasible solution, Gurobi should instead focus on either improving the solution, or proving that the solution is indeed optimal.

“If you are more interested in good quality feasible solutions, you can select MIPFocus=1. If you believe the solver is having no trouble finding the optimal solution, and wish to focus more attention on proving optimality, select MIPFocus=2. If the best objective bound is moving very slowly (or not at all), you may want to try MIPFocus=3 to focus on the bound.” — https://www.gurobi.com/documentation/9.0/refman/heuristics.html#parameter:MIPFocus

In Figure 9, instances 1 through 3 of the Schwerin benchmark show that Gurobi improves the initial solution from FFD and finds an optimal solution. In instance 4, we see that Gurobi is unable to find a more optimal solution and instead returns the initial solution from FFD. Again, it’s important to remember that Gurobi had a TimeLimit=300 and SolutionLimit=3 which means Gurobi will timeout after 5 minutes or return the last solution after finding 3 more optimal solutions. If allowed to run with no termination parameters, Gurobi would eventually find an optimal solution.

Pros and Cons of Heuristics and MIPs

After digesting the results, it is important to ask what are the pros and cons of each method.

Heuristics have the advantage of providing quick solutions. In addition, they are relatively simple to implement when compared to linear or mixed integer programs. But, depending on the triviality of the problem, or the worst-case ratio of the algorithm, a heuristic solution may or may not provide an optimal solution. And while this may not be apparent from my results, it is generally known that in the majority of cases, heuristics are not able to find an optimal solution. Lastly, heuristics are not flexible. For example, if a variable or constraint of the problem changes, the effectiveness of the heuristic may be affected. If performance declines, then an entirely new algorithm must be written.

Given ample time, optimization techniques routinely provide the best possible solution. Variables and constraints are not static. The Gurobi model adapts automatically to changes. For example, if our list of items changes over time in such a way that an FFD heuristic performs poorly, we must choose a new heuristic. An MIP on the other hand will not be affected. The mathematical concepts and methods of the solver perform just the same. While a Gurobi model does provide optimal solutions, in order to optimize the model, the problem must first be formulated as a linear or mixed integer program. For the case of the 1-dimensional bin packing problem with a fixed bin size, this proved to be quite easy; however, as problems become more complex, modeling them mathematically may prove to be daunting task. And most obviously, the optimal solutions found by a Gurobi model come at the cost of added time complexity. For realtime applications, this latency and runtime complexity may not be tolerable.

Lastly, it’s important to recognize how both methods can be used in a complementary. So, when should a heuristic be used to provide an optimal solution to an linear or mixed integer program?

Gurobi recommends this approach when:

• Initial solution is hard
• Relaxation is hard to solve
• Need quick solution, strict time constraints
• Helps prune tree

By providing an initial solution to the solver, the computation overhead for Gurobi is decreased. Gurobi no longer needs to solve the entire problem from scratch. Instead, it either proves optimality or improves the initial solution. Figures 10 and 11 shows exactly that.

In Figure 10, Gurobi is provided no initial solution. It is able to find a heuristic solution of 330 bins and finds an initial solution of 330 and a solution of 173 after 15 seconds.

Figure 10: Execution of MIP Gurobi model without initial solution

Below in Figure 11, the FFD solution of 190 bins is passed to Gurobi and 190 is set at the upper bound for the model. The first solution is 190 bins, and is improved to 171 after 30 seconds.

Figure 11: Execution of MIP Gurobi model with FFD initial solution

This is not the perfect example for the benefit of providing initial solutions to an optimization approach. The reason being is that for this example, the initial solution is not difficult. In Figure 10, Gurobi is able to find an initial solution within seconds. But as problems become larger and more complex, the initial solutions may take longer to solve. In these scenarios, as Gurobi recommends, providing initial solutions will reduce the computation and result in quicker solutions.

Related Work

Employing heuristics to approximate combinatorial optimization problems, and specifically the bin packing problem, is not a novel idea. There are dozens if not hundreds of publications detailing different algorithms and heuristics for many of the variants of the bin packing problem, each proposing some new algorithm or formulation and publishing the approximate ratio achieved. In addition, there are many works such as Comparison of some bin packing heuristics [9] that compare the time complexity and performance of some of the most popular heuristics.

Employing heuristics to provide good initial solutions to NP-complete optimization problems also is a well studied and documented topic. Much of the inspiration for my exploration was fueled by the blog post Optimization vs. heuristics: Which is the right approach for your business?. Here Z Caner Taşkın takes a practical approach about how businesses can chose the right approach to utilize optimization techniques for their applications. After reading this article, I knew this was a topic I wanted to explore. I was determined to apply it to a variant of the bin packing problem because the bin packing problem finds itself at the root of a wide range of optimization applications.

The first example I found of heuristics being used in tandem with Gurobi was from Gurobi’s tutorial Python III — Optimization and Heuristics [3]. In this video, they used heuristics and the Gurobi solver to find solutions for a mining problem. In this example, a miner must determine which blocks of land to extract and the order in which to extract them. After some more googling, I found a great YouTube series published by Decision Making 101 called Models in Python and Gurobi [5] which applied this same method to the bin packing problem at a small scale.

At this point, I had the foundation and examples to implement something similar in both Gurobi and SCIP. After reading some publications, I found many which cited BPPLIB benchmarks [7]. I decided to extend the examples I found from [3] and [5] to evaluate a larger set of instances of the bin packing problem. BPPLIB in total contained over 6,000 instances!

Future Work

There are three ways in which I would like to continue my work:

• Solve BPPLIB CSP instances using column generation approach
• Model more variants of bin packing problem as MIPs/LPs
• Compare commercial solver Gurobi vs opensource alternative SCIP

Column Generation Approach

In addition to all of the bin packing benchmarks I used in this post, BPPLIB also contains cutting stock instances. I would like to do a similar analysis as described in the Implementation section using a Gurobi model that uses a column generation approach.

The advantage of column generation approach is that not all possibilities need to be enumerated. First, a subset of the variables (the columns) is considered. Columns are sequentially added by using information derived from the dual variables. In a column generation approach, the problem is broken into a master problem and a subproblem. In the case of the cutting stock problem, the subproblem ends up being the knapsack problem.

For more information, read about the column generation approach on Wikipedia. The SCIP documentation walks through how to use the column generation approach to solve a simple instance of the cutting stock problem.

Variants of Bin Packing Problem

There are many variants of the bin packing problem. I would like to study how to model the 2-Dimensional BPP, Variable Sized BPP, Item Fragmentation BPP and many more.

Comparing Gurobi and SCIP

Lastly, I want to compare the performance of the most popular commercial optimization solver, Gurobi, and its open source competition, SCIP. Gurobi is largely considered the fastest and most powerful solver available. Gurobi recently published its own results in 2019 comparing itself to its competition [4]. I would like to create experiments with some bin packing benchmarks to analyze the performance of both solvers.

Conclusion

Optimization has wide ranging applications and is key to finding optimal solutions to many business supply chain, scheduling, and manufacturing problems. I wanted to explore the foundational concepts to one of the most popular combinatorial optimization problems — the bin packing problem. More specifically, I wanted to compare some of the methods that can be used to provide solutions to these problems and evaluate each method through a practical lens.

Heuristics and optimization solvers each come with their own pros and cons. Some applications may require optimal solutions with minimal MIPGap and thus will favor optimization solvers. Others may operate in a real-time setting and opt to use good solutions offered by heuristics. I’ve found that a complementary approach of blending both techniques often is the most effective solution.

“In sum, heuristic techniques are practical and offer fast and feasible short-term solutions to planning and scheduling challenges, but lack the power and flexibility to create ongoing, optimal solutions that create pathways to greater productivity and profitability.” — Z. Caner Taşkın

Heuristics and optimization solvers will continue to be paramount to many business applications and will remain a focus of much academic study. I’m thoroughly excited to find an opportunity to continue my curiosity in either.

References

1. Bin packing problem. (2020, May 6). Retrieved from https://en.wikipedia.org/wiki/Bin_packing_problem
2. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
3. [Gurobi Optimization]. (2017, April 27). Python III — Optimization and Heuristics [Video File]. Retreived from https://www.youtube.com/watch?v=VMJNb0sY_x8
4. [Gurobi Optimization]. (2019, February 11). Gurobi 8 Performance Benchmarks [PDF]. Retrieved from https://www.gurobi.com/pdfs/benchmarks.pdf
5. [Decision Making 101]. (2019, September 20). Models in Python and Gurobi [Video File]. Retrieved from https://www.youtube.com/playlist?list=PLjiMsqjDUvBj0Oz3hpzKEOsMScSi3Mp_u
6. Pedroso, João Pedro, et al. “Bin Packing and Cutting Stock Problems.” Scipbook.io, 2012, scipbook.readthedocs.io/en/latest/bpp.html.
7. M. Delorme, M. Iori, and S. Martello. BPPLIB: A library for bin packing and cutting stock problems. Optimization Letters, 12(2):235–250, 2018
8. Taşkın, Z Caner. “Optimization vs. heuristics: Which is the right approach for your business?” ICRONTech, https://icrontech.com/blog_item/optimization-vs-heuristics-which-is-the-right-approach-for-your-business/.
9. Blach, Beata Bozena (1993). Comparison of some bin packing heuristics. Master’s thesis, Texas A&M University. Available electronically from http : / /hdl .handle .net /1969 .1 /ETD-TAMU -1993 -THESIS -B627.