The Bin-Packing Problem (BPP)

The problem consists of packing a set of items into a number of bins such that the total weight, volume, etc. does not exceed a maximum value. In a precise way, we define a bin-packing problem (BPP) as follows:

• We are given a finite set of items each of which has a weight
• There exist precedence constraints between items such that we incur a (possibly infinite) cost when item j follows item i
• We define an ordered group to be an ordered subset of items such that
• The total weight of the ordered group does exceed the bin capacity
• No cost between adjacent items in the group is infinite
• The primary goal is to create a feasible solution with the minimum number of ordered groups
• When two solutions have the same number of ordered groups, the one with the minimum aggregate cost is chosen

Mathematically the problem's formulation can be as follows: Given a finite set of elements with associated weights such that . Partition into subsets such that the sum of weights in each partition is at most and that is the minimum.

A typical input for the BPP and its corresponding output are shown in figure 1 and 2, respectively.

 Figure 1: Input for BBP Figure 2: Output of BBP