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

Gleb Belov, Heide Rohling

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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
Volume61
Issue number2
DOIs
Publication statusPublished - Mar 2013
Externally publishedYes

Keywords

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

Cite this

@article{ec330206c1d04f21885897d55d14402c,
title = "LP bounds in an interval-graph algorithm for orthogonal-packing feasibility",
abstract = "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.",
keywords = "Branch-and-price, Dimension reduction, Interval graph, Packing",
author = "Gleb Belov and Heide Rohling",
year = "2013",
month = "3",
doi = "10.1287/opre.1120.1150",
language = "English",
volume = "61",
pages = "483--497",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS",
number = "2",

}

LP bounds in an interval-graph algorithm for orthogonal-packing feasibility. / Belov, Gleb; Rohling, Heide.

In: Operations Research, Vol. 61, No. 2, 03.2013, p. 483-497.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Belov, Gleb

AU - Rohling, Heide

PY - 2013/3

Y1 - 2013/3

N2 - 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.

AB - 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.

KW - Branch-and-price

KW - Dimension reduction

KW - Interval graph

KW - Packing

UR - http://www.scopus.com/inward/record.url?scp=84877857502&partnerID=8YFLogxK

U2 - 10.1287/opre.1120.1150

DO - 10.1287/opre.1120.1150

M3 - Article

VL - 61

SP - 483

EP - 497

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 2

ER -