Bin Packing Heuristics

The Bin Packing (BP) problem is one of the more celebrated members of the class of problems commonly titled “combinatorial optimization”. Other famous ones are machine scheduling, the knapsack problem, job assignment, the traveling salesman itinerary and many more. Practically all of these problems may be viewed as special cases of integer programming, but they display special structure and characteristics which have led to specialized algorithms and approaches. While the fame of the BP problem derives to no little extent from its being simple to present and relatively easy to analyze, the significance of many others of this class of problems derives from their commercial value in a business environment; hence the great interest in them. Karp (1986) gives a sweeping overview of the field.