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.

Complexity and why optimal solutions are impractical

2D irregular bin packing is NP-hard — meaning no polynomial-time algorithm is known that guarantees the optimal solution. For a job with n parts:

The number of orderings to try is n! (factorial)
Each ordering can be placed in infinite ways due to continuous position and rotation
For n = 20, the search space is already larger than the number of atoms in the observable universe

In practice this means:

Nesting software never guarantees the optimal solution — it finds good solutions within a time budget
Better algorithms and more compute time produce better (but not perfect) results
For most production jobs, “near-optimal” is commercially sufficient — the gap between a good heuristic and the true optimum is typically 3–8% in utilization

Algorithm families

Greedy bottom-left placement

The simplest approach: sort parts by area (largest first), then place each part at the lowest, leftmost valid position on the sheet. Fast — O(n²) complexity — but often leaves irregular gaps and achieves 60–75% utilization on typical jobs.

Bottom-left fill (BLF) variants

Improvements on basic greedy placement that try multiple candidate positions and pick the one minimising some criterion (wasted area below, height of bounding box, etc.). Still runs in polynomial time; achieves 70–82% utilization.

Genetic algorithm (GA)

A population of candidate solutions (part orderings and orientations) evolves over generations. Good solutions are combined and mutated; poor solutions are discarded. The approach used by SVGNest and Deepnest.

Strong at escaping local optima
Quality improves with more generations (runtime)
Sensitive to population size and mutation rate tuning
Typically reaches 80–90% utilization given sufficient time

Simulated annealing (SA)

A single solution is modified iteratively. “Worse” modifications are accepted with decreasing probability over time (the “temperature” schedule), allowing escape from local optima. Well-suited for nesting because it naturally handles the continuous nature of placement.

Metaheuristics (hybrid approaches)

Modern nesting engines combine multiple approaches: using GA for high-level part ordering, NFP-based placement for collision-free positioning, and local search to refine results. Lapas’s Sparrow engine falls into this category.

Practical implications for shops

More parts = better utilization potential. The optimizer has more combinations to work with. A job with 200 parts generally achieves higher utilization than a job with 5 parts of the same geometry, because there are more interlocking combinations available.

Part variety helps. Mixed-size jobs let the optimizer fill gaps with smaller parts. Homogeneous jobs (many identical parts) are harder to pack efficiently because the parts can’t interlock with themselves (unless they’re concave and complementary).

Run time vs. quality tradeoff. Giving the optimizer more time always produces equal-or-better results. For expensive material (steel, aluminium, carbon fibre), running the deep optimizer for an extra 2 minutes to gain 3% utilization translates to real material savings.

FAQ

If bin packing is NP-hard, how does nesting software produce results quickly?

It uses approximation algorithms (heuristics) that sacrifice the guarantee of optimality in exchange for practical runtime. A heuristic that runs in 10 seconds and finds a solution 5% worse than optimal is far more useful in production than an exact algorithm that would take years.

Does running the optimizer longer always give better results?

For metaheuristic approaches (GA, SA, hybrid), yes — more iterations means more of the search space explored, which generally improves solution quality. There are diminishing returns: the first 30 seconds of optimization capture most of the gain, and the next 5 minutes might only improve utilization by another 1–2%. Lapas shows live utilization as it improves so you can stop when you’re satisfied.

What’s the difference between strip packing and bin packing?

In bin packing, the number of bins (sheets) is minimized — the sheet dimensions are fixed and you want to use as few sheets as possible. In strip packing, the sheet width is fixed but the length (height) is minimized — you want the smallest strip that fits all parts. Most practical nesting solvers treat the problem as bin packing with fixed sheet dimensions.