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

DOI10.1016/J.ORL.2011.10.008zbMATH Open1242.90106arXiv2101.00441OpenAlexW2142331260MaRDI QIDQ433833FDOQ433833

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)

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.

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

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

zbMATH Keywords

linear programminginteger programmingpackingload planningpigeon hole principle

Mathematics Subject Classification ID

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

Cites Work

• Hardness of approximation for orthogonal rectangle packing and covering problems
• Conflict analysis in mixed integer programming
• A time indexed formulation of non-preemptive single machine scheduling problems
• A hybrid placement strategy for the three-dimensional strip packing problem
• An analytical model for the container loading problem
• Three-dimensional container loading models with cargo stability and load bearing constraints
• 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.
• Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing
• Probabilistic Analysis of Geometric Location Problems
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem
• Title not available (Why is that?)

Cited In (7)

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

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)