A space-indexed formulation of packing boxes into a larger box

DOI10.1016/J.ORL.2011.10.008MaRDI QIDQ433833zbMATHOpenAlexFDO

Authors Sam D. Allen, Jakub Mareček, Edmund K. Burke

Publication date 6 July 2012

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.00441

zbMATH Keywords

linear programminginteger programmingpackingload planningpigeon hole principle

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10)

Abstract: Current integer programming solvers fail to decide whether 12 unit cubes can be packed into a 1x1x11 box within an hour using the natural relaxation of Chen/Padberg. We present an alternative relaxation of the problem of packing boxes into a larger box, which makes it possible to solve much larger instances.

Recommendations

• Exploiting packing components in general-purpose integer programming solvers
• Packing small boxes into a big box.
• Packing cubes into a cube in \((D>3)\)-dimensions
• Packing a trunk
• Bidimensional Packing by Bilinear Programming

Cites work

• scientific article; zbMATH DE number 702559 (Why is no real title available?)
• A hybrid placement strategy for the three-dimensional strip packing problem
• A time indexed formulation of non-preemptive single machine scheduling problems
• Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing
• An analytical model for the container loading problem
• Conflict analysis in mixed integer programming
• Hardness of approximation for orthogonal rectangle packing and covering problems
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
• Packing small boxes into a big box.
• Probabilistic Analysis of Geometric Location Problems
• Three-dimensional container loading models with cargo stability and load bearing constraints
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem

Cited in

(7)

• A comparative review of 3D container loading algorithms
• Exact methods for three-dimensional cutting and packing: a comparative study concerning single container problems
• A MIP-based slicing heuristic for three-dimensional bin packing
• Applying spatial representation techniques to the container packing problem
• Packing small boxes into a big box.
• Exploiting packing components in general-purpose integer programming solvers
• A data-driven approach for mixed-case palletization with support

Describes a project that uses

Uses Software

• SCIP
• MIPLIB

This page was built for publication: A space-indexed formulation of packing boxes into a larger box

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433833)