Safe Haskell | Safe-Inferred |
---|
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 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 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.
- 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 worst-fitting bin. |
SumOfSquaresFit | Choose bin such that sum-of-squares heuristic is minimized. |
data OrderPolicy Source
How to pre-process 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 pre-filled 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.
Bin-Packing Functions
:: (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 |
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"])]
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 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.