CSC 380

Fall 2016

11/28/16

Bin Packing Optimization

By: Rachel Jackson & Kirklyn Fields

CSC380 Final Report

Abstract

Bin packing is a commonly known problem within computer science with many algorithmic solutions and a variety of applications. Bin packing algorithms have been used for storing files on disk, job scheduling, and even shipping items. In this paper we consider three different algorithms for creating packing solutions that minimize the number of containers needed to pack a finite set of items. The purpose of this report is to detail our experimental process of designing our algorithms and report and compare the results of our findings.

Introduction

The problemour team has chosen to investigate this semester is the widely known bin-packing problem. There are two types of bin packing problems, online and offline. Online bin-packing is differentiated by the arrival of items that need to be packed one at a time. Contrarily, in offline bin-packing all items are present and can be dealt with at one time. For the purposes of this project we will only focus on offline bin-packing.

Previously we proposed to study the optimization of parking lot designs using bin packing algorithms. However, we ran into several difficulties trying to solve the problem within the necessary constraints intrinsic to the problem domain.Because our original project boiled down to a bin-packing problem we decided to drastically simplified our project plan to study and compare algorithmic approaches to the bin-packing.The three algorithms we chose to research, implement and compare were Exhaustive Search, First-Fit Decreasing approximation and a Genetic Algorithm.

Why 380?

This project is worthy of study within CSC 380 because it requires us to design and implement our own realizations of the algorithms we will analyze. The bin packing problem is a widely known area of interest within Computer Science, and has several useful applications in many problem domains such as memory allocation, shipping items, and job scheduling.

Literature Review

Countless computer scientist have researched the bin backing problem and its solutions. In his article “Fast Algorithms for Bin packing”, David Johnson of the Massachusetts Institute of Technology analyzed several adaptations to First Fit and Best Fit packing algorithms. First fit packs items in arbitrary order into the left most bin [2]. On the other hand, Best Fit assigns items so as to maximize the capacity of the bin into which it goes without exceeding the maximum volume of that bin [2]. That is pack the item as tightly as possible. Johnson found the variety of heuristic variations to these common algorithms had similar worst case behavior [2]. Another researcher Gy¨orgyD´osa also explored First Fit Decreasing (FFD) focusing on the”tight bound” of the algorithm. In their article “The Tight Bound of First Fit Decreasing Bin-Packing,” they demonstrated for an instance of items I, the optimal algorithm OPT(I) using FFD is less than or equal to 11/9OPT(I) +6/9 [1].

It is also possible to utilize the common genetic algorithm to solve the bin packing problem. Belgian researcher Emanuel Falknauer in his article “A Hybrid Grouping Genetic Algorithm for Bin Packing” compares the genetic grouping algorithm (GGA) to the classic style genetic algorithms applied to bin packing. Viewing the packing problem as a partitioning of a set of U items in to a collection of subsets, Falknauer aims to find a grouping of those items [3]. The objective of grouping is to optimize a cost function defined over a set of all valid groupings [3]. A special encoding scheme is used to make those valid grouping solutions which become the “chromosomes” of the hybrid GGA. Falknauer demonstrated the hybrid GGA was superior in creating better candidate solution than the classic genetic algorithm [3].

Problem Statements

Informal Statement

A collection of objects of different sizes must be packed into a finite number of containers or “bins”. Each of these bins has a fixed volume. All items must be packed in such a manner minimizes the total number of bins used. An optimal solution uses the least amount of bins, while packing all of the items. A hard constraint is the sum of weights of the items that need to be packed.

Formal Statement

Given a set of bins , B with the same size S, and a list of j items each with sizes to pack inside of those bins, find the minimum number of bins ,K ,such that the sum of items within each bin is less than or equal to the capacity of the bin.

Mixed Integer Programming formulation:

Minimize

Subject to

  • K = the number of bins needed to pack all items
  • = the ith bin
  • = the weight of items within bin B(i)
  • = The capacity for every bin (all bins have the same capacity

Experimental Procedure

Many algorithmic strategies already exist to solve bin packing problems, however our problem is naturally NP-hard, thus there will not be much optimization possible in respect to time. Instead we will measure which algorithm will minimize the total number of bins used to pack a fixed same array of items.The capacity of each bin will be the same. We experimented with three algorithms: Exhaustive Search, First Fit Decreasing Approximation, and a Genetic Algorithm. For the purposes of comparison and keeping run time manageable with exhaustive search, we used the same small array of items, [10,10,8,7,6,7,1,2,3], for each packing algorithm.

The first algorithm we researched and implemented was Exhaustive Search, a brute for approach using combinational logicThe goal of this algorithm is to generate every possible combinations of elements and select the permutation that satisfies constraints, then finding the desired result. In the bin packing problem the goal is to generate all the subsets of the set of n items and then see if any of the subsets satisfy the constraints.Finally, the last step in the algorithm will be to compare the results to return the best option. Here is some pseudocode for this algorithm:

  • For each item in the list of items:
  • Add item to total
  • if total less than size of bin
  • add item to bin
  • if bin is full
  • Create a new bin
  • Pack item
  • For each result of total bins from each iteration
  • Find least amount of bins
  • return result

Another algorithm we implemented was First Fit Decreasing Approximation. This algorithm uses a greedy approximation approach that preprocesses items with a time complexity of O(nlogn). Unlike a regular First Fit approach, items are first sorted in decreasing order before they are packed into each bin. This helps to prevent the creation of excessive bins by packing the largest items first, rather than encountering those items later on in an arbitrarily ordered list and attempting to pack them into bins that will be unable to accommodate them. Initially the number of bins is set to 0, and all bins are empty. The first bin is automatically created when the first item is encountered and packed. For each item in the list, attempt to pack that item into the first available bine If that item will not fit, create a new bin and pack that item.

Below is the pseudo code used to implement the algorithm:

Sort items to be packed in to decreasing order.

For each item:

Try: place the item in the first bin

If no bin is found:

Create a new bin

Pack item

To demonstrate how First Fit Decreasing would pack a list of items [10,10,8,7,6,7,1,2,3], with a bin capacity of 30 below is table that shows the content of a bin as each item is visited within the for loop and packed into the existing bins.

Items being packed / Total / Bins
Used
Bin 1 / 10 / 10
10 / 10 / 20
10 / 10 / 8 / 28
10 / 10 / 8 / 7 / Full
Bin 2 / 7 / 7
7 / 6 / 13
7 / 6 / 3 / 16
7 / 6 / 3 / 3 / 19
7 / 6 / 3 / 3 / 2 / 21
7 / 6 / 3 / 3 / 2 / 1 / 22
2 Bins

The last algorithm we researched and implemented was Hybrid Genetic Algorithm. To begin a population of 100 parent solutions generating using the first fit algorithm is initialized. For a total of 50 generations, two parents were selected at random. Offspring were then created from these parents using crossover and mutation. Crossover was achieved by cloning two parents, and then picking two crossover locations to swap bins between the parents and its clone. If any, duplicate items are then removed from the child solution, and any unused items are then packed into the child. Next mutation is allowed with a 50 percent probability of occurring. Simply, random bins were selected to be destroyed and the contents of those bins were saved and then repacked. Finally, the new offspring’s fitness is graded by the function below:

Fitness = [cite HGGA]

n = number of bins

 = sum of the ith bin

c = capacity of the bin

k = 2 (can be any constant greater than1)

Below is the pseudo code we used to implement this algorithm:

Initialize a population of possible solutions

For a specified amount of time:

Select two parents

Generate offspring through crossover

Mutation

Grade Fitness

Sample output of the algorithm I implemented can be seen in the chart below with a bin size of 30.

Initial population example bins:

[ [7,1], [6], [7], [8], [10], [10]],

[[1,8], [10]], [[1,7], [10], [10]],

[[10], [1,6]],

[[10], [7,1], [10], [6], [8], [7]],

[[8,1]], [[10], [7,1], [6], [7], [10], [8]]…]

Generation # / Best Fitness Score / Bins used
1 / .877111 / 1
2 / .877111 / 1
3 / .877111 / 1
4 / .877111 / 1
5 / .877111 / 1
…
50 / .877111 / 1

Here I ran into some issues in implementation because the algorithm was returning the best fitness score in the population from a chromosome solution that did not pack all of the items in the list. I believe this is a result of the mutation function not properly repacking items from bins that were deleted and how the population is being updated between generations. In the future, more time and study would be needed to prefect the genetic algorithm for bin packing in order to properly compare the results to exhaustive search and FFD.

Results and Conclusions

As expected first fit decreasing and the genetic algorithm performed faster than exhaustive search and give near optimal solutions, however they do not always find the optimal packing. FFD uses at most (4M + 1)/3 bins where M is the optimal amount of bins.Below is a chart comparing the result of bin size and number of bins used between Exhaustive search and FFD. The x-axis denotes the bin size, and the y-axis is the number of bins used to pack the items in the array.

As demonstrated by the graph above, both the first fit decreasing algorithm and exhaustive search algorithm both return the same result of total bins throughout the experiment.A lower bound exists on the bin capacity where the bin size must at least be as big as the largest item in the list in order to pack all items. As the bin size increase the number of bins used for both algorithms decreases.

Below is a chart comparing the time complexities of FFD and Exhaustive search. As you can see Exhaustive search takes longer amount of time to execute as the bin capacity increases because the number of possible combinations of item packings increases as well.

In the future we the future we would to correct the genetic algorithm so we may compare its solutions more accurately with our other two algorithms. In addition, we would like to apply these algorithms to a real world problem much like the original parking lot optimization problem we first proposed to solve.

Bibliography

  1. D´osa, Gy¨orgy. "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm I." (n.d.): n. pag. Department of Mathematics, University of Pannonia, Veszpr´em,. Web.
  2. Falkenauer, Emanuel. "A Hybrid Grouping Genetic Algorithm for Bin Packing."Journal of Heuristics2.1 (1996): 5-30.Springer. Web.
  3. Johnson, David S. "Fast Algorithms for Bin Packing."Journal of Computer and System Sciences8.3 (1974): 272-314. Web.
  4. Martello, Silvano, and Paolo Toth. "Lower Bounds and Reduction Procedures for the Bin Packing Problem."Discrete Applied Mathematics28.1 (1990): 59-70. Web