Bin Packing

A Rust-first cut list and bin packing optimization library for one-dimensional cutting stock (linear bar / pipe stock), two-dimensional rectangular sheet stock, three-dimensional box packing, and irregular nesting problems. The crate uses #![forbid(unsafe_code)], widened integer dimensions for regular packing, and explicit floating-point tolerances for irregular geometry. It is serde-friendly so problems and solutions travel cleanly across process boundaries and language bindings.

• Core crate: crates/bin-packing — published to crates.io as bin-packing.
• Node.js bindings: bindings/node — published to npm as @0xdoublesharp/bin-packing, powered by napi-rs.
• WebAssembly bindings: bindings/wasm — published to npm as @0xdoublesharp/bin-packing-wasm, powered by wasm-bindgen. Targets browsers and Node.js; other WASM hosts may need loader configuration.
• Fuzz targets: fuzz/ — libFuzzer harnesses for the 1D, 2D, and 3D entry points.

Features

Version 0.6.1 refreshes dependency security fixes, native package READMEs, and release tooling. The solver APIs and packing models are unchanged.

See the v0.6.1 release notes for changes and compatibility notes. The testing guide explains validation and coverage.

Native geometry, physical rules and explicit objectives

• Irregular nesting: concave polygons, holes, circular arcs, rigid components, irregular bins/defects, rotations, reflection and spacing.
• Staged cutting: physical cut trees, stage limits, cut modes, cut spacing/counts, defects, trims, kerf and production groups.
• Stack loading: compatible upright columns, nesting, stack/weight/density limits, payload, exact axle reactions and unloading groups.
• Explicit objectives: material cost, profit/knapsack, feasibility and open dimensions across regular and physical models.

These APIs are native Rust and available through Node.js and WebAssembly. The optional irregular feature uses safe Rust geometry. PackingSolver supplies reference algorithms and benchmark workloads; no C++ backend is required. Each model documents its supported bounds, geometric approximation and search limits. Independent validators check source identity and physical results.

1D cutting stock

• Multi-stock support. Mix any number of stock dimensions with independent length, kerf, trim, cost, and optional inventory available caps.
• Kerf and trim modeling. Each layout deducts trim from usable length and charges kerf between adjacent cuts, so results match physical cut lists.
• Inventory-aware procurement. When stock has available caps, the solver returns both the capped solution and a relaxed-inventory estimate so you can see per-stock used_quantity, required_quantity, and additional_quantity_needed.
• Multi-objective ranking. Solutions are compared lexicographically by (unplaced, stock_count, total_waste, total_cost, !exact) so better heuristic candidates win automatically in Auto mode.
• Lower bounds. The column-generation backend reports a certified LP or conservative length bound and marks the solution exact = true when full pattern enumeration and integer search establish the optimum.
• Structured errors. Public boundary validation fails fast with typed BinPackingError variants instead of panics.

3D box packing

• Multi-bin support. Mix any number of bin types with independent width, height, depth, cost, and optional quantity caps.
• Per-item rotation control. Each demand has an allowed_rotations bitmask over the six axis-permutation orientations of (w, h, d). RotationMask3D::ALL allows all six; RotationMask3D::UPRIGHT permits only the two orientations that keep the declared y axis vertical.
• 29-algorithm catalog. Includes Extreme Points (6 scoring variants), Guillotine 3D beam search (7 variants), horizontal layer-building (5 inner-2D backends), Bischoff & Marriott vertical wall-building, column / stack building, Deepest-Bottom-Left and DBLF, volume-sorted FFD/BFD, Multi-start, GRASP, and Local Search meta-strategies, plus a restricted Martello-Pisinger-Vigo branch-and-bound exact backend.
• Same ranking contract. Solutions are compared lexicographically by (unplaced, bin_count, total_waste_volume, total_cost), so Auto mode always returns the best candidate.
• Dimension safety. Per-axis dimensions are capped at 1 << 15 (MAX_DIMENSION_3D) so that w × h × d never overflows u64.

2D rectangular packing

• Multi-sheet support. Mix any number of sheet types with independent width, height, cost, and optional quantity caps.
• Per-item rotation control. Each demand has its own can_rotate flag; the solver enumerates the legal orientations per item.
• Guillotine mode. guillotine_required = true restricts the Auto strategy to guillotine-compatible constructions and sets TwoDSolution.guillotine on the result.
• Kerf-aware packing. Each sheet type accepts an optional kerf gap (in the same units as the sheet dimensions). The solver enforces the gap between every pair of adjacent placements (factory edges are free; only internal cuts consume kerf). The solution reports kerf_area per layout and total_kerf_area across all sheets.
• Edge kerf relief. Set Sheet2D.edge_kerf_relief = true to allow a trailing placement to extend up to one kerf past the sheet boundary, modeling a blade that exits the stock. Parts must still fit within the declared sheet dimensions.
• Multistart search. A randomized MaxRects meta-strategy (multi_start) permutes input orderings under a reproducible seed.
• Rotation search. Exhaustive (or sampled) rotation assignment search (rotation_search) enumerates all 2^k rotation assignments for k rotatable demand types, finding globally better rotation choices than greedy per-placement rotation.
• Usable-drop consolidation. Set TwoDOptions.min_usable_side to filter out narrow leftover strips that are too small to reuse. The solver reports SheetLayout2D.largest_usable_drop_area (largest maximal free rectangle meeting the threshold on that sheet), SheetLayout2D.sum_sq_usable_drop_areas (sum of squares of all qualifying drops on that sheet), and aggregates across the solution as TwoDSolution.max_usable_drop_area (the MAX over all layouts, not the sum) and TwoDSolution.total_sum_sq_usable_drop_areas (saturating sum across layouts). Candidates that are equal on waste and cost are tiebroken in favour of larger / more consolidated drops; this tiebreaker sits AFTER total_waste_area and total_cost so waste and cost always dominate.
• Integer-safe math. Dimensions are widened to u64 before area calculations; u32 * u32 on dimensions is forbidden by the workspace lint policy.

Cut plans

After solving, you can generate an ordered cut plan for any OneDSolution or TwoDSolution. The cut planner is a pure post-processor — it reads a finished layout and emits a per-bar or per-sheet sequence of CutSteps optimized for a chosen shop cost model. The solver is not re-run.

Entry points:

• bin_packing::one_d::cut_plan::plan_cuts(&problem, &solution, &options) -> Result<CutPlanSolution1D, CutPlanError>
• bin_packing::two_d::cut_plan::plan_cuts(&solution, &options) -> Result<CutPlanSolution2D, CutPlanError>

Presets: ChopSaw in 1D; TableSaw, PanelSaw and CncRouter in 2D. The generated preset costs are resolved by the actual planning APIs and checked before publication.

Any cost field on the options struct overrides the preset default. Pass ..CutPlanOptions2D::default() to accept all preset defaults.

Output:

• CutPlanSolution1D — contains bar_plans: Vec<BarCutPlan1D> and a solution-level total_cost. Each BarCutPlan1D carries:
  • steps: Vec<CutStep1D> — ordered Cut and FenceReset steps.
  • total_cost, num_cuts, num_fence_resets.
• CutPlanSolution2D — contains sheet_plans: Vec<SheetCutPlan2D> and a solution-level total_cost. Each SheetCutPlan2D carries:
  • steps: Vec<CutStep2D> — ordered Cut, LineCut, Rotate, FenceReset, ToolUp, ToolDown, and Travel steps.
  • total_cost, num_cuts, num_rotations, num_fence_resets, num_tool_ups, travel_distance.

Total cost is the linear sum: num_cuts * cut_cost + num_rotations * rotate_cost + num_fence_resets * fence_reset_cost + num_tool_ups * tool_up_down_cost + travel_distance * travel_cost.

Errors (CutPlanError, #[non_exhaustive]):

• NonGuillotineNotCuttable { sheet_name } — the layout cannot be expressed as a sequence of full guillotine cuts, and the TableSaw or PanelSaw preset was requested. Switch to CncRouter or re-solve with guillotine_required = true.
• InvalidOptions(String) — a cost field is negative, NaN, or infinite.

Quick example (Rust):

use bin_packing::two_d::{
    RectDemand2D, Sheet2D, TwoDAlgorithm, TwoDOptions, TwoDProblem, solve_2d,
    cut_plan::{CutPlanOptions2D, CutPlanPreset2D, plan_cuts},
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let problem = TwoDProblem {
        sheets: vec![Sheet2D {
            name: "plywood".into(),
            width: 96,
            height: 48,
            cost: 1.0,
            quantity: None,
            kerf: 2,
            edge_kerf_relief: false,
        }],
        demands: vec![
            RectDemand2D { name: "panel-a".into(), width: 24, height: 18, quantity: 4, can_rotate: true },
            RectDemand2D { name: "panel-b".into(), width: 12, height: 12, quantity: 6, can_rotate: true },
        ],
    };

    let solution = solve_2d(problem, TwoDOptions { algorithm: TwoDAlgorithm::Auto, guillotine_required: true, ..Default::default() })?;

    let cut_plan = plan_cuts(
        &solution,
        &CutPlanOptions2D { preset: CutPlanPreset2D::TableSaw, ..Default::default() },
    )?;

    println!("total cut plan cost: {}", cut_plan.total_cost);
    for sheet_plan in &cut_plan.sheet_plans {
        println!("  {}: {} steps, cost {:.2}", sheet_plan.sheet_name, sheet_plan.steps.len(), sheet_plan.total_cost);
    }

    Ok(())
}

Cross-cutting

• Cost-first linear stock. one_d::solve_1d_min_cost (JavaScript solve1dMinCost) can use more bars when doing so reduces material cost. It retains the existing bounded pattern search, inventory and kerf/trim behavior. See cost-first cutting stock.

• Native constrained packing. Additive two_d::constrained and three_d::constrained APIs support physical sheet trims/rectangular defects, carton payload limits, explicit source indices, independent validation, and count-first or cost-first construction. JavaScript exposes solve2dConstrained and solve3dConstrained in Node and dimension-specific WebAssembly builds. See 2D constraints and 3D constraints for limits and semantics.

• Count-bound-aware search. two_d::adaptive::solve_2d_adaptive (JavaScript solve2dAdaptive) can stop once a complete packing meets a conservative geometric lower bound. It certifies sheet count only; ordinary Auto and its secondary ranking remain unchanged. See adaptive search.

• serde round-tripping. Every request, option, solution, and metrics type derives Serialize / Deserialize.

• Reproducibility. All randomized strategies accept a seed; runs with identical seeds and inputs produce identical output.

• Metrics. Each solution carries a metrics block (iterations, explored_states, etc.) plus free-form notes, so callers can surface diagnostics without re-running.

• Benchmarks. Criterion benches live in crates/bin-packing/benches/solver_benches.rs.

• Fuzzing. cargo fuzz run solver_inputs exercises the 1D, 2D, and 3D solvers against randomized inputs.

Algorithms

Selected via OneDOptions.algorithm, TwoDOptions.algorithm, or ThreeDOptions.algorithm. All names below are the exact snake_case strings accepted by serde and the Node / WebAssembly bindings.

3D (ThreeDAlgorithm)

Extreme Points family — maintains a set of extreme points (EPs) and places each item at the EP that scores best under the chosen criterion:

Name	Description
extreme_points	Volume-fit residual scoring (default EP variant).
extreme_points_residual_space	Crainic-Perboli-Tadei "RS" — scores by residual space remaining after placement.
extreme_points_free_volume	CPT "FV" — scores by free volume in the remaining space.
extreme_points_bottom_left_back	Bottom-left-back tiebreaking (place as close to the origin as possible).
extreme_points_contact_point	Score by surface contact with already-placed items or bin walls.
extreme_points_euclidean	CPT "EU" — scores by Euclidean distance of the EP from the bin origin.

Guillotine 3D beam search — recursive three-slab partition with configurable split and ranking rules:

Name	Description
guillotine_3d	Beam search with best-volume-fit ranking.
guillotine_3d_best_short_side_fit	Ranked by the shortest leftover edge after placement.
guillotine_3d_best_long_side_fit	Ranked by the longest leftover edge after placement.
guillotine_3d_shorter_leftover_axis	Split along the axis that leaves the shorter leftover slab.
guillotine_3d_longer_leftover_axis	Split along the axis that leaves the longer leftover slab.
guillotine_3d_min_volume_split	Split to minimise the volume of the new sub-cuboid.
guillotine_3d_max_volume_split	Split to maximise the volume of the new sub-cuboid.

Layer building — packs items into horizontal layers; each layer uses an independent 2D inner backend:

Name	Description
layer_building	Auto inner-2D backend (picks best of MaxRects, Skyline, Guillotine).
layer_building_max_rects	MaxRects inner backend.
layer_building_skyline	Skyline inner backend.
layer_building_guillotine	Guillotine inner backend.
layer_building_shelf	Best-fit-decreasing-height shelf inner backend.

Geometry-based heuristics:

Name	Description
wall_building	Bischoff & Marriott 1990 vertical wall-building: builds planar walls of items from floor to ceiling.
column_building	Vertical stack / column building with 2D footprint packing for column placement.
deepest_bottom_left	Deepest-Bottom-Left (Karabulut & İnceoğlu): place each item at the deepest, then bottom-most, then leftmost feasible position.
deepest_bottom_left_fill	Deepest-Bottom-Left-Fill: adds a fill pass to resolve deadlocks in DBL.
first_fit_decreasing_volume	Sort items by volume descending; assign each to the first bin with space.
best_fit_decreasing_volume	Sort items by volume descending; assign each to the bin with the least remaining volume that still fits.

Meta-strategies:

Name	Description
multi_start	Randomized EP meta-strategy. Runs multistart_runs restarts with shuffled item orderings under seed.
grasp	Greedy Randomized Adaptive Search: RCL-based randomized construction (top-30% by volume) followed by local search improvement.
local_search	Standalone local search seeded from FFD volume. Explores move/rotate/swap neighbourhood with bin-elimination repair.
branch_and_bound	Restricted Martello-Pisinger-Vigo exact backend. Computes conservative-scale lower bounds; returns Unsupported for multi-bin-type, capped, or rotatable (non-XYZ) inputs.
auto (default)	Tiered sweep: tier-1 runs ExtremePoints (3 variants), Guillotine3D, LayerBuilding, and FFD; tier-2 (when multistart_runs > 0) adds MultiStart and LocalSearch. Returns the best result.

Solution ranking for 3D is lexicographic on (unplaced, bin_count, total_waste_volume, total_cost).

1D (OneDAlgorithm)

Name	Description
auto (default)	Runs FFD, BFD, and local search, then optionally escalates to column generation when the instance is small enough (auto_exact_max_types, auto_exact_max_quantity, single uncapped stock). Returns the best candidate.
first_fit_decreasing	Classic FFD: sort cuts by length descending, place each into the first open bin that fits, open a new bin otherwise. O(n²) deterministic.
best_fit_decreasing	BFD: place each sorted cut into the open bin with the tightest fit. Typically uses fewer bins than FFD on mixed sizes.
local_search	Multistart local search seeded from FFD/BFD, with bin-elimination repair. multistart_runs restarts × improvement_rounds swap/move rounds, driven by seed.
column_generation	Exact backend: generates cutting patterns via price-and-solve, refines with pattern search, and runs one capped enumeration pass after at most column_generation_rounds LP/pricing rounds. Reports a certified LP or conservative volume lower bound; exact = true requires complete pattern enumeration and integer search.

2D (TwoDAlgorithm)

MaxRects family — maintains an explicit set of free rectangles, scoring each candidate placement under a different criterion and then splitting / merging free rectangles:

Name	Description
max_rects	Best-area-fit MaxRects (the classic variant).
max_rects_best_short_side_fit	Prefer placements that minimize the shorter leftover edge.
max_rects_best_long_side_fit	Prefer placements that minimize the longer leftover edge.
max_rects_bottom_left	Bottom-left-first tiebreaking.
max_rects_contact_point	Score by perimeter contact with already-placed items or the sheet boundary.

Skyline family — maintains a monotone skyline along one axis:

Name	Description
skyline	Place each item at the lowest feasible skyline segment.
skyline_min_waste	Skyline construction with waste-minimizing candidate ranking, which keeps sub-skyline gaps smaller.

Guillotine beam search — recursive two-stage cuts with a beam-width search front (beam_width) and configurable split / ranking rules:

Name	Description
guillotine	Beam search with default (best-area-fit) ranking and default split.
guillotine_best_short_side_fit	Beam search ranked by shorter leftover edge.
guillotine_best_long_side_fit	Beam search ranked by longer leftover edge.
guillotine_shorter_leftover_axis	Split along the axis that leaves the shorter leftover strip.
guillotine_longer_leftover_axis	Split along the axis that leaves the longer leftover strip.
guillotine_min_area_split	Split to minimize the area of the new sub-rectangle.
guillotine_max_area_split	Split to maximize the area of the new sub-rectangle.

Shelf heuristics — simple fast baselines that stack items into horizontal "shelves" sized by the tallest item on each shelf:

Name	Description
next_fit_decreasing_height	NFDH: open a new shelf as soon as the current one overflows.
first_fit_decreasing_height	FFDH: place each item on the first shelf that fits.
best_fit_decreasing_height	BFDH: place each item on the tightest-fitting shelf.

Meta-strategies:

Name	Description
multi_start	Randomized MaxRects meta-strategy. Runs multistart_runs restarts with permuted item orderings under seed.
rotation_search	Exhaustive (or sampled) rotation assignment search: enumerates all 2^k rotation assignments for k rotatable demand types (or samples multistart_runs random assignments when k exceeds auto_rotation_search_max_types). Each assignment fixes rotations and packs via MaxRects best-area-fit.
auto (default)	Runs MaxRects (best-area, BSSF, BLSF, contact), Skyline and Skyline-min-waste, BFDH, Guillotine BSSF and shorter-leftover-axis, Multistart, and RotationSearch, then returns the best candidate. When guillotine_required is set, only the guillotine variants run.

Solution ranking for 2D is lexicographic on (unplaced, sheet_count, total_waste_area, total_cost, max_usable_drop_area↑, total_sum_sq_usable_drop_areas↑). The two consolidation keys (↑ = prefer larger) only reorder candidates that are already equal on every primary key; waste and cost always win. When guillotine_required is set, auto narrows its candidate set to the guillotine variants — the guillotine constraint is enforced by candidate selection, not by a ranking tie-break, so every candidate auto ranks is already guillotine-compatible.

Rust usage

Add the crate to your Cargo.toml:

[dependencies]
bin-packing = "0.6.1"

The regular dimension modules expose these primary entry points:

• one_d::solve_1d(problem, options) -> Result<OneDSolution>
• two_d::solve_2d(problem, options) -> Result<TwoDSolution>
• three_d::solve_3d(problem, options) -> Result<ThreeDSolution>

All problem and solution types implement serde::Serialize / serde::Deserialize, so the same models are usable from Rust code or wire-format APIs. The crate root re-exports BinPackingError and Result; the regular models come from one_d, two_d, and three_d. The irregular module adds shape nesting; optimization supplies shared objective controls. See the generated reference for features, defaults and binding exports, and the API guide for the added models.

1D cutting stock

use bin_packing::one_d::{
    CutDemand1D, OneDAlgorithm, OneDOptions, OneDProblem, Stock1D, solve_1d,
};

fn main() -> bin_packing::Result<()> {
    let problem = OneDProblem {
        stock: vec![Stock1D {
            name: "96in bar".into(),
            length: 96,
            kerf: 1,
            trim: 0,
            cost: 1.0,
            available: None,
        }],
        demands: vec![
            CutDemand1D { name: "rail".into(), length: 45, quantity: 2 },
            CutDemand1D { name: "brace".into(), length: 30, quantity: 2 },
        ],
    };

    let solution = solve_1d(
        problem,
        OneDOptions {
            algorithm: OneDAlgorithm::Auto,
            ..Default::default()
        },
    )?;

    println!("algorithm: {}", solution.algorithm);
    println!("stock used: {}", solution.stock_count);
    println!("waste: {}", solution.total_waste);
    println!("exact: {}", solution.exact);
    if let Some(bound) = solution.lower_bound {
        println!("lower bound: {bound}");
    }

    for layout in &solution.layouts {
        println!(
            "{}: used {} / {}",
            layout.stock_name, layout.used_length, layout.stock_length
        );
    }

    for requirement in &solution.stock_requirements {
        println!(
            "{}: used {}, required {}, additional {}",
            requirement.stock_name,
            requirement.used_quantity,
            requirement.required_quantity,
            requirement.additional_quantity_needed,
        );
    }

    Ok(())
}

Stock1D fields:

• length: raw stock length before trim is removed.
• kerf: material lost to the saw between adjacent cuts.
• trim: unusable material removed from the stock length before packing.
• cost: per-unit cost of consuming one piece of this stock type.
• available: optional inventory cap (number of pieces of this type that may be used).

OneDOptions fields (effective defaults are in the generated reference):

• algorithm: auto (default), first_fit_decreasing, best_fit_decreasing, local_search, or column_generation.
• multistart_runs: number of restarts for local search.
• improvement_rounds: improvement passes per local-search start.
• column_generation_rounds: LP/pricing rounds before one pattern-enumeration pass.
• exact_pattern_limit: cap on the single exhaustive enumeration pass in the exact backend; hitting it discards that batch and leaves the result non-exact.
• auto_exact_max_types: maximum distinct demand types for Auto mode to attempt the exact backend.
• auto_exact_max_quantity: maximum total demand quantity for Auto mode to attempt the exact backend.
• seed: optional RNG seed for reproducible randomized algorithms.

OneDSolution fields of interest:

• algorithm / exact / lower_bound
• stock_count, total_waste, total_cost
• layouts: per-piece StockLayout1D entries (stock name, used/remaining length, waste, cost, and cut list), sorted by utilization descending.
• stock_requirements: per-stock procurement summary including any shortage against the declared available inventory. When inventory caps are present this is computed from a relaxed-inventory Auto re-solve.
• unplaced: cuts the solver could not place (normally empty unless inventory capped the solution).
• metrics: iterations, generated_patterns, enumerated_patterns, explored_states, and diagnostic notes.

2D rectangular packing

use bin_packing::two_d::{
    RectDemand2D, Sheet2D, TwoDAlgorithm, TwoDOptions, TwoDProblem, solve_2d,
};

fn main() -> bin_packing::Result<()> {
    let problem = TwoDProblem {
        sheets: vec![Sheet2D {
            name: "plywood".into(),
            width: 96,
            height: 48,
            cost: 1.0,
            quantity: None,
            kerf: 2,
            edge_kerf_relief: false,
        }],
        demands: vec![
            RectDemand2D {
                name: "panel-a".into(),
                width: 24,
                height: 18,
                quantity: 4,
                can_rotate: true,
            },
            RectDemand2D {
                name: "panel-b".into(),
                width: 12,
                height: 12,
                quantity: 6,
                can_rotate: true,
            },
        ],
    };

    let solution = solve_2d(
        problem,
        TwoDOptions {
            algorithm: TwoDAlgorithm::Auto,
            seed: Some(42),
            ..Default::default()
        },
    )?;

    println!("algorithm: {}", solution.algorithm);
    println!("sheets used: {}", solution.sheet_count);
    println!("waste area: {}", solution.total_waste_area);
    println!("guillotine: {}", solution.guillotine);

    for layout in &solution.layouts {
        println!(
            "{}: {} placements, {} waste area",
            layout.sheet_name,
            layout.placements.len(),
            layout.waste_area
        );
        for placement in &layout.placements {
            println!(
                "  {} @ ({}, {}) {}x{}{}",
                placement.name,
                placement.x,
                placement.y,
                placement.width,
                placement.height,
                if placement.rotated { " rotated" } else { "" },
            );
        }
    }

    Ok(())
}

Sheet2D fields:

• width, height: sheet dimensions (positive, up to 1 << 30).
• cost: per-unit cost of consuming one sheet of this type.
• quantity: optional cap on the number of sheets of this type that may be used.
• kerf: optional saw-blade kerf width. The solver enforces this gap between every pair of adjacent placements on the sheet; the gap between a placement and the sheet edge is free (factory edge rule).
• edge_kerf_relief: when true, the trailing placement on the sheet may extend up to one kerf past the sheet's right and bottom edges, modeling a cut that exits the stock. Individual parts must still fit within the sheet's declared dimensions.

RectDemand2D fields:

• width, height: rectangle dimensions (positive, up to 1 << 30).
• quantity: number of identical rectangles required.
• can_rotate: whether the solver may rotate this rectangle 90°.

TwoDOptions fields (effective defaults are in the generated reference):

• algorithm: see the 2D algorithm table above; defaults to auto.
• multistart_runs: number of restarts for the multistart meta-strategy.
• beam_width: beam width for the guillotine beam search backend.
• guillotine_required: filters auto to guillotine variants. It does not override an explicitly selected algorithm.
• min_usable_side: minimum side length (in the same units as sheet dimensions) for a leftover drop to count as usable. A zero threshold counts all nonzero drops. Raise this to ignore narrow strips that are too small to reuse; the consolidation tiebreakers then favour solutions that leave fewer but larger reusable offcuts.
• auto_rotation_search_max_types: maximum number of rotatable demand types for which rotation search uses exhaustive enumeration, subject to a hard ceiling of 16. Above the smaller of this threshold and 16, rotation search switches to sampling multistart_runs random assignments.
• seed: optional RNG seed for reproducible randomized algorithms.

TwoDSolution fields of interest:

• algorithm, guillotine
• sheet_count, total_waste_area, total_kerf_area, total_cost
• max_usable_drop_area: the largest single usable drop area across all layouts (MAX over layouts, not a sum). A drop qualifies when both its sides are at least min_usable_side.
• total_sum_sq_usable_drop_areas: saturating sum of sum_sq_usable_drop_areas across all layouts. Higher values indicate better drop consolidation (fewer but larger reusable offcuts).
• layouts: per-sheet SheetLayout2D entries (sheet name, dimensions, placements, used area, waste area, kerf_area — the portion of waste_area attributable to kerf gaps — largest_usable_drop_area, and sum_sq_usable_drop_areas).
• placements: each Placement2D carries x, y, width, height, and rotated (whether the rectangle was rotated from its declared orientation).
• unplaced: demands the solver could not place.
• metrics: iterations, explored_states, and diagnostic notes.

3D box packing

use bin_packing::three_d::{
    Bin3D, BoxDemand3D, RotationMask3D, ThreeDAlgorithm, ThreeDOptions,
    ThreeDProblem, solve_3d,
};

fn main() -> bin_packing::Result<()> {
    let problem = ThreeDProblem {
        bins: vec![Bin3D {
            name: "pallet".into(),
            width: 120,
            height: 100,
            depth: 80,
            cost: 1.0,
            quantity: None,
        }],
        demands: vec![
            BoxDemand3D {
                name: "carton-a".into(),
                width: 30,
                height: 25,
                depth: 20,
                quantity: 6,
                allowed_rotations: RotationMask3D::ALL,
            },
            BoxDemand3D {
                name: "carton-b".into(),
                width: 20,
                height: 15,
                depth: 10,
                quantity: 8,
                allowed_rotations: RotationMask3D::UPRIGHT,
            },
        ],
    };

    let solution = solve_3d(
        problem,
        ThreeDOptions {
            algorithm: ThreeDAlgorithm::Auto,
            seed: Some(42),
            ..Default::default()
        },
    )?;

    println!("algorithm: {}", solution.algorithm);
    println!("bins used: {}", solution.bin_count);
    println!("waste volume: {}", solution.total_waste_volume);

    for layout in &solution.layouts {
        println!(
            "{}: {} placements, {} waste volume",
            layout.bin_name,
            layout.placements.len(),
            layout.waste_volume
        );
        for placement in &layout.placements {
            println!(
                "  {} @ ({}, {}, {}) {}x{}x{} rotation={:?}",
                placement.name,
                placement.x, placement.y, placement.z,
                placement.width, placement.height, placement.depth,
                placement.rotation,
            );
        }
    }

    Ok(())
}

Bin3D fields:

• width, height, depth: bin dimensions (positive, up to 1 << 15).
• cost: per-unit cost of consuming one bin of this type.
• quantity: optional cap on the number of bins of this type that may be used.

BoxDemand3D fields:

• width, height, depth: declared box dimensions (positive, up to 1 << 15).
• quantity: number of identical boxes required.
• allowed_rotations: bitmask of the six axis-permutation orientations permitted for this box. Use RotationMask3D::ALL (all six), RotationMask3D::UPRIGHT (only Xyz and Zyx, keeping the y-axis vertical), or construct a custom mask from the per-rotation constants (RotationMask3D::XYZ, XZY, YXZ, YZX, ZXY, ZYX).

ThreeDOptions fields (effective defaults are in the generated reference):

• algorithm: see the 3D algorithm table above; defaults to auto.
• multistart_runs: number of restarts for randomized meta-strategies.
• improvement_rounds: improvement passes per local-search or GRASP start.
• beam_width: beam width for the Guillotine 3D beam search backend.
• seed: optional RNG seed for reproducible randomized algorithms.
• auto_exact_max_types / auto_exact_max_quantity: reserved for compatibility; 3D Auto does not use these fields. Select branch_and_bound explicitly to request the restricted exact backend.
• branch_and_bound_node_limit: maximum nodes the exact backend may expand.
• guillotine_required: filters Auto to its guillotine-compatible ensemble; it does not override an explicitly selected algorithm.

ThreeDSolution fields of interest:

• algorithm, exact, lower_bound, guillotine
• bin_count, total_waste_volume, total_cost
• layouts: per-bin BinLayout3D entries (bin name, dimensions, placements, used_volume, waste_volume).
• placements: each Placement3D carries x, y, z, width, height, depth, and rotation (the Rotation3D variant applied).
• bin_requirements: per-bin procurement summary (populated when at least one Bin3D.quantity cap is set).
• unplaced: boxes the solver could not place.
• metrics: iterations, explored_states, extreme_points_generated, branch_and_bound_nodes, and diagnostic notes.

Errors

BinPackingError is #[non_exhaustive]. Match it with a wildcard arm.

• InvalidInput(String) — problem failed boundary validation (empty stock/sheet list, zero dimension, non-finite cost, trim ≥ length, etc.).
• Infeasible1D { item, length } — a 1D demand does not fit any declared stock.
• Infeasible2D { item, width, height } — a 2D demand does not fit any declared sheet, even with rotation.
• Infeasible3D { item, width, height, depth } — a 3D demand does not fit any declared bin in any allowed rotation.
• InvalidConstraint { field, reason } — a physical/objective request or its controls exceed a supported rule or bound.
• InvalidSolution { reason } — independent readback found inconsistent output.
• Unsupported(String) — the exact backend encountered a configuration it does not currently handle (for example, multi-stock input or capped inventory for column generation), or an internal invariant violation was caught by a defensive check at runtime.

Node.js usage

Build the binding from bindings/node:

pnpm install
pnpm run build

Then call the wrapper with plain JavaScript objects. Field names match the Rust serde representation (snake_case):

const assert = require('node:assert/strict');
const binPacking = require('@0xdoublesharp/bin-packing');

const cutList = binPacking.solve1d(
  {
    stock: [{ name: 'bar', length: 100, kerf: 1, available: 5 }],
    demands: [
      { name: 'A', length: 45, quantity: 2 },
      { name: 'B', length: 30, quantity: 2 }
    ]
  },
  { algorithm: 'auto', seed: 7 }
);

console.log(cutList.stock_count);
console.log(cutList.stock_requirements);
console.log(cutList.unplaced);

const layout = binPacking.solve2d(
  {
    sheets: [{ name: 'plywood', width: 96, height: 48, kerf: 2 }],
    demands: [
      { name: 'panel', width: 24, height: 18, quantity: 4, can_rotate: true }
    ]
  },
  { algorithm: 'auto', guillotine_required: true, beam_width: 12 }
);

console.log(layout.sheet_count, layout.total_waste_area, layout.guillotine);

const packing = binPacking.solve3d(
  {
    bins: [{ name: 'pallet', width: 120, height: 100, depth: 80 }],
    demands: [
      { name: 'carton-a', width: 30, height: 25, depth: 20, quantity: 6 },
      { name: 'carton-b', width: 20, height: 15, depth: 10, quantity: 8 }
    ]
  },
  { algorithm: 'auto', seed: 42 }
);

assert.equal(cutList.unplaced.length, 0);
assert.equal(layout.unplaced.length, 0);
assert.equal(layout.guillotine, true);
assert.equal(packing.unplaced.length, 0);
assert.equal(packing.layouts.flatMap(bin => bin.placements).length, 14);
console.log(packing.bin_count, packing.total_waste_volume);

TypeScript type definitions ship alongside the JavaScript wrapper in bindings/node/wrapper.d.ts. Both camelCase (solve1D / solve2D / solve3D) and lowercase (solve1d / solve2d / solve3d) aliases are exported, plus a version() helper.

Browser / WASM usage

For browsers and Node.js environments where a native addon is inconvenient, the WebAssembly binding at bindings/wasm publishes to npm as @0xdoublesharp/bin-packing-wasm. It ships combined and dimension-specific targets through a single package:

pnpm add @0xdoublesharp/bin-packing-wasm

// Bundlers (Vite, webpack, esbuild, Next.js, Rollup, Parcel)
import { solve1d, solve2d } from '@0xdoublesharp/bin-packing-wasm';

// Smaller dimension-specific browser bundles
import { solve1d as solveCutList } from '@0xdoublesharp/bin-packing-wasm/one-d';
import { solve2d as solveSheets } from '@0xdoublesharp/bin-packing-wasm/two-d';
import { solve3d as packBoxes } from '@0xdoublesharp/bin-packing-wasm/three-d';

// Raw ES modules / Deno — explicit init required
import init, { solve2d as solveWebSheets } from '@0xdoublesharp/bin-packing-wasm/web';
await init();

// Node.js / Bun — synchronous load, no init
import { solve1d as solveNodeCuts } from '@0xdoublesharp/bin-packing-wasm/nodejs';

The API is identical to the Node binding: plain JS objects go in, plain JS objects come out, and errors throw native JavaScript exceptions with the original BinPackingError message. Full TypeScript types are included. Combined builds include irregular nesting. Use a dimension-specific import to reduce payload size. The dated expansion report records measured sizes; a fresh build is required for current sizes.

Build it locally:

cd bindings/wasm
rustup target add wasm32-unknown-unknown
cargo install wasm-pack
pnpm run build  # builds combined and dimension-specific targets into dist/
pnpm test       # runs the Node smoke test against dist/nodejs

See bindings/wasm/README.md for the full API reference and per-target usage examples.

Repository layout

crates/bin-packing/          # core solver crate
  src/one_d/                 #   1D model, heuristics, and exact backend
  src/two_d/                 #   2D model, MaxRects, Skyline, Guillotine, Shelf, RotationSearch
  src/three_d/               #   3D model, loading and objective solvers
  src/irregular/             #   polygon/curve nesting and independent validation
  src/optimization.rs        #   public shared objective controls
  src/optimization/          #   shared bounded objective search
  benches/solver_benches.rs  #   Criterion benchmarks (1D + 2D + 3D)
  tests/solver_regressions.rs
bindings/node/               # napi-rs Node.js bindings (@0xdoublesharp/bin-packing)
bindings/wasm/               # wasm-bindgen WebAssembly bindings (@0xdoublesharp/bin-packing-wasm)
fuzz/fuzz_targets/           # cargo-fuzz / libFuzzer targets (1D + 2D + 3D)
AGENTS.md                    # contributor rules

Verification

One-time install for the repo-wide hygiene tools:

cargo install taplo-cli typos-cli --locked

Full Rust/doc/text/TOML quality gate (matches CI):

./scripts/check-quality.sh

See correctness checks and production coverage for independent oracle tests and the repeatable line/branch coverage command.

The gate also checks generated docs, local documentation links and runnable Rust examples. Refresh source-derived facts with python3 -B scripts/check-docs.py --write; see documentation maintenance.

Individual Rust/text/TOML commands (the script also runs Python and docs checks):

cargo fmt --all --check
taplo fmt --check
typos
cargo clippy --workspace --all-targets --all-features --locked -- -D warnings
cargo test --workspace --all-targets --all-features --locked
cargo test -p bin-packing --doc --all-features --locked
cargo doc --manifest-path crates/bin-packing/Cargo.toml --locked --no-deps --document-private-items

Criterion benchmarks:

cargo bench -p bin-packing --bench solver_benches -- --sample-size 10

Node binding smoke test:

cd bindings/node
pnpm test

WebAssembly binding build and smoke test:

cd bindings/wasm
pnpm run build
pnpm test

Fuzz target build and execution:

cargo check --manifest-path fuzz/Cargo.toml
cargo fuzz run solver_inputs

Complete workspace and package verification

See workspace verification for the feature matrix, all binding entry points, isolated npm archive checks, browser/type checks and the seeded counterexample finder. scripts/check-bindings.sh rebuilds and checks both packages; scripts/check-features.sh includes the separate fuzz project.

For local builds on a separate disposable volume, see Scratch build storage.

Publishing

See the release runbook for version synchronization, documentation checks, package verification, tag publication and readback.

Contributing and community

See CONTRIBUTING.md for development setup, verification, bug reports, and pull requests. Project participation follows the code of conduct. Report vulnerabilities privately using the security policy.

License

Licensed under the MIT License.