Conservative Scales in Packing

  • :

    July 12th, 2012

  • Referent:

    Dr. Vadim Kartak, Ufa State Aviation Technical University (Russia)

Conservative Scales in Packing Problems

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) dualfeasible functions ((D)DFFs).We introduce the notions of maximal CS (MCS).We propose fast greedy methods to maximize¨a given CS. For higher-dimensional orthogonal packing, we propose a Sequential LP (SLP) method over the set of CS. Finally, the equivalence problem is discussed. This research is support by DFG and RFBR.