Binpack-0.3.1: Common bin packing heuristics

Data.BinPack

Description

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. 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` as a default. Use `BestFit` (in combination with `binpack`) if you want your 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. A 71/60 Theorem for Bin-Packing. Journal of Complexity, 1:65-106, 1985.
• M. Yue and L. Zhang. 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, 1995.

Synopsis

# Documentation

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.

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 Arbitrary OrderPolicy

type Measure a b = b -> aSource

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.

type Bin = []Source

A `Bin` is a list of items.

The list of all possible `OrderPolicy` choices. Useful for benchmarking.

The list of all possible `PlacementPolicy` choices. Useful for benchmarking.

All supported ordering and placment choices. Useful for benchmarking.

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. -> ([a], [Bin b]) The result: a list of the remaining capacities and a list of the 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!")
~~> ([1,4,4,2],[["heuristics"],["packing"],["fun!","lot"],["are","Bin","of","a"]])
```
• Similarly, for `Int`. Note that we use `id` as the `Measure` for the size of an `Int`. In this case, all bins are full.
``` minimizeBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4]
~~> ([0,0,0],[[2,3,3,3],[4,7],[1,10]])
```

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

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`. Note that we use `id` as the `Measure` for the size of an `Int`.
``` countBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4]
~~> 3
```

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. -> [a] Intitial per-bin capacities. -> [b] The items. -> ([a], [Bin b], [b]) The result; a list of residue capacities, the bins, and a list of items that could not be placed.

Bin pack with a given limit on the number (and sizes) of bins. Instead of creating new bins, this version will return a list of items that could not be packed (if any).

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

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