Bin Packing
A class of combinatorial optimization problems concerned with packing items of various sizes into a finite number of containers (bins) as efficiently as possible. 2D irregular bin packing is the theoretical basis for nesting software.
What is bin packing?
Bin packing is a family of optimization problems where the goal is to fit a set of items into the minimum number of containers (bins) without exceeding the bin’s capacity.
In the context of nesting and sheet cutting, the “bins” are sheets of material, and the “items” are the parts to be cut. The objective is to minimize the number of sheets consumed (and therefore material cost) while fitting all required parts.
1D, 2D, and 3D bin packing
| Dimension | Application |
|---|---|
| 1D | Cutting linear stock (pipe, bar, timber lengths) to minimize off-cuts |
| 2D rectangular | Packing rectangles (glass panes, circuit boards, standard panels) |
| 2D irregular | Nesting irregular shapes (sheet metal parts, apparel patterns) |
| 3D | Logistics container packing, palletization |
2D irregular bin packing is the form relevant to most cutting shops and is computationally the most complex — it’s an NP-hard problem, meaning no algorithm is guaranteed to find the optimal solution in polynomial time for large instances.
Why bin packing is NP-hard
The number of ways to arrange n parts on a sheet grows factorially with n, and for continuous rotation the search space is infinite. For a job with 50 parts, the theoretical number of distinct arrangements is astronomically large — even the fastest computers cannot evaluate all of them.
In practice, nesting software uses heuristic and metaheuristic algorithms that find good (not necessarily optimal) solutions quickly:
- Greedy heuristics — place parts one by one in order, choosing the locally best position each time. Fast, but often suboptimal.
- Simulated annealing — probabilistic search that accepts some “worse” moves to escape local optima. Good quality/time balance.
- Genetic algorithms — evolve a population of candidate solutions over many generations. The approach used by SVGNest and Deepnest.
- Metaheuristics (proprietary) — combinations of the above, often tuned for specific problem classes. Lapas’s Sparrow engine falls into this category.
Bin packing vs. nesting terminology
In academic literature, the problem is called 2D Irregular Bin Packing or 2D Irregular Strip Packing (when the sheet width is fixed but the length can grow). In industrial settings, the same problem is called nesting or true-shape nesting.
The two terms refer to the same underlying problem.
Ready to try Lapas?
Start free — no credit card