Graph explorer

Relationship: shares method with

Claim: 1D cutting stock and bin packing are closely related members of the same cutting & packing family; both are addressed with pattern/configuration formulations.

Evidence:

B — Survey / tutorial / community

Equivalence:

E3 · structural analogy

Relationship: direct benchmark

Claim: BPPLIB is a direct benchmark providing instances for bin packing and cutting stock problems.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Integer solutions to cutting stock have been reported with branch-and-price, combining column generation with branch and bound.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Gilmore & Gomory (1961) introduced the column-generation (delayed pattern generation) LP approach for the cutting-stock problem.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: 1D cutting stock is formulated as an integer linear program over pattern (cutting-pattern) variables — the Gilmore-Gomory pattern formulation is its basis.

Evidence:

A — Peer-reviewed / official

Relationship: shares method with

Claim: 2D bin packing and strip packing share constructive and exact methods; strip packing often appears as a subproblem when filling a single bin.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: direct benchmark

Claim: 2DPackLib provides standard instances for two-dimensional orthogonal bin packing.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Exact approaches to 2D bin packing have been reported with branch-and-bound (and branch-and-price) formulations.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Exact approaches to 2D bin packing have been reported with column generation / branch-and-price.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: First-fit-decreasing (FFD) style constructive heuristics are widely used for fast approximate bin packing.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: 2D bin packing has also been addressed with metaheuristics such as genetic algorithms.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: 2D bin packing is formulated as an integer linear program (ILP), the starting point for exact methods such as branch-and-bound and branch-and-price.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Exact methods for 2D bin packing prune the search with strong lower bounds, from area bounds to Martello–Toth-style discrete bounds.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: 2D bin packing has also been reported with tabu-search-based search.

Evidence:

B — Survey / tutorial / community

Relationship: shares method with

Claim: Irregular nesting and 2D bin packing belong to the same cutting & packing family and share metaheuristic search methodology.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: generalizes

Claim: Irregular nesting generalizes rectangular strip packing: rectangles are a special case of arbitrary polygons.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: adjacent benchmark

Claim: 2DPackLib is adjacent, not direct: it targets two-dimensional orthogonal (rectangular) cutting and packing, whereas irregular nesting handles arbitrary polygons. Relevant for shared packing methodology but not a like-for-like benchmark.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Bottom-left and bottom-left-fill placement rules are widely used constructive heuristics for irregular nesting layouts.

Evidence:

B — Survey / tutorial / community

Relationship: open-source implementation

Claim: Deepnest is an open-source desktop nesting app built on the SVGnest algorithm.

Evidence:

C — Vendor / case-reported

Relationship: direct benchmark

Claim: ESICUP distributes community instances for irregular (nesting) problems used to compare reported results.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Irregular nesting has been reported with genetic-algorithm-based search over piece sequence and orientation, paired with a placement heuristic.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Containment within the sheet boundary is encoded by the Inner-Fit Polygon, which together with the No-Fit Polygon's overlap test forms the two geometric axes of irregular-nesting placement.

Evidence:

A — Peer-reviewed / official

Relationship: open-source implementation

Claim: libnest2d is an open-source C++ library providing 2D nesting of arbitrary polygons.

Evidence:

C — Vendor / case-reported

Relationship: uses method

Claim: Because the No-Fit Polygon used for overlap testing is computed as a Minkowski sum, irregular nesting directly relies on the Minkowski sum.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: The No-Fit Polygon is the canonical geometric primitive for testing and resolving overlap between two irregular pieces in nesting.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Overlap in irregular placement can also be encoded with phi-functions, an alternative to the No-Fit Polygon that enables nonlinear-programming formulations with continuous rotation.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: RL-based nesting has been reported in recent literature, but its industrial maturity and generalization are not verified here. [unverified — no grade-A source recorded]

Evidence:

D — Expert inference

Relationship: uses method

Claim: Irregular nesting has been reported with simulated-annealing search over piece sequence and orientation, paired with a placement heuristic.

Evidence:

B — Survey / tutorial / community

Relationship: open-source implementation

Claim: SVGnest is an open-source implementation of irregular nesting using No-Fit Polygon placement and a genetic algorithm.

Evidence:

C — Vendor / case-reported

Relationship: uses method

Claim: Irregular nesting has also been reported with tabu-search-based search, using a placement heuristic as the inner loop.

Evidence:

B — Survey / tutorial / community

Relationship: shares method with

Claim: 2D knapsack and bin packing share the orthogonal placement core and many exact/heuristic methods.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: direct benchmark

Claim: 2DPackLib includes two-dimensional orthogonal knapsack instances.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Exact branch-and-bound algorithms have been proposed for the geometric 2D knapsack, using a one-dimensional knapsack relaxation (rectangle areas as weights) as a bound (Caprara & Monaci 2004).

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: 2D knapsack variants have been addressed with dynamic programming and exact/approximate methods built on it.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: 2D knapsack variants have also been addressed with metaheuristics such as genetic algorithms.

Evidence:

B — Survey / tutorial / community

Relationship: generalizes

Claim: 2D knapsack is a two-dimensional generalization of the 1D 0/1 knapsack problem, extending item selection to geometric placement.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: shares method with

Claim: Rectangle strip packing and irregular nesting share placement heuristics (e.g. bottom-left) and sit in the same cutting & packing family; rectangles are the orthogonal special case.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: shares method with

Claim: Strip packing and 2D knapsack share the orthogonal placement core and methodology.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: direct benchmark

Claim: 2DPackLib provides instances directly relevant to two-dimensional orthogonal strip packing.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Bottom-left and bottom-left-fill were introduced for rectangle strip/packing layouts and are standard constructive heuristics here.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Level-based first-fit-decreasing rules (e.g. FFDH) are classic constructive heuristics for strip packing.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Rectangle strip/packing has been addressed with genetic-algorithm search over piece sequence and orientation.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: 2D strip packing is formulated as an integer linear program, the basis for exact methods.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Strip packing has also been reported with simulated-annealing-based search.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Strip packing has also been reported with tabu-search-based search.

Evidence:

B — Survey / tutorial / community

Relationship: generalizes

Claim: 3D bin packing is a higher-dimensional generalization of 2D bin packing and shares many constructive and search methods.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: uses method

Claim: Exact approaches to 3D bin packing / container loading have been reported with branch-and-bound formulations.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Container loading / 3D bin packing has been widely addressed with metaheuristics such as genetic algorithms.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: RL-based 3D packing/loading has been reported recently, but its industrial maturity is not verified here. [unverified]

Evidence:

D — Expert inference

Relationship: industry instance of

Claim: Apparel marker making is a canonical industrial instance of irregular 2D nesting, with grain-line orientation constraints.

Evidence:

B — Survey / tutorial / community

Equivalence:

E1 · same base, different side constraints

Relationship: occurs in

Claim: Marker making is a standard pre-cutting step in apparel manufacturing.

Evidence:

B — Survey / tutorial / community

Relationship: shares method with

Claim: Combining column generation with branch and bound yields branch-and-price, used for exact solutions to integer cutting & packing problems.

Evidence:

A — Peer-reviewed / official

Equivalence:

E2 · shared methodology

Relationship: industry instance of

Claim: Container loading is an industrial instance of 3D bin packing, adding practical constraints such as stability, load bearing, and loading order.

Evidence:

A — Peer-reviewed / official

Equivalence:

E1 · same base, different side constraints

Relationship: occurs in

Claim: Container loading is a core step in logistics and transport.

Evidence:

B — Survey / tutorial / community

Relationship: shares method with

Claim: Deepnest is built on SVGnest's nesting algorithm (per open-source project materials).

Evidence:

C — Vendor / case-reported

Equivalence:

E1 · same base, different side constraints

Relationship: shares method with

Claim: First-fit-decreasing and bottom-left-fill are both constructive placement heuristics that place items one by one under a fixed rule.

Evidence:

B — Survey / tutorial / community

Equivalence:

E3 · structural analogy

Relationship: variant of

Claim: Guillotine cutting is a variant of 2D orthogonal cutting & packing with the added constraint that cuts must be edge-to-edge and straight.

Evidence:

A — Peer-reviewed / official

Equivalence:

E1 · same base, different side constraints

Relationship: shares method with

Claim: Maximizing on a single sheet under the guillotine constraint is the guillotine 2D knapsack, sharing methodology with 2D knapsack.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: shares method with

Claim: Guillotine cutting and strip packing share orthogonal placement methodology.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: adjacent benchmark

Claim: Some orthogonal instances in 2DPackLib relate to guillotine variants, making it an adjacent benchmark.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Exact approaches to guillotine cutting have been reported with branch and bound.

Evidence:

B — Survey / tutorial / community

Relationship: uses method

Claim: Gilmore & Gomory extended the column-generation / pattern-generation approach to two-dimensional guillotine cutting stock.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Guillotine patterns, thanks to their recursive subdivision structure, can be handled efficiently with dynamic programming (Gilmore–Gomory).

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: Guillotine cutting / panel cutting has also been addressed with metaheuristics such as genetic algorithms.

Evidence:

B — Survey / tutorial / community

Relationship: shares method with

Claim: The Inner-Fit Polygon (IFP) gives the region where a piece fits inside the sheet boundary while the No-Fit Polygon (NFP) handles piece-to-piece overlap — complementary geometric primitives that reduce irregular-nesting placement to point-location queries.

Evidence:

A — Peer-reviewed / official

Equivalence:

E2 · shared methodology

Relationship: shares method with

Claim: Integer linear programs are solved exactly by branch-and-bound — ILP is the model that states the problem, branch-and-bound the method that solves it.

Evidence:

A — Peer-reviewed / official

Equivalence:

E2 · shared methodology

Relationship: open-source implementation

Claim: Google OR-Tools provides open-source MIP and CP-SAT solvers for integer linear programs.

Evidence:

C — Vendor / case-reported

Relationship: shares method with

Claim: In cutting-stock column generation the pricing subproblem appears as an (integer) knapsack problem, methodologically linking the two.

Evidence:

A — Peer-reviewed / official

Equivalence:

E3 · structural analogy

Relationship: uses method

Claim: Besides dynamic programming, the 0/1 knapsack problem is also solved exactly by branch and bound.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: The 0/1 knapsack problem can be solved exactly by pseudo-polynomial dynamic programming.

Evidence:

A — Peer-reviewed / official

Relationship: uses method

Claim: The 0/1 knapsack problem is directly formulated as a 0/1 integer linear program with binary variables and a single capacity constraint.

Evidence:

A — Peer-reviewed / official

Relationship: direct benchmark

Claim: OR-Library distributes standard test instances including the knapsack family.

Evidence:

B — Survey / tutorial / community

Relationship: open-source implementation

Claim: Google OR-Tools provides an open-source KnapsackSolver for the 0/1 knapsack problem.

Evidence:

C — Vendor / case-reported

Relationship: shares method with

Claim: Lower-bound computation is the core component that drives pruning in branch-and-bound — the stronger the bound, the more of the search tree it cuts.

Evidence:

A — Peer-reviewed / official

Equivalence:

E2 · shared methodology

Relationship: shares method with

Claim: The No-Fit Polygon of A and B equals the Minkowski sum of A and the reflection (−B); computing the NFP is computing a Minkowski sum.

Evidence:

A — Peer-reviewed / official

Equivalence:

E0 · near-identical formulation

Relationship: variant of

Claim: (Manufacturer's) pallet loading is a structured variant that fills a single area with identical rectangles, close to 2D orthogonal packing.

Evidence:

B — Survey / tutorial / community

Equivalence:

E2 · shared methodology

Relationship: shares method with

Claim: (Manufacturer's) pallet loading — maximizing identical rectangles in a single area — connects to 2D-knapsack-style placement methods.

Evidence:

B — Survey / tutorial / community

Equivalence:

E3 · structural analogy

Relationship: shares method with

Claim: Distributor's pallet loading, which stacks boxes on a pallet, is methodologically connected to container loading and 3D bin packing.

Evidence:

B — Survey / tutorial / community

Equivalence:

E3 · structural analogy

Relationship: uses method

Claim: Exact/constructive approaches to manufacturer's pallet loading have been reported with recursive partitioning and dynamic programming.

Evidence:

C — Vendor / case-reported

Relationship: industry instance of

Claim: Paper roll slitting is an industrial instance of 1D cutting stock and was the real-world motivation behind Gilmore–Gomory's cutting-stock work.

Evidence:

A — Peer-reviewed / official

Equivalence:

E1 · same base, different side constraints

Relationship: occurs in

Claim: Roll slitting is a core step in paper processing.

Evidence:

B — Survey / tutorial / community

Relationship: shares method with

Claim: Phi-functions and the No-Fit Polygon both encode piece-to-piece overlap — the NFP as a combinatorial locus, phi-functions as a continuous analytic expression suited to nonlinear optimization and continuous rotation.

Evidence:

A — Peer-reviewed / official

Equivalence:

E3 · structural analogy

Relationship: industry instance of

Claim: Sheet-metal true-shape nesting is an industrial instance of irregular 2D nesting (vendor-reported framing).

Evidence:

C — Vendor / case-reported

Equivalence:

E1 · same base, different side constraints

Relationship: shares method with

Claim: Sheet-metal true-shape nesting and apparel marker making share the same irregular nesting core and overlapping methodology.

Evidence:

B — Survey / tutorial / community

Equivalence:

E1 · same base, different side constraints

Relationship: commercial tool

Claim: RADAN Radnest is vendor-reported as a true-shape nesting module for sheet-metal fabrication.

Evidence:

C — Vendor / case-reported

Relationship: occurs in

Claim: True-shape nesting is a routine step before sheet-metal cutting.

Evidence:

C — Vendor / case-reported

Relationship: shares method with

Claim: Sheet-metal true-shape nesting and shipbuilding plate nesting are both overlap-free placement of irregular shapes and share placement/search methodology.

Evidence:

B — Survey / tutorial / community

Equivalence:

E1 · same base, different side constraints

Relationship: industry instance of

Claim: Shipbuilding plate nesting is an industrial instance of irregular 2D nesting, adding manufacturability constraints (bevel, kerf, bridge, cutting path).

Evidence:

B — Survey / tutorial / community

Equivalence:

E1 · same base, different side constraints

Relationship: shares method with

Claim: Both reduce to overlap-free placement of irregular shapes and share placement/search methodology, differing mainly in side constraints.

Evidence:

B — Survey / tutorial / community

Equivalence:

E1 · same base, different side constraints

Relationship: occurs in

Claim: Plate nesting is a routine step in shipyard steel production.

Evidence:

C — Vendor / case-reported

Relationship: commercial tool

Claim: SigmaNEST is vendor-reported as supporting true-shape nesting for shipbuilding plate work.

Evidence:

C — Vendor / case-reported

Relationship: shares method with

Claim: Variable-sized bin packing and 1D cutting stock share the structure of choosing among several stock/bin types at minimum cost, and both are addressed with pattern/configuration formulations.

Evidence:

B — Survey / tutorial / community

Equivalence:

E3 · structural analogy

Relationship: variant of

Claim: Variable-sized bin packing is the bin-packing variant with bins of several sizes/costs, minimizing total bin cost rather than bin count — distinguished along the 'bin assortment' dimension of the Wäscher et al. typology.

Evidence:

A — Peer-reviewed / official

Equivalence:

E1 · same base, different side constraints

Relationship: mentions

Claim: The typology classifies 1D cutting stock as an 'input minimization' type with strongly heterogeneous small items.

Evidence:

A — Peer-reviewed / official

Relationship: mentions

Claim: The typology classifies 2D bin packing as an 'input minimization' type — accommodate all items while minimizing the bins used.

Evidence:

A — Peer-reviewed / official

Relationship: mentions

Claim: The typology classifies 2D knapsack as an 'output maximization' type — maximize the value packed into a fixed resource.

Evidence:

A — Peer-reviewed / official

Relationship: occurs in

Claim: Panel cutting is a routine step in furniture manufacturing.

Evidence:

C — Vendor / case-reported

Relationship: industry instance of

Claim: Wood panel cutting is an industrial instance of guillotine cutting because panel saws make edge-to-edge straight cuts.

Evidence:

B — Survey / tutorial / community

Equivalence:

E1 · same base, different side constraints