MATHEMATICAL PROBLEM ENCYCLOPEDIA · BPP

One-dimensional Bin Packing Problem

minimize bins while every item is assigned and each bin respects capacity

Canonical objectivemin z = Σᵦ yᵦ

ORIGIN

Historical context

Classical bin packing developed a rich approximation and worst-case analysis lineage around packing indivisible items into identical-capacity bins.

SIGNIFICANCE

Why this problem matters

It is the simplest reusable model of capacity consolidation and a component of scheduling, cloud placement and logistics.

container consolidation
memory and server placement
cutting and stock allocation

FORMULATION

One bounded canonical mathematical model

This formulation is a governed representative model. Variant assumptions must be declared before results are compared.

Variable	Domain	Meaning
`xᵢᵦ`	`{0,1}`	1 when item i is assigned to bin b.
`yᵦ`	`{0,1}`	1 when bin b is opened.

Σᵦ xᵢᵦ = 1 ∀ item i
Indexed feasibility condition applied to every entity covered by the stated index.
Σᵢ wᵢxᵢᵦ ≤ C yᵦ ∀ bin b
Indexed feasibility condition applied to every entity covered by the stated index.
xᵢᵦ,yᵦ ∈ {0,1}
Binary decision-variable domain; each indexed choice is either inactive or active.

COMPLEXITY

Strongly NP-hard

Tractable frontier. Pseudo-polynomial or fixed-parameter methods exist under bounded capacities or item types.

Hardness driver. Many near-capacity combinations compete for a minimum number of bins.

STATE OF THE ART

Methods and certificates

Exact. Branch-and-price, arc-flow, subset-sum based branch and bound.

Bounds. Continuous capacity, dual-feasible functions and pattern LP bounds.

Heuristics. First-fit decreasing, best-fit and local or evolutionary improvement.

Computational boundary. Hardness depends on item-size distribution and dominance, not only number of items.

BENCHMARKS

Reproducible test families

Falkenauer and Scholl families
OR-Library bin packing

OPEN QUESTIONS

Research frontier

Certified high-throughput online packing
Robust packing with uncertain item sizes

PRIMARY LITERATURE

Sources and evidence boundary

Curated technical synthesis with explicit evidence boundaries. No universal largest exactly solvable instance or undated best-known value is asserted. Numerical claims require a versioned instance, solver contract and reproducible certificate.

J. E. Beasley (1990). OR-Library. PRIMARY_SOURCE_VERIFIED

Return to the problem registry