Bin Packing Problem

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, creating file backup in removable media and technology mapping in Field-programmable gate array semiconductor chip design.

The bin packing problem can also be seen as a special case of the cutting stock problem. When the number of bins is restricted to 1 and each item is characterised by both a volume and a value, the problem of maximising the value of items that can fit in the bin is known as the knapsack problem.

Despite the fact that it is NP-hard, optimal solutions to very large instances can be produced with sophisticated algorithms. In addition, many heuristics have been developed: for example, the first fit algorithm provides a fast but often non-optimal solution, involving placing each item into the first bin in which it will fit. It requires Θ(n log n) time, where n is the number of elements to be packed. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this still does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm. It is known, however, that there always exists at least one ordering of items that allows first-fit to produce an optimal solution.

Read more about Bin Packing ProblemFormal Statement, First-fit Algorithm, Analysis of Approximate Algorithms, Exact Algorithm

Other articles related to "bin packing problem, bins, problems, bin, problem, packing":

Variations - Multiple Knapsack Problem
... This variation is similar to the Bin Packing Problem ... It differs from the Bin Packing Problem that only a subset of items can be selected, whereas, in the Bin Packing Problem, all items have to be packed to certain bins ... This variation is used in many loading and scheduling problems in Operations Research and has an FPTAS ...
Bin Packing Problem - Exact Algorithm
... In, an exact algorithm for the 1-D bin-packing problem has been developed, called MTP ...
Packing - Other Uses
... Backpacking Packing (firestopping), the process of installing backer materials, such as mineral wool in service penetrations Packing (phallus), the practice of wearing a phallic object ...
Circle Packing
... In geometry, circle packing is the study of the arrangement of circles (of equal or varying sizes) on a given surface such that no overlapping occurs and so that all circles touch another ... The associated "packing density", η, of an arrangement is the proportion of the surface covered by the circles ... Generalisations can be made to higher dimensions – this is called sphere packing, which usually deals only with identical spheres ...
Circle Packing Theorem
... Circle packing theorem For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G ...

Famous quotes containing the words problem and/or packing:

    The writer operates at a peculiar crossroads where time and place and eternity somehow meet. His problem is to find that location.
    Flannery O’Connor (1925–1964)

    The good husband finds method as efficient in the packing of fire-wood in a shed, or in the harvesting of fruits in the cellar, as in Peninsular campaigns or the files of the Department of State.
    Ralph Waldo Emerson (1803–1882)