Conservative scales in packing problems

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

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

Packing problems (sometimes also called cutting problems) are combinatorial optimization problems concerned with placement of objects (items) in one or several containers. Some packing problems are special cases of several other problems such as resource-constrained scheduling, capacitated vehicle routing, etc. In this paper we consider a bounding technique for one- and higher-dimensional orthogonal packing problems, called conservative scales (CS) (in the scheduling terminology, redundant resources). CS are related to the possible structure of resource consumption: filling of a bin, distribution of the resource to the jobs, etc. In terms of packing, CS are modified item sizes such that the set of feasible packings is not reduced. In fact, every CS represents a valid inequality for a certain binary knapsack polyhedron. CS correspond to dual variables of the set-partitioning model of a special 1D cutting-stock problem. Some CS can be constructed by (data-dependent) dual-feasible functions ((D)DFFs). We discuss the relation of CS to DFFs: CS assume that at most one copy of each object can appear in a combination, whereas DFFs allow several copies. The literature has investigated the so-called extremal maximal DFFs (EMDFFs) which should provide very strong CS. Analogously, we introduce the notions of maximal CS (MCS) and extremal maximal CS (EMCS) and show that EMDFFs do not necessarily produce (E)MCS. We propose fast greedy methods to "maximize" a given CS. Using the fact that EMCS define facets of the binary knapsack polyhedron, we use lifted cover inequalities as EMCS. For higher-dimensional orthogonal packing, we propose a Sequential LP (SLP) method over the set of CS and investigate its convergence. Numerical results are presented.

Original languageEnglish
Pages (from-to)505-542
Number of pages38
JournalOR Spectrum
Volume35
Issue number2
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Capacitated problems
  • Conservative scales
  • Convergence
  • Dual-feasible functions
  • Knapsack inequalities
  • Lifting
  • Linearization
  • Multilinear programming
  • Packing
  • Resource-constrained problems
  • Sequential linear programming

Cite this

Belov, G., Kartak, V. M., Rohling, H., & Scheithauer, G. (2013). Conservative scales in packing problems. OR Spectrum, 35(2), 505-542. https://doi.org/10.1007/s00291-011-0277-9
Belov, G. ; Kartak, V. M. ; Rohling, H. ; Scheithauer, G. / Conservative scales in packing problems. In: OR Spectrum. 2013 ; Vol. 35, No. 2. pp. 505-542.
@article{6ca621c8c330404f850663590f1c9c80,
title = "Conservative scales in packing problems",
abstract = "Packing problems (sometimes also called cutting problems) are combinatorial optimization problems concerned with placement of objects (items) in one or several containers. Some packing problems are special cases of several other problems such as resource-constrained scheduling, capacitated vehicle routing, etc. In this paper we consider a bounding technique for one- and higher-dimensional orthogonal packing problems, called conservative scales (CS) (in the scheduling terminology, redundant resources). CS are related to the possible structure of resource consumption: filling of a bin, distribution of the resource to the jobs, etc. In terms of packing, CS are modified item sizes such that the set of feasible packings is not reduced. In fact, every CS represents a valid inequality for a certain binary knapsack polyhedron. CS correspond to dual variables of the set-partitioning model of a special 1D cutting-stock problem. Some CS can be constructed by (data-dependent) dual-feasible functions ((D)DFFs). We discuss the relation of CS to DFFs: CS assume that at most one copy of each object can appear in a combination, whereas DFFs allow several copies. The literature has investigated the so-called extremal maximal DFFs (EMDFFs) which should provide very strong CS. Analogously, we introduce the notions of maximal CS (MCS) and extremal maximal CS (EMCS) and show that EMDFFs do not necessarily produce (E)MCS. We propose fast greedy methods to {"}maximize{"} a given CS. Using the fact that EMCS define facets of the binary knapsack polyhedron, we use lifted cover inequalities as EMCS. For higher-dimensional orthogonal packing, we propose a Sequential LP (SLP) method over the set of CS and investigate its convergence. Numerical results are presented.",
keywords = "Capacitated problems, Conservative scales, Convergence, Dual-feasible functions, Knapsack inequalities, Lifting, Linearization, Multilinear programming, Packing, Resource-constrained problems, Sequential linear programming",
author = "G. Belov and Kartak, {V. M.} and H. Rohling and G. Scheithauer",
year = "2013",
doi = "10.1007/s00291-011-0277-9",
language = "English",
volume = "35",
pages = "505--542",
journal = "OR Spectrum",
issn = "0171-6468",
publisher = "Springer-Verlag London Ltd.",
number = "2",

}

Belov, G, Kartak, VM, Rohling, H & Scheithauer, G 2013, 'Conservative scales in packing problems', OR Spectrum, vol. 35, no. 2, pp. 505-542. https://doi.org/10.1007/s00291-011-0277-9

Conservative scales in packing problems. / Belov, G.; Kartak, V. M.; Rohling, H.; Scheithauer, G.

In: OR Spectrum, Vol. 35, No. 2, 2013, p. 505-542.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Conservative scales in packing problems

AU - Belov, G.

AU - Kartak, V. M.

AU - Rohling, H.

AU - Scheithauer, G.

PY - 2013

Y1 - 2013

N2 - Packing problems (sometimes also called cutting problems) are combinatorial optimization problems concerned with placement of objects (items) in one or several containers. Some packing problems are special cases of several other problems such as resource-constrained scheduling, capacitated vehicle routing, etc. In this paper we consider a bounding technique for one- and higher-dimensional orthogonal packing problems, called conservative scales (CS) (in the scheduling terminology, redundant resources). CS are related to the possible structure of resource consumption: filling of a bin, distribution of the resource to the jobs, etc. In terms of packing, CS are modified item sizes such that the set of feasible packings is not reduced. In fact, every CS represents a valid inequality for a certain binary knapsack polyhedron. CS correspond to dual variables of the set-partitioning model of a special 1D cutting-stock problem. Some CS can be constructed by (data-dependent) dual-feasible functions ((D)DFFs). We discuss the relation of CS to DFFs: CS assume that at most one copy of each object can appear in a combination, whereas DFFs allow several copies. The literature has investigated the so-called extremal maximal DFFs (EMDFFs) which should provide very strong CS. Analogously, we introduce the notions of maximal CS (MCS) and extremal maximal CS (EMCS) and show that EMDFFs do not necessarily produce (E)MCS. We propose fast greedy methods to "maximize" a given CS. Using the fact that EMCS define facets of the binary knapsack polyhedron, we use lifted cover inequalities as EMCS. For higher-dimensional orthogonal packing, we propose a Sequential LP (SLP) method over the set of CS and investigate its convergence. Numerical results are presented.

AB - Packing problems (sometimes also called cutting problems) are combinatorial optimization problems concerned with placement of objects (items) in one or several containers. Some packing problems are special cases of several other problems such as resource-constrained scheduling, capacitated vehicle routing, etc. In this paper we consider a bounding technique for one- and higher-dimensional orthogonal packing problems, called conservative scales (CS) (in the scheduling terminology, redundant resources). CS are related to the possible structure of resource consumption: filling of a bin, distribution of the resource to the jobs, etc. In terms of packing, CS are modified item sizes such that the set of feasible packings is not reduced. In fact, every CS represents a valid inequality for a certain binary knapsack polyhedron. CS correspond to dual variables of the set-partitioning model of a special 1D cutting-stock problem. Some CS can be constructed by (data-dependent) dual-feasible functions ((D)DFFs). We discuss the relation of CS to DFFs: CS assume that at most one copy of each object can appear in a combination, whereas DFFs allow several copies. The literature has investigated the so-called extremal maximal DFFs (EMDFFs) which should provide very strong CS. Analogously, we introduce the notions of maximal CS (MCS) and extremal maximal CS (EMCS) and show that EMDFFs do not necessarily produce (E)MCS. We propose fast greedy methods to "maximize" a given CS. Using the fact that EMCS define facets of the binary knapsack polyhedron, we use lifted cover inequalities as EMCS. For higher-dimensional orthogonal packing, we propose a Sequential LP (SLP) method over the set of CS and investigate its convergence. Numerical results are presented.

KW - Capacitated problems

KW - Conservative scales

KW - Convergence

KW - Dual-feasible functions

KW - Knapsack inequalities

KW - Lifting

KW - Linearization

KW - Multilinear programming

KW - Packing

KW - Resource-constrained problems

KW - Sequential linear programming

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

U2 - 10.1007/s00291-011-0277-9

DO - 10.1007/s00291-011-0277-9

M3 - Article

VL - 35

SP - 505

EP - 542

JO - OR Spectrum

JF - OR Spectrum

SN - 0171-6468

IS - 2

ER -