-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Common bin-packing heuristics.
--
-- An implementation of the first-fit, modified-first-fit, last-fit,
-- best-fit, sum-of-squares-fit, worst-fit, and almost-last-fit bin
-- packing heuristics. Items can be packed in order of both decreasing
-- and increasing size (and, of course, in unmodified order).
--
-- The module supports both the standard (textbook) minimization problem
-- (How many bins do I need?) and the more practical fitting
-- problem (I've got n bins; which items can I take?).
--
-- The API is simple and the module is documented with Haddock (complete
-- with examples). The implementation of the above-mentioned heuristics
-- is complete and partially tested with QuickCheck. However, note that
-- speed has not been a primary concern to date.
--
-- Patches and feedback are very welcome.
@package Binpack
@version 0.4
-- | 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:
--
--
-- - 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.
-- - Take the list of bins created in Step 1 and reverse it.
-- - 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.
-- - Reverse the list of bins again.
-- - 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.
--
module Data.BinPack
-- | What placement heuristic should be used?
data PlacementPolicy
-- | Traverse bin list from head to last and place item in
-- the first bin that has sufficient capacity.
FirstFit :: PlacementPolicy
-- | See above.
ModifiedFirstFit :: PlacementPolicy
-- | Traverse bin list from last to head and place item in
-- the first bin that has sufficient capacity.
LastFit :: PlacementPolicy
-- | Place item in the bin with the most capacity.
BestFit :: PlacementPolicy
-- | Place item in the bin with the least (but sufficient) capacity.
WorstFit :: PlacementPolicy
-- | Choose the 2nd to worst-fitting bin.
AlmostWorstFit :: PlacementPolicy
-- | Choose bin such that sum-of-squares heuristic is minimized.
SumOfSquaresFit :: PlacementPolicy
-- | How to pre-process the input.
data OrderPolicy
-- | Don't modify item order.
AsGiven :: OrderPolicy
-- | Sort from largest to smallest.
Decreasing :: OrderPolicy
-- | Sort from smallest to largest.
Increasing :: OrderPolicy
-- | 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 Measure a b = b -> a
-- | The list of all possible OrderPolicy choices.
allOrders :: [OrderPolicy]
-- | The list of all possible PlacementPolicy choices.
allPlacements :: [PlacementPolicy]
-- | All supported ordering and placment choices.
allHeuristics :: [(PlacementPolicy, OrderPolicy)]
-- | A Bin consists of the remaining capacity together with a list
-- of items already placed.
type Bin a b = (a, [b])
-- | Create an empty bin.
emptyBin :: (Num a, Ord a) => a -> Bin a b
-- | Create multiple empty bins with uniform capacity.
emptyBins :: (Num a, Ord a) => a -> Int -> [Bin a b]
-- | Turn a list of items into a pre-filled bin.
asBin :: (Ord a, Num a) => a -> Measure a b -> [b] -> Bin a b
-- | Try placing an item inside a Bin.
tryAddItem :: (Num a, Ord a) => a -> b -> Bin a b -> Maybe (Bin a b)
-- | Place an item inside a Bin. Fails if there is insufficient
-- capacity.
addItem :: (Num a, Ord a) => a -> b -> Bin a b -> Bin a b
-- | Add a list of items to an existing bin. Fails if there is insufficient
-- capacity.
addItems :: (Ord a, Num a) => Bin a b -> Measure a b -> [b] -> Bin a b
-- | Get the items in a bin.
items :: Bin a b -> [b]
-- | Get the remaining capacity of a bin.
gap :: Bin a b -> a
-- | 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])]
--
minimizeBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> [Bin a b]
-- | 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
--
countBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> Int
-- | 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.
binpack :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> [Bin a b] -> [b] -> ([Bin a b], [b])
instance Show PlacementPolicy
instance Eq PlacementPolicy
instance Ord PlacementPolicy