NestingProbleme

NestingProbleme is a family of optimization problems that asks how to arrange a set of items with defined shapes inside a fixed container so as to minimize waste, material use, or production cost. It encompasses 2D nesting, where items are laid out on a sheet, and 3D nesting, involving volume packing. The objective is to place all items without overlap, possibly allowing rotations, flips, or reflections, while respecting boundaries and orientation constraints.

Variants differ by what transformations are allowed, whether guillotine cuts are required, the rigidity of piece shapes, and whether the container is a single sheet or multiple bins. Common goals include minimizing waste area, reducing the number of sheets or bins, or balancing workload in production lines. Some formulations also optimize cut sequences for downstream processing.

NestingProbleme is NP-hard in most nontrivial cases. Exact solutions use integer programming, constraint programming, or geometric decomposition; but practical instances are large, so researchers rely on heuristics and metaheuristics such as greedy packing, genetic algorithms, simulated annealing, and tabu search to obtain good solutions quickly.

Applications span manufacturing and logistics, including textile and garment cutting, sheet metal and wood fabrication, glass and ceramic layout, laser or waterjet cutting, and packaging design. In additive manufacturing, 3D nesting informs efficient build volume usage.

The study of nesting problems has a long history in operations research and computational geometry, with specialized benchmarks and commercial software. Ongoing work focuses on higher-dimensional nesting, non-convex shapes, and integration with production planning and cutting optimization.