Safe Haskell  SafeInferred 

This module implements a number of common binpacking heuristics: FirstFit
,
LastFit
, BestFit
, WorstFit
, and AlmostWorstFit
. In addition, the
notsocommon, but analytically superior (in terms of worstcase behavior),
ModifiedFirstFit
heuristic is also supported. Further, the (slow)
SumOfSquaresFit
heuristic, which has been considered in the context of online
binpacking (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 wellknown 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 predetermined 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 binpacked, 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 sublists, lA
, lB
, lC
, lD
.
lA
 All items strictly larger than
cap/2
. lB
 All items of size at most
cap/2
and strictly larger thancap/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:
 Create a list of
length lA
bins. Place each item inlA
into its own bin (while maintaining relative item order with respect tolst
). Note: relevant published analysis assumes thatlst
is sorted in order ofdecreasing
size.  Take the list of bins created in Step 1 and reverse it.
 Sequentially consider each bin
b
. If the two smallest items inlC
do NOT fit together intob
of if there a less than two items remaining inlC
, then pack nothing intob
and move on to the next bin (if any). If they do fit together, then find the largest itemx1
inlC
that would fit together with the smallest item inlC
intob
. Removex1
fromlC
. Then find the largest itemx2
,x2 \= x1
, inlC
that will now fit intob
together withx1
. Removex1
fromlC
. Place bothx1
andx2
intob
and move on to the next item.  Reverse the list of bins again.
 Use the
FirstFit
heuristic to place all remaining items, i.e.,lB
,lD
, and any remaining items oflC
.
References:
 D.S. Johnson and M.R. Garey (1985). A 71/60 Theorem for BinPacking. Journal of Complexity, 1:65106.
 M. Yue and L. Zhang (1995). A Simple Proof of the Inequality MFFD(L) <= 71/60 OPT(L) + 1, L for the MFFD BinPacking Algorithm. Acta Mathematicae Applicatae Sinica, 11(3):318330.
 M.A. Bender, B. Bradley, G. Jagannathan, and K. Pillaipakkamnatt (2008). SumofSquares Heuristics for Bin Packing and Memory Allocation. ACM Journal of Experimental Algorithmics, 12:119.
 data PlacementPolicy
 = FirstFit
  ModifiedFirstFit
  LastFit
  BestFit
  WorstFit
  AlmostWorstFit
  SumOfSquaresFit
 data OrderPolicy
 = AsGiven
  Decreasing
  Increasing
 type Measure a b = b > a
 allOrders :: [OrderPolicy]
 allPlacements :: [PlacementPolicy]
 allHeuristics :: [(PlacementPolicy, OrderPolicy)]
 type Bin a b = (a, [b])
 emptyBin :: (Num a, Ord a) => a > Bin a b
 emptyBins :: (Num a, Ord a) => a > Int > [Bin a b]
 asBin :: (Ord a, Num a) => a > Measure a b > [b] > Bin a b
 tryAddItem :: (Num a, Ord a) => a > b > Bin a b > Maybe (Bin a b)
 addItem :: (Num a, Ord a) => a > b > Bin a b > Bin a b
 addItems :: (Ord a, Num a) => Bin a b > Measure a b > [b] > Bin a b
 items :: Bin a b > [b]
 gap :: Bin a b > a
 minimizeBins :: (Num a, Ord a) => PlacementPolicy > OrderPolicy > Measure a b > a > [b] > [Bin a b]
 countBins :: (Num a, Ord a) => PlacementPolicy > OrderPolicy > Measure a b > a > [b] > Int
 binpack :: (Num a, Ord a) => PlacementPolicy > OrderPolicy > Measure a b > [Bin a b] > [b] > ([Bin a b], [b])
Types
data PlacementPolicy Source
What placement heuristic should be used?
FirstFit  Traverse bin list from 
ModifiedFirstFit  See above. 
LastFit  Traverse bin list from 
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 worstfitting bin. 
SumOfSquaresFit  Choose bin such that sumofsquares heuristic is minimized. 
data OrderPolicy Source
How to preprocess the input.
AsGiven  Don't modify item order. 
Decreasing  Sort from largest to smallest. 
Increasing  Sort from smallest to largest. 
Feature Enumeration
Lists of all supported heuristics. Useful for benchmarking and testing.
allOrders :: [OrderPolicy]Source
The list of all possible OrderPolicy
choices.
allPlacements :: [PlacementPolicy]Source
The list of all possible PlacementPolicy
choices.
allHeuristics :: [(PlacementPolicy, OrderPolicy)]Source
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.
A Bin
consists of the remaining capacity together with a list of items
already placed.
Create an empty bin.
Create multiple empty bins with uniform capacity.
asBin :: (Ord a, Num a) => a > Measure a b > [b] > Bin a bSource
Turn a list of items into a prefilled bin.
:: (Num a, Ord a)  
=> a  The item's size. 
> b  The item. 
> Bin a b  The bin. 
> Maybe (Bin a b) 

Try placing an item inside a Bin
.
:: (Num a, Ord a)  
=> a  The item's size. 
> b  The item. 
> Bin a b  The bin. 
> Bin a b 

Place an item inside a Bin
. Fails if there is insufficient capacity.
:: (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.
BinPacking Functions
:: (Num a, Ord a)  
=> PlacementPolicy  How to order the items before placement. 
> OrderPolicy  The binpacking 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 
Binpacking 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 suboptimal 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"])]
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] > 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
countBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4] ~~> 3
:: (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 nonuniform and prefilled. 
> [b]  The items. 
> ([Bin a b], [b])  The result; a list of bins and a list of items that could not be placed. 
Binpack a list of items into a list of (possibly nonuniform) 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.