One-Dimensional Relaxations and LP Bounds for Orthogonal Packing

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • G. Belov - (Autor:in)
  • V. Kartak - (Autor:in)
  • Heide Rohling - (Autor:in)
  • Guntram Scheithauer - (Autor:in)

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.

Details

OriginalspracheEnglisch
Seiten (von - bis)745-766
FachzeitschriftInternational transactions in operational research : ITOR ; a journal of the International Federation of Operational Research Societies (IFORS)
Jahrgang16
Ausgabenummer6
PublikationsstatusVeröffentlicht - 2009
Peer-Review-StatusJa

Externe IDs

Scopus 84956801161

Schlagworte

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis

Ziele für nachhaltige Entwicklung

Schlagwörter

  • Orthogonal Packing, Relaxation, LP-Bound

Bibliotheksschlagworte