LP Bounds in an Interval-Graph Algorithm for Orthogonal-Packing Feasibility

Gleb Belov () and Heide Rohling ()
Additional contact information
Gleb Belov: Department of Mathematics, University of Duisburg-Essen, 47057 Duisburg, Germany
Heide Rohling: OncoRay---National Center of Radiation Research in Oncology, Dresden University of Technology, 01307 Dresden, Germany

Operations Research, 2013, vol. 61, issue 2, 483-497

Abstract: We consider the feasibility problem OPP (orthogonal packing problem) in higher-dimensional orthogonal packing: given a set of d -dimensional ( d (ge) 2) rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. The one-dimensional (1D) “bar” LP relaxation of OPP reduces the latter to a 1D cutting-stock problem where the packing of each stock bar represents a possible 1D stitch through an OPP layout. The dual multipliers of the LP provide us with another kind of powerful bounding information (conservative scales). We investigate how the set of possible 1D packings can be tightened using the overlapping information of item projections on the axes, with the goal to tighten the relaxation. We integrate the bar relaxation into an interval-graph algorithm for OPP, which operates on such overlapping relations. Numerical results on 2D and 3D instances demonstrate the efficiency of tightening leading to a speedup and stabilization of the algorithm.

Keywords: packing; branch-and-price; dimension reduction; interval graph (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1150 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:2:p:483-497

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().