Data.BinPack

This module implements a number of common bin-packing heuristics: FirstFit, LastFit, BestFit, WorstFit, and AlmostWorstFit. In addition, the not-so-common, but analytically superior (in terms of worst-case behavior), ModifiedFirstFit heuristic is also supported. Further, the (slow) SumOfSquaresFit heuristic, which has been considered in the context of online bin-packing (Bender et al., 2008), is also supported.

Items can be packed in order of both Decreasing and Increasing size (and, of course, in unmodified order; see AsGiven).

The module supports both the standard (textbook) minimization problem ("How many bins do I need to pack all items?"; see minimizeBins and countBins) and the more practical fitting problem ("I've got n bins; which items can I take?"; see binpack).

The well-known heuristics are described online in many places and are not further discussed here. For example, see http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm for an overview. A description of the ModifiedFirstFit algorithm is harder to come by online, hence a brief description and references are provided below.

Note that most published analysis assumes items to be sorted in some specific (mostly Decreasing) order. This module does not enforce such assumptions, rather, any ordering can be combined with any placement heuristic.

If unsure what to pick, then try FirstFit Decreasing or BestFit Decreasing as a default. Use WorstFit Decreasing (in combination with binpack) if you want a pre-determined number of bins filled evenly.

A short overview of the ModifiedFirstFit heuristic follows. This overview is based on the description given in (Yue and Zhang, 1995).

Let lst denote the list of items to be bin-packed, let x denote the size of the smallest element in lst, and let cap denote the capacity of one bin. lst is split into the four sub-lists, lA, lB, lC, lD.

lA

All items strictly larger than cap/2.

lB

All items of size at most cap/2 and strictly larger than cap/3.

lC

All items of size at most cap/3 and strictly larger than (cap - x)/5.

lD

The rest, i.e., all items of size at most (cap - x)/5.

Items are placed as follows:

1. Create a list of length lA bins. Place each item in lA into its own bin (while maintaining relative item order with respect to lst). Note: relevant published analysis assumes that lst is sorted in order of decreasing size.
2. Take the list of bins created in Step 1 and reverse it.
3. Sequentially consider each bin b. If the two smallest items in lC do NOT fit together into b of if there a less than two items remaining in lC, then pack nothing into b and move on to the next bin (if any). If they do fit together, then find the largest item x1 in lC that would fit together with the smallest item in lC into b. Remove x1 from lC. Then find the largest item x2, x2 \= x1, in lC that will now fit into b together with x1. Remove x1 from lC. Place both x1 and x2 into b and move on to the next item.
4. Reverse the list of bins again.
5. Use the FirstFit heuristic to place all remaining items, i.e., lB, lD, and any remaining items of lC.

References:

• D.S. Johnson and M.R. Garey (1985). A 71/60 Theorem for Bin-Packing. Journal of Complexity, 1:65-106.
• M. Yue and L. Zhang (1995). A Simple Proof of the Inequality MFFD(L) <= 71/60 OPT(L) + 1, L for the MFFD Bin-Packing Algorithm. Acta Mathematicae Applicatae Sinica, 11(3):318-330.
• M.A. Bender, B. Bradley, G. Jagannathan, and K. Pillaipakkamnatt (2008). Sum-of-Squares Heuristics for Bin Packing and Memory Allocation. ACM Journal of Experimental Algorithmics, 12:1-19.

Types

data PlacementPolicy

What placement heuristic should be used?

Constructors

FirstFit

Traverse bin list from head to last and place item in the first bin that has sufficient capacity.

ModifiedFirstFit

See above.

LastFit

Traverse bin list from last to head and place item in the first bin that has sufficient capacity.

BestFit

Place item in the bin with the most capacity.

WorstFit

Place item in the bin with the least (but sufficient) capacity.

AlmostWorstFit

Choose the 2nd to worst-fitting bin.

SumOfSquaresFit

Choose bin such that sum-of-squares heuristic is minimized.

Instances

Eq PlacementPolicy

Ord PlacementPolicy

Show PlacementPolicy

data OrderPolicy

How to pre-process the input.

Constructors

AsGiven

Don't modify item order.

Decreasing

Sort from largest to smallest.

Increasing

Sort from smallest to largest.

Instances

Eq OrderPolicy

Ord OrderPolicy

Show OrderPolicy

type Measure a b = b -> a

A function that maps an item b to its size a. The constraint (Num a, Ord a) has been omitted from the type, but is required by the exposed functions.

Feature Enumeration

Lists of all supported heuristics. Useful for benchmarking and testing.

allOrders :: [OrderPolicy]

The list of all possible OrderPolicy choices.

allPlacements :: [PlacementPolicy]

The list of all possible PlacementPolicy choices.

allHeuristics :: [(PlacementPolicy, OrderPolicy)]

All supported ordering and placment choices.

Bin Abstraction

Conceptually, a bin is defined by its remaining capacity and the contained items. Currently, it is just a tuple, but this may change in future releases. Clients of this module should rely on the following accessor functions.

type Bin a b = (a, [b])

A Bin consists of the remaining capacity together with a list of items already placed.

emptyBin

Arguments

:: (Num a, Ord a)

=> a

The initial capacity.

-> Bin a b

The empty bin.

Create an empty bin.

emptyBins

Arguments

:: (Num a, Ord a)

=> a

The initial capacity.

-> Int

Number of bins.

-> [Bin a b]

Create multiple empty bins with uniform capacity.

asBin :: (Ord a, Num a) => a -> Measure a b -> [b] -> Bin a b

Turn a list of items into a pre-filled bin.

tryAddItem

Arguments

:: (Num a, Ord a)

=> a

The item's size.

-> b

The item.

-> Bin a b

The bin.

-> Maybe (Bin a b)

Just the updated bin with the item inside, Nothing if it does not fit.

Try placing an item inside a Bin.

addItem

Arguments

:: (Num a, Ord a)

=> a

The item's size.

-> b

The item.

-> Bin a b

The bin.

-> Bin a b

Just the updated bin with the item inside, Nothing if it does not fit.

Place an item inside a Bin. Fails if there is insufficient capacity.

addItems

Arguments

:: (Ord a, Num a)

=> Bin a b

The bin that should be augmented.

-> Measure a b

A function to determine each item's size.

-> [b]

The items that are to be added.

-> Bin a b

The resulting bin.

Add a list of items to an existing bin. Fails if there is insufficient capacity.

items :: Bin a b -> [b]

Get the items in a bin.

gap :: Bin a b -> a

Get the remaining capacity of a bin.

Bin-Packing Functions

minimizeBins

Arguments

:: (Num a, Ord a)

=> PlacementPolicy

How to order the items before placement.

-> OrderPolicy

The bin-packing heuristic to use.

-> Measure a b

How to size the items.

-> a

The size of one bin.

-> [b]

The items.

-> [Bin a b]

The result: a list of Bins.

Bin-packing without a limit on the number of bins (minimization problem). Assumption: The maximum item size is at most the size of one bin (this is not checked).

Examples:

• Pack the words of the sentence "Bin packing heuristics are a lot of fun!" into bins of size 11, assuming the size of a word is its length. The Increasing ordering yields a sub-optimal result that leaves a lot of empty space in the bins.

 minimizeBins FirstFit Increasing length 11 (words "Bin packing heuristics are a lot of fun!")
 ~~> [(2,["are","Bin","of","a"]),(4,["fun!","lot"]),(4,["packing"]),(1,["heuristics"])]

• Similarly, for Int. Note that we use id as a Measure of the size of an Int.

 minimizeBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4]
 ~~> [(0,[1,10]),(0,[4,7]),(0,[2,3,3,3])]

countBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> Int

Wrapper around minimizeBins; useful if only the number of required bins is of interest. See minimizeBins for a description of the arguments.

Examples:

• How many bins of size 11 characters each do we need to pack the words of the sentence "Bin packing heuristics are a lot of fun!"?

 countBins FirstFit Increasing length 11 (words "Bin packing heuristics are a lot of fun!")
 ~~> 4

• Similarly, for Int. As before, we use id as a Measure for the size of an Int.

 countBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4]
 ~~> 3

binpack

Arguments

:: (Num a, Ord a)

=> PlacementPolicy

The bin packing heuristic to use.

-> OrderPolicy

How to order the items before placement.

-> Measure a b

How to size the items.

-> [Bin a b]

The bins; may be non-uniform and pre-filled.

-> [b]

The items.

-> ([Bin a b], [b])

The result; a list of bins and a list of items that could not be placed.

Bin-pack a list of items into a list of (possibly non-uniform) bins. If an item cannot be placed, instead of creating a new bin, this version will return a list of items that could not be packed (if any).

Example: We have two empty bins, one of size 10 and one of size 12. Which words can we fit in there?

 binpack WorstFit Decreasing length [emptyBin 10, emptyBin 12]  (words "Bin packing heuristics are a lot of fun!")
 ~~> ([(0,["Bin","packing"]),(0,["of","heuristics"])],["a","lot","are","fun!"])

Both bins were filled completely, and the words "are a lot fun!" coult not be packed.