One-dimensional relaxations and LP bounds for orthogonal packing

G. Belov, V. Kartak, H. Rohling, G. Scheithauer

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We consider the feasibility problem in d-dimensional orthogonal packing (d2), called the Orthogonal Packing Problem (OPP): given a set of d-dimensional rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. We review two kinds of one-dimensional (1D) relaxations of OPP. The first kind is non-preemptive cumulative-resource scheduling, equivalently 1D contiguous stock cutting. The second kind is simple (preemptive) 1D stock cutting. In three and more dimensions we distinguish the so-called bar and slice preemptive relaxations of OPP. We review some models of these problems and compare the strength of their LP relaxations with regard to a certain OPP instance, theoretically and numerically. Both the theory and computational results in 2D and 3D show the advantage of the bar relaxation. We also compare the LP bounds with the commonly used volume bounds from dual-feasible functions. Moreover, we test the so-called probing (temporary fixing) of intersection variables of OPP with the aim to strengthen the relaxations.

Original languageEnglish
Pages (from-to)745-766
Number of pages22
JournalInternational Transactions in Operational Research
Volume16
Issue number6
DOIs
Publication statusPublished - 1 Jan 2009

Keywords

  • Conservative scales
  • Dual-feasible function
  • Modeling
  • Packing
  • Probing
  • Relaxation

Cite this

Belov, G. ; Kartak, V. ; Rohling, H. ; Scheithauer, G. / One-dimensional relaxations and LP bounds for orthogonal packing. In: International Transactions in Operational Research. 2009 ; Vol. 16, No. 6. pp. 745-766.
@article{9c75d14369b4464ebc488055696d107f,
title = "One-dimensional relaxations and LP bounds for orthogonal packing",
abstract = "We consider the feasibility problem in d-dimensional orthogonal packing (d2), called the Orthogonal Packing Problem (OPP): given a set of d-dimensional rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. We review two kinds of one-dimensional (1D) relaxations of OPP. The first kind is non-preemptive cumulative-resource scheduling, equivalently 1D contiguous stock cutting. The second kind is simple (preemptive) 1D stock cutting. In three and more dimensions we distinguish the so-called bar and slice preemptive relaxations of OPP. We review some models of these problems and compare the strength of their LP relaxations with regard to a certain OPP instance, theoretically and numerically. Both the theory and computational results in 2D and 3D show the advantage of the bar relaxation. We also compare the LP bounds with the commonly used volume bounds from dual-feasible functions. Moreover, we test the so-called probing (temporary fixing) of intersection variables of OPP with the aim to strengthen the relaxations.",
keywords = "Conservative scales, Dual-feasible function, Modeling, Packing, Probing, Relaxation",
author = "G. Belov and V. Kartak and H. Rohling and G. Scheithauer",
year = "2009",
month = "1",
day = "1",
doi = "10.1111/j.1475-3995.2009.00713.x",
language = "English",
volume = "16",
pages = "745--766",
journal = "International Transactions in Operational Research",
issn = "0969-6016",
publisher = "Wiley-Blackwell",
number = "6",

}

One-dimensional relaxations and LP bounds for orthogonal packing. / Belov, G.; Kartak, V.; Rohling, H.; Scheithauer, G.

In: International Transactions in Operational Research, Vol. 16, No. 6, 01.01.2009, p. 745-766.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - One-dimensional relaxations and LP bounds for orthogonal packing

AU - Belov, G.

AU - Kartak, V.

AU - Rohling, H.

AU - Scheithauer, G.

PY - 2009/1/1

Y1 - 2009/1/1

N2 - We consider the feasibility problem in d-dimensional orthogonal packing (d2), called the Orthogonal Packing Problem (OPP): given a set of d-dimensional rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. We review two kinds of one-dimensional (1D) relaxations of OPP. The first kind is non-preemptive cumulative-resource scheduling, equivalently 1D contiguous stock cutting. The second kind is simple (preemptive) 1D stock cutting. In three and more dimensions we distinguish the so-called bar and slice preemptive relaxations of OPP. We review some models of these problems and compare the strength of their LP relaxations with regard to a certain OPP instance, theoretically and numerically. Both the theory and computational results in 2D and 3D show the advantage of the bar relaxation. We also compare the LP bounds with the commonly used volume bounds from dual-feasible functions. Moreover, we test the so-called probing (temporary fixing) of intersection variables of OPP with the aim to strengthen the relaxations.

AB - We consider the feasibility problem in d-dimensional orthogonal packing (d2), called the Orthogonal Packing Problem (OPP): given a set of d-dimensional rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. We review two kinds of one-dimensional (1D) relaxations of OPP. The first kind is non-preemptive cumulative-resource scheduling, equivalently 1D contiguous stock cutting. The second kind is simple (preemptive) 1D stock cutting. In three and more dimensions we distinguish the so-called bar and slice preemptive relaxations of OPP. We review some models of these problems and compare the strength of their LP relaxations with regard to a certain OPP instance, theoretically and numerically. Both the theory and computational results in 2D and 3D show the advantage of the bar relaxation. We also compare the LP bounds with the commonly used volume bounds from dual-feasible functions. Moreover, we test the so-called probing (temporary fixing) of intersection variables of OPP with the aim to strengthen the relaxations.

KW - Conservative scales

KW - Dual-feasible function

KW - Modeling

KW - Packing

KW - Probing

KW - Relaxation

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

U2 - 10.1111/j.1475-3995.2009.00713.x

DO - 10.1111/j.1475-3995.2009.00713.x

M3 - Article

VL - 16

SP - 745

EP - 766

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

SN - 0969-6016

IS - 6

ER -