1 Basic concepts

Packing problems ask how a collection of objects can be placed into a space under specified rules so that the arrangement is as efficient as possible. The objects may be physical items, abstract intervals, or geometric shapes, and the available space may be a container, a region, or a set of bins. In many settings, the goal is to fit as many items as possible, use as little space as possible, or achieve the tightest possible arrangement.

1.1 Definition of a packing problem

A packing problem is any optimization problem in which objects must be assigned positions or containers so that they satisfy the admissible placement rules. These rules usually require that objects stay within the available space and avoid illegal overlap or interference. The problem may be discrete, with a finite set of placement choices, or continuous, with positions and orientations chosen from a geometric domain.

1.2 Feasible packings and constraints

A feasible packing is one that satisfies all imposed restrictions. These constraints may limit size, weight, orientation, adjacency, symmetry, or capacity. In geometric cases, non-overlap is central; in resource-allocation settings, feasibility often depends on whether the total demand assigned to a container stays within its limit. Additional constraints can make the search space much smaller, but they also increase complexity.

1.3 Objective functions

The objective function expresses what counts as a good packing. Some problems seek the greatest number of items placed, while others focus on the smallest number of containers used or the highest spatial efficiency. The choice of objective strongly affects both the model and the methods used to solve it.

1.3.1 Maximizing utilization

Maximizing utilization means filling the available space as completely as possible. This can involve placing more items in a fixed container or increasing the fraction of volume, area, or length that is occupied. Utilization is common in logistics, storage, and cutting applications.

1.3.2 Minimizing number of containers

In many packing problems, items must be distributed among identical containers, and the task is to use as few containers as possible. This formulation appears in bin packing and related allocation problems. It is especially important when each container has a cost or when the number of available containers is limited.

1.3.3 Maximizing packing density

Packing density measures how much of the available space is occupied by the packed objects. High density is especially significant in geometric packing, where the arrangement itself is studied for its tightness and regularity. Dense packings are often compared using ratios that relate occupied measure to total available measure.

1.4 Types of objects and spaces

Packing models differ according to the objects being placed and the geometry of the space. Objects may be identical or varied, rigid or flexible, and may allow rotation or only fixed orientation. The ambient space may be one-dimensional, planar, three-dimensional, or more abstract, such as a graph or network. These distinctions determine the appropriate mathematical tools and the difficulty of the problem.

2 Classical variants

Classical packing variants are often grouped by dimension and by the nature of the objects involved. Some arise from practical allocation tasks, while others are studied for their theoretical structure. Although these problems look different on the surface, many share common ideas such as capacity limits, feasibility testing, and optimization under constraints.

2.1 One-dimensional packing

One-dimensional packing concerns intervals or quantities arranged along a line. The most familiar examples involve assigning items to bins, choosing a subset of objects under a capacity limit, or cutting a large resource into smaller parts. Because the structure is simpler than in higher dimensions, many one-dimensional models have been studied intensively.

2.1.1 Bin packing

Bin packing asks how to place items of given sizes into the fewest bins of fixed capacity. Each item must be assigned to exactly one bin, and the total size in any bin cannot exceed its limit. The problem is a standard benchmark in combinatorial optimization and has many practical variants.

2.1.2 Knapsack problem

The knapsack problem selects a subset of items whose total weight does not exceed a capacity while maximizing total value. Unlike bin packing, which emphasizes distribution among containers, knapsack centers on choosing which objects to include at all. It is one of the most studied optimization problems in computer science.

2.1.3 Cutting stock problem

The cutting stock problem asks how to cut large stock material into smaller pieces while meeting demand and reducing waste. It is closely related to one-dimensional bin packing, but it is often framed in manufacturing terms. The main challenge is to choose cutting patterns that use material efficiently.

2.2 Two-dimensional packing

Two-dimensional packing studies the placement of shapes in a plane. It appears in layout design, fabrication, and scheduling analogues where rectangles, circles, or irregular figures must be arranged without overlap. Rotations, boundaries, and shape interactions make these problems substantially more complex than one-dimensional versions.

2.2.1 Rectangle packing

Rectangle packing places rectangles within a larger rectangle or another planar region. The task may allow rotations or may fix the orientation, depending on the application. This variant is important in image layout, board cutting, and container planning.

2.2.2 Circle packing

Circle packing concerns arranging circles so they do not overlap and fit as tightly as possible within a given region. The problem has a rich geometric theory because circles are highly symmetric, yet the optimal arrangement can still be difficult to determine. Circle packing also connects to pattern formation and extremal geometry.

2.2.3 Irregular shape packing

Irregular shape packing involves objects with nonstandard outlines, such as polygons or free-form silhouettes. These problems are common in industrial nesting, where parts must be cut from sheet material with minimal waste. The irregular geometry makes collision detection and placement search especially demanding.

2.3 Three-dimensional packing

Three-dimensional packing extends the same ideas to volumes. Here, boxes, spheres, and containers must be arranged in space with attention to orientation, stability, and accessibility. The added dimension greatly expands the number of possible placements and increases computational difficulty.

2.3.1 Box packing

Box packing places rectangular solids into a larger volume. It is used in shipping, warehouse organization, and fabrication planning. Variations may permit rotation, stacking, or the grouping of multiple item types.

2.3.2 Sphere packing

Sphere packing studies how spheres can be arranged in three-dimensional space with the highest possible density. This is one of the most famous problems in geometry, with deep links to symmetry and spatial efficiency. It also serves as a model for particles, bubbles, and idealized material structures.

2.3.3 Container loading

Container loading asks how to arrange cargo items inside a transport container while respecting size, weight, and stability limits. Practical versions often include loading order, fragile goods, and accessibility constraints. The objective is usually to maximize the value or volume of shipped goods while maintaining safe placement.

2.4 Graph and network packing

Packing ideas also appear in graphs and networks, where the objects to be arranged are edges, paths, or substructures rather than geometric bodies. In this setting, feasibility is defined by combinatorial rules, such as whether selected components share endpoints or violate network constraints. These problems are often studied through matching, cover, and decomposition techniques.

2.4.1 Edge packing

Edge packing selects edges so that the chosen set satisfies a specified non-interference condition. Depending on the model, this may mean that edges are disjoint, nearly disjoint, or arranged under a structural restriction. Such problems are useful in network design and resource assignment.

2.4.2 Matching-based packing

Matching-based packing uses matchings as the basic building blocks of a packing model. A matching is a set of pairwise non-adjacent edges, so it naturally represents a feasible non-overlapping selection. Matching formulations often serve as simplified or specialized versions of broader packing problems.

3 Mathematical formulation

Packing problems are usually written as optimization models with decision variables, feasibility constraints, and an objective function. The exact formulation depends on whether the problem is discrete or geometric, but the general structure is similar across many variants. Mathematical models help clarify the problem and support exact or approximate solution methods.

3.1 Decision variables

Decision variables describe the placement or assignment choices. They may indicate whether an object is placed in a container, which position it occupies, or whether a pair of objects overlaps. In geometric models, variables often include coordinates and orientations, while in combinatorial models they are commonly binary or integer.

3.2 Constraints

Constraints enforce the rules of the packing task. They may limit how much can be assigned, require that objects remain separate, or restrict the allowable positions and transformations. Good formulations balance accuracy with computational tractability.

3.2.1 Capacity constraints

Capacity constraints ensure that no container or resource exceeds its permitted limit. These are common in bin packing, knapsack-type models, and loading problems. The constraints are often written as inequalities involving total size, weight, volume, or another measure of demand.

3.2.2 Non-overlap constraints

Non-overlap constraints prevent objects from occupying the same space or conflicting in a network structure. In geometric settings, this means that shapes must be placed so that their interiors do not intersect. These conditions are central to the validity of the packing.

3.2.3 Geometric constraints

Geometric constraints regulate positions, rotations, boundary contact, and relative placement. They can include alignment rules, symmetry restrictions, or stability requirements. Because geometry is continuous, these constraints often make the problem much harder to solve exactly.

3.3 Optimization criteria

Optimization criteria quantify what the model is trying to improve. Common criteria include minimizing unused space, minimizing the number of bins, maximizing total packed value, or maximizing density. Some models use multiple criteria, either in sequence or with weighted priorities.

3.4 Integer programming models

Integer programming provides a common framework for packing problems, especially when decisions are discrete. Binary variables can represent assignment choices, while additional inequalities encode capacity and non-overlap restrictions. Many practical formulations rely on mixed-integer programming, which combines integer and continuous variables.

4 Computational complexity

Packing problems are frequently difficult from a computational standpoint. Even when the rules appear simple, the number of possible placements or assignments can grow rapidly with the input size. As a result, many packing variants are computationally intractable in the worst case.

4.1 NP-hardness of packing problems

A large number of packing problems are NP-hard, meaning that no efficient algorithm is known for solving all instances exactly. This hardness reflects the combinatorial explosion of possibilities, especially when choices must be made among many possible assignments or placements. NP-hardness is a major reason why heuristic and approximation methods are widely used.

4.2 Approximation and inapproximability

Approximation algorithms produce solutions that are guaranteed to be close to optimal within a stated ratio or bound. For some packing problems, such guarantees are possible and highly valuable. Other variants are difficult to approximate well, and inapproximability results show that no algorithm can achieve certain performance thresholds unless major complexity-theoretic assumptions fail.

4.3 Exact algorithms

Exact algorithms seek provably optimal solutions. They are typically effective only for small or moderately sized instances, but they provide valuable benchmarks and can solve structured cases efficiently. Their design usually relies on systematic exploration combined with pruning or decomposition.

4.3.1 Branch and bound

Branch and bound explores the search space by splitting it into subproblems and discarding regions that cannot beat the current best solution. Bounds on the objective help eliminate large parts of the tree early. This method is widely used in packing because it can handle discrete choices effectively.

4.3.2 Dynamic programming

Dynamic programming builds solutions from overlapping subproblems and is especially useful in one-dimensional or highly structured packing models. It can exploit additive properties of capacities or item values. However, its state space may become too large for complex instances.

4.3.3 Constraint programming

Constraint programming represents the problem through variables, domains, and logical restrictions, then searches for assignments that satisfy all constraints. It is particularly effective when the structure includes many explicit rules, such as non-overlap or placement conditions. Propagation techniques can reduce the search space significantly.

4.4 Heuristic algorithms

Heuristic algorithms aim for good solutions without guaranteeing optimality. They are favored when the problem size is large or exact methods are too slow. Many practical packing systems depend on heuristics because they provide usable answers quickly.

4.4.1 Greedy methods

Greedy methods place items one at a time according to a local rule, such as largest-first or best-fit. They are simple to implement and often produce reasonable packings. Their main limitation is that early choices may block better arrangements later.

Local search starts from an initial arrangement and improves it through small modifications. Typical moves include swapping items, shifting positions, or repacking a subset. This approach can refine a feasible solution substantially, especially when combined with a strong initial heuristic.

4.4.3 Metaheuristics

Metaheuristics are higher-level search strategies designed to escape local optima. Examples include simulated annealing, tabu search, and genetic algorithms. They are widely used in packing because they can balance exploration and exploitation across a large search space.

5 Geometric packing theory

Geometric packing theory studies the arrangement of shapes in space from a mathematical perspective. It asks which configurations are densest, which arrangements are periodic, and how packing quality can be bounded. The subject has deep connections to geometry, number theory, and discrete mathematics.

5.1 Dense packings

Dense packings maximize the proportion of space occupied by objects. They often exhibit strong regularity, especially when the shapes are congruent and symmetric. Dense arrangements are studied both as idealized mathematical objects and as models for physical structure.

5.2 Packing density and efficiency

Packing density measures the ratio of occupied space to total space in a given arrangement. Efficiency is a broader notion that may also account for shape handling, ease of construction, or robustness under perturbation. In applications, a packing with slightly lower density may still be preferred if it is easier to compute or implement.

5.3 Lattice packings

Lattice packings place object centers at points of a regular repeating grid. They are analytically tractable and often serve as a baseline for comparison. Because of their periodic structure, lattice packings are central in the study of highly ordered geometric arrangements.

5.4 Non-lattice packings

Non-lattice packings do not require the centers of objects to follow a periodic grid. They can sometimes achieve greater density than lattice packings. These packings are important because they show that optimal arrangements need not always be regular or repeating.

5.5 Packing bounds and extremal results

Packing bounds limit how dense or efficient a packing can be. Extremal results identify the best possible arrangements under specified conditions. Such theorems are valuable because they distinguish what is achievable from what is merely feasible.

6 Applications

Packing problems arise wherever limited space or capacity must be used effectively. They appear in industrial production, transportation, computing, and communication systems. In many cases, the same mathematical ideas adapt to very different practical contexts.

6.1 Manufacturing and cutting

Manufacturing uses packing models to cut materials into parts with minimal waste. Examples include sheet metal nesting, textile cutting, and allocation of raw stock. Good packings reduce material loss and improve production efficiency.

6.2 Logistics and freight loading

Logistics relies on packing to organize goods in trucks, pallets, ships, and storage facilities. Efficient loading can reduce transport cost and increase throughput. Practical systems often need to consider size, weight, delivery order, and handling constraints.

6.3 Memory and resource allocation

In computing, packing analogies appear in memory allocation, task assignment, and storage organization. Resources must be distributed among competing demands while avoiding fragmentation or overload. These problems are frequently modeled with bin-like structures or capacity limits.

6.4 Telecommunications and scheduling

Telecommunications and scheduling use packing concepts to assign limited channels, time slots, or frequency bands. The goal is to place compatible demands so they do not interfere. Although the setting is abstract, the mathematical structure resembles classical packing in many respects.

6.5 Data compression and storage

Data compression and storage can involve packing information densely into limited space. While the methods are not always geometric, the same principle of efficient fitting applies. Encoding schemes and storage layouts often seek to minimize wasted capacity.

Packing problems belong to a wider family of optimization questions that share similar constraints or objectives. Covering, partitioning, scheduling, and tiling often differ in their direction of fit or in the nature of the feasible arrangement. Studying these relationships helps clarify why certain methods transfer across problem types.

7.1 Covering problems

Covering problems ask how to use selected objects to fill or dominate a target region. Unlike packing, which avoids overlap and focuses on fitting objects inside a space, covering emphasizes complete coverage. The two notions are complementary and are often studied together.

7.2 Partitioning problems

Partitioning problems divide a set or region into disjoint parts under specified rules. They resemble packing because both require assigning elements without conflict. The main difference is that partitioning typically uses all elements, whereas packing may select only a subset.

7.3 Scheduling analogues

Scheduling analogues treat time as the resource being packed. Jobs, tasks, or operations must be assigned to time intervals or processors without conflict. Many scheduling problems can be recast as packing questions with capacity and overlap constraints.

7.4 Tiling and tessellation

Tiling and tessellation arrange shapes to cover a region without gaps or overlaps. They are closely related to packing, though tiling usually requires complete coverage rather than partial occupancy. In geometric theory, the boundary between packing and tiling is often mathematically significant.

8 Historical development

The study of packing has developed across geometry, optimization, and computation. Early work focused on classical shape arrangements and density questions, while later research connected packing to algorithms and complexity theory. Modern studies combine theory with practical methods for large-scale applications.

8.1 Early geometric packing results

Early geometric packing results examined how circles, spheres, and other shapes could be arranged as tightly as possible. These questions were pursued in classical mathematics and often led to elegant symmetry-based solutions. They helped establish packing as a core topic in discrete geometry.

8.2 Development in combinatorial optimization

Packing became a central subject in combinatorial optimization as researchers began studying bin packing, knapsack, and cutting stock problems. This shift connected geometric intuition with algorithmic modeling. The field developed a rich set of approximation methods, exact procedures, and complexity results.

8.3 Modern algorithmic approaches

Modern approaches combine integer programming, constraint solving, heuristics, and hybrid methods. Advances in computation have made it possible to solve larger and more realistic instances than before. Current research often focuses on balancing optimality, speed, and flexibility in applications.