LP bounds in an interval-graph algorithm for orthogonal-packing feasibility

Gleb Belov, Heide Rohling

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)


We consider the feasibility problem OPP (orthogonal packing problem) in higher-dimensional orthogonal packing: given a set of d-dimensional (d ≥ 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.

Original languageEnglish
Pages (from-to)483-497
Number of pages15
JournalOperations Research
Issue number2
Publication statusPublished - Mar 2013
Externally publishedYes


  • Branch-and-price
  • Dimension reduction
  • Interval graph
  • Packing

Cite this