Approaches to the bin packing problem

By Cutlist Evolution · Updated 29 July 2026

What the problem actually specifies

The parts are rectangles. The sheets are larger rectangles. Every part must end up inside exactly one sheet, no two parts may overlap, and parts sit square to the sheet edges rather than at arbitrary angles. Rotation by ninety degrees is usually allowed, though not always. Grained material and printed stock have a direction, and a part rotated across the grain is scrap.

The objective is to use as few sheets as possible. In practice that is rarely the only objective. A layout that saves half a sheet but leaves twenty unusable slivers is worse than one that uses the same material and leaves a single rectangular offcut you can put back on the rack. Cut count matters too, because every cut is time on a saw and a chance to introduce error.

The problem is NP-hard. In plain terms, no known method finds the guaranteed best answer in reasonable time once the number of parts grows, and the time required climbs faster than the problem does. Twenty parts is tractable. Two hundred is not, at least not exactly. Everything below is a response to that fact.

Heuristics: fast, good enough, and the basis of almost everything

A heuristic follows a sensible rule rather than searching for the best answer. It gives up any guarantee of optimality in exchange for speed, which for most real work is the right trade.

First-Fit and Best-Fit

The simplest approach takes the parts one at a time and places each into the first sheet it fits. That is First-Fit. Best-Fit instead places each part into the sheet where it leaves the least space behind, which tends to keep sheets tightly packed rather than leaving several half-used.

Both improve substantially if the parts are sorted largest first before placement, giving First-Fit Decreasing and Best-Fit Decreasing. The reasoning is intuitive. Large parts are hard to place late, when only awkward gaps remain, whereas small parts will fit almost anywhere. Placing the difficult items while options are still open is worth more than any amount of cleverness later.

These methods run in milliseconds and produce respectable layouts. Their weakness is that every decision is local. A choice that looks best for one part can leave the sheet in a shape that costs two parts later, and the algorithm has no mechanism to notice or reconsider.

Guillotine cuts

Guillotine packing adds a constraint that comes from the machine rather than the mathematics. A guillotine cut runs edge to edge across the material, splitting it into two pieces. Cut those pieces the same way, recursively, and you have a guillotine layout.

This matters because most panel saws and beam saws physically cannot cut any other way. The blade traverses the whole width. A layout containing an L-shaped region that a real saw cannot produce is not a solution, however efficient it looks on screen.

The constraint costs material. A guillotine layout will generally use slightly more sheet than an unconstrained one. It buys a cutting sequence that a machine can actually execute, which is a requirement rather than a compromise.

Shelf algorithms

Shelf methods divide the sheet into horizontal bands. Parts are placed left to right along a shelf until the next one will not fit, at which point a new shelf opens above.

The approach suits parts of similar height, which is why it appears in linear and roll cutting more often than in general panel work. Where heights vary widely it wastes the space above every short part on a tall shelf. It is simple, predictable and fast, and it produces layouts that are trivially guillotine-safe.

Exact methods: the right answer, at a price

Exact methods search until they can prove no better layout exists. When they finish, the answer is not merely good. It is optimal, and you know it.

Integer linear programming

The problem can be written as a set of linear constraints over integer variables, with binary decisions for whether a given part occupies a given position on a given sheet, and constraints forbidding overlap. Commercial and open-source solvers then apply decades of accumulated technique to it.

The formulation is exact and the tooling is mature. The difficulty is that the number of variables grows quickly with the number of parts and the resolution of the coordinate grid, and solve time grows faster still. Integer programming is genuinely useful on small instances, and as a benchmark to measure heuristics against, which is arguably its more valuable role. It is rarely the engine behind a production optimiser handling hundreds of parts.

Dynamic programming

Dynamic programming breaks the problem into subproblems, solves each once and reuses the results. For packing, that usually means computing the best way to fill a region of given dimensions and consulting that answer whenever the same region reappears.

It works well when the material and part sizes come from a small set, which happens more often than you might expect. A workshop cutting standard sheets into a repeating catalogue of components sees the same subproblems constantly. It degrades when dimensions are arbitrary, because the table of stored states grows past anything useful.

Metaheuristics: searching the space of solutions

Metaheuristics sit above the problem. Rather than constructing a layout directly, they explore the space of possible layouts, using a heuristic to evaluate each one and a strategy to decide where to look next. They offer no guarantee, but on hard instances they routinely beat anything constructive.

Genetic algorithms

A genetic algorithm keeps a population of candidate solutions, scores each, and builds the next generation by combining the better ones and introducing random variation. Over many generations the population tends toward stronger layouts.

The encoding matters more than the biology. Represent a layout as an ordering of parts fed to a placement heuristic, and crossover produces valid offspring naturally. Represent it as raw coordinates and most offspring are invalid, so most of the computation is spent repairing them.

Simulated annealing

Simulated annealing starts from one solution and repeatedly makes small changes, accepting improvements always and accepting worse solutions sometimes. The probability of accepting a worse solution falls as the search proceeds.

That willingness to move backwards early is the entire point. A search that only ever improves gets stuck at the first local optimum it reaches, and in packing those are everywhere. Annealing climbs out of them while it is still hot, then settles as it cools.

Particle swarm optimization

Particle swarm methods maintain a population that moves through the solution space, each member steering partly toward its own best result and partly toward the best the group has found. It converges quickly and parallelises well, though on packing problems it tends to need a well-chosen encoding to compete with annealing or an evolutionary approach.

Hybrid approaches

In the published literature, combinations consistently outperform any single method used alone. There is no single recommended recipe. Broadly they fall into two families. In one, a fast constructive method produces a starting layout that a slower search then refines. In the other, an exact method is applied to small or critical subproblems while an approximate method handles the rest.

The appeal is the trade-off. A hybrid can approach the quality of an exact method at a fraction of the cost, which is what makes these approaches practical outside academic work. Where the handover happens, and how each component is tuned, is where most of the engineering effort goes, and it varies considerably with the material, the part mix and the time available.

What this looks like in practice

Software that optimizes cutting layouts hides all of the above behind an interface, which is the correct place for it. The person cutting the material should not have to choose a metaheuristic.

Tools such as Cutlist Evolution and SmartCut take a parts list and a stock list and return a layout, usually in a second or two. What that saves is straightforward. Less material goes in the skip, planning that took half an hour takes seconds, and the cutting instructions that come out are unambiguous enough to hand to someone else or send to a machine.

Two things are worth checking in any optimizer you evaluate. Does it respect the constraints your saw actually has, particularly guillotine cutting and grain direction? And does it publish results against real jobs rather than describing its approach in general terms? Cutting optimization is unusually easy to make claims about and unusually hard to verify, so measurements against a stated set of jobs are worth more than a description of the algorithm.

Final words

The two-dimensional bin packing problem sits where mathematics meets a saw. The theory is genuinely hard, the practical constraints are unforgiving, and the methods that work in production are usually combinations rather than any single technique from a textbook.

For anyone specifying or buying this kind of software, the useful question is not which algorithm a tool uses. It is whether the layouts it produces can be cut on the machine you own, and whether the vendor can show you what happened when it was tried on jobs like yours.