hyperpack

hyperpack provides exact-aware packing models, proposal algorithms, and feasibility replay over hyperreal::Real. It covers stock cutting, sheet packing, cuboid packing, cardinal orientations, multi-bin assignment, constraints, local search, and bounded exact search.

The central rule is simple: a heuristic proposes coordinates; replay decides whether those coordinates satisfy the modeled constraints. Unsupported or uncertified constraints remain explicit instead of being rounded into success.

Installation

[dependencies]
hyperpack = "0.3.0"

For a sibling checkout:

[dependencies]
hyperpack = { path = "../hyperpack" }

Quick Start

Every proposal report includes its exact replay. This example packs two fixed-orientation rectangles with MaxRects and checks the result:

use hyperpack::{
    FeasibilityStatus, ItemId, Real, Rect2, SheetBin2, SheetItem2,
    maxrects_best_short_side_fit_2d,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let bin = SheetBin2::new(Rect2::new(Real::from(10), Real::from(10))?);
    let items = vec![
        SheetItem2::new(
            ItemId::new("a")?,
            Rect2::new(Real::from(4), Real::from(4))?,
        ),
        SheetItem2::new(
            ItemId::new("b")?,
            Rect2::new(Real::from(6), Real::from(3))?,
        ),
    ];

    let report = maxrects_best_short_side_fit_2d(&bin, &items)?;
    assert_eq!(report.replay.status, FeasibilityStatus::Feasible);
    assert!(report.rejected.is_empty());
    Ok(())
}

For coordinates supplied by another algorithm, construct StockPlacement1, SheetPlacement2, or Placement3 values and call verify_packing_1d, verify_packing_2d, or verify_packing_3d directly.

Model and Reports

The principal input types are:

• StockBin1 and StockItem1 for exact intervals;
• SheetBin2, SheetItem2, and Rect2 for exact rectangles;
• Bin3, Item3, and AxisBox3 for exact axis-aligned cuboids;
• OrientedSheetItem2 and OrientedItem3 for allowed cardinal dimension permutations; and
• BinInstance3 and MultiBinPlacement3 for named-bin assignment and cost.

FeasibilityStatus distinguishes Feasible, Infeasible, and Unknown. Verification reports retain exact objective values, item accounting, check counts, and human-readable evidence. Orientation, clearance, support, load, multi-bin, and domain handoff checks have separate reports so a geometric pass cannot accidentally imply that an unmodeled policy also passed.

Proposal and Search Algorithms

The proposal surface includes:

• 2D shelf (NFDH, FFDH, BFDH), skyline, MaxRects, and guillotine variants;
• 3D corner-point, extreme-point, maximal-space, guillotine, and LAFF variants;
• deterministic portfolios, order local search, tabu search, seeded multistart, reinsertion repair, and bin-emptying repair; and
• branch_and_bound_one_bin_3d, a limit-bearing fixed-orientation solver for small one-bin instances.

Proposal reports include trace counters, rejected items, retained free-space state, and exact replay. PreparedPacking3 caches exact demand classes, grid facts, lower bounds, initial free space, and deterministic order for repeated search. Prepared data is advisory; replay remains authoritative.

The bounded solver returns Unknown when its item or node limit prevents an exhaustive result. A feasible replay proves feasibility, while objective values, lower bounds, and heuristic rankings do not by themselves prove global optimality.

Exactness Boundary

Dimensions, positions, lengths, areas, volumes, costs, weights, and bounds use Real. The implemented interval, rectangle, and cuboid containment and no-overlap tests use certified sign queries. Uncertified comparisons propagate as Unknown; the crate does not introduce an epsilon or silently lower a decision to f64.

Exact replay currently covers:

• 1D, fixed-orientation 2D, cardinally oriented 2D, fixed-orientation 3D, and six-permutation oriented 3D geometry;
• one-placement-per-item accounting and multi-bin assignment;
• exact used space, waste, height, cost, and lexicographic objective comparison;
• capacity and pair-incompatibility necessary bounds;
• positive kerf/clearance separation;
• full-base, area-ratio, and footprint-center support policies; and
• direct top-face load limits with caller-supplied exact weights.

Snapshot helpers preserve rational text or full hyperreal structural JSON. The binary format uses length-prefixed UTF-8 fields rather than primitive-float encodings. No-overlap model exports preserve exact coordinate domains and pairwise axis-separation disjunctions for solver adapters.

Limitations

• Orientations are cardinal dimension permutations, not arbitrary rotations.
• CenterOfMassProjection checks the geometric footprint center, not a mass distribution supplied by a physics model.
• Support and direct-load reports do not model friction, deformation, dynamics, or transitive load propagation.
• Routing, manufacturing-process, and richer physical constraints require certified domain handoffs.
• The bounded 3D branch-and-bound backend is intentionally for small, fixed-orientation, one-bin instances; the crate is not a general optimality-proving optimizer.

Development

cargo fmt --all -- --check
cargo test --locked
cargo check --benches --locked
cargo clippy --all-targets --locked -- -D warnings
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --locked
cargo bench --bench feasibility

References

• Chee K. Yap, “Towards Exact Geometric Computation”, Computational Geometry 7(1–2), 1997.
• Harald Dyckhoff, “A Typology of Cutting and Packing Problems”, European Journal of Operational Research 44(2), 1990.
• Silvano Martello and Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990.
• Silvano Martello, David Pisinger, and Daniele Vigo, “The Three-Dimensional Bin Packing Problem”, Operations Research 48(2), 2000.
• Andrea Lodi, Silvano Martello, and Daniele Vigo, “Heuristic Algorithms for the Three-Dimensional Bin Packing Problem”, European Journal of Operational Research 141(2), 2002.
• Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei, “Extreme Point-Based Heuristics for Three-Dimensional Bin Packing”, INFORMS Journal on Computing 20(3), 2008.
• Jukka Jylänki, “A Thousand Ways to Pack the Bin—A Practical Approach to Two-Dimensional Rectangle Bin Packing”, 2010.
• Manuel Iori, Vinícius L. de Lima, Silvano Martello, Flávio K. Miyazawa, and Michele Monaci, “Exact Solution Techniques for Two-Dimensional Cutting and Packing”, European Journal of Operational Research 289(2), 2021.
• Andreas Bortfeldt and Gerhard Wäscher, “Constraints in Container Loading—A State-of-the-Art Review”, European Journal of Operational Research 229(1), 2013.
• Fred Glover, “Tabu Search—Part I”, ORSA Journal on Computing 1(3), 1989.
• David H. Wolpert and William G. Macready, “No Free Lunch Theorems for Optimization”, IEEE Transactions on Evolutionary Computation 1(1), 1997.
• Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann, 2004.

Hyper Ecosystem

hyperpack uses hyperreal for exact scalars. Related geometry, manufacturing, search, and integration crates include hyperparts, hyperphysics, hyperpath, hyperdrc, hypersolve, and hyperevolution.