- 2013
- 2012
- 2009
- 2007
- 2006
- 2005
- 2003
- A Class of Subpattern Formulations for 1D Stock Cutting
- Models with Variable Strip Widths for Two-Dimensional Two-Stage Cutting
- Setup and Open Stacks Minimization in One-Dimensional Stock Cutting
- The Number of Setups (Different Patterns) in One-Dimensional Stock Cutting
- Packing of convex polytopes into a parallelepiped
- A Branch-and-Cut-and-Price Algorithm for One-Dimensional Stock Cutting and Two-Dimensional Two-Stage Cutting

2002

- Construction of a Phi-function for two convex polytopes
- Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem
- Phi-functions for primary 2D-objects
- Phi-functions for primary 3D-objects
- Families of Non-IRUP instances of the one-dimensional cutting stock problem
- A Cutting Plane Algorithm for the One-Dimensional Cutting Stock Problem with Multiple Stock Lengths
- Phi-functions for complex 2D-objects
- Solving One-Dimensional Cutting Stock Problems with Multiple Stock Material Lengths Using Cutting Plane Approach

- 2001
- 2000
- Solving the General One-Dimensional Cutting Stock Problem with a Cutting Plane Approach
- Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem
- Construction of a $\Phi$-function for two convex polytopes
- Facet-defining inequalities for the cutting stock problem
- An Efficient Approach for the Multi-Pallet Loading Problem

- 1999
- 1998
- 4-Block Heuristic for the Rectangle Packing Problem
- New Cases of the Cutting Stock Problem Having MIRUP
- Equivalence and Dominance for Problems of Optimal Packing of Rectangles
- Optimale Positionierung beim Vollholzzuschnitt durch automatisierte Fehlererkennung
- Families of Non-IRUP instances of the one-dimensional cutting stock problem

- 1997
- A Heuristic Approach for Solving the Multi-Pallet Packing Problem
- LP-based bounds for the Container and Multi-Container Loading Problem
- The Properties IRUP and MIRUP for the Cutting Stock Problem
- The value correction method for packing of irregular shapes
- Cutting and Packing: An Annotated Bibliography
- An Efficient Approach for the Multi-Pallet Loading Problem
- Facet-defining inequalities for the cutting stock problem

- 1996
- The G4-Heuristic for the Pallet Loading Problem
- The Solution of Two-stage Guillotine Cutting Stock Problems Having Extremely Varying Order Demands
- A new heuristic for the Pallet Loading Problem
- Auftragsoptimierung bei Zuschnitt- und Packungsproblemen als ganzzahliges lineares Optimierungsmodell
- Dreidimensionale Packungsprobleme (Auftragsoptimierung auf Europaletten)
- A Heuristic Approach for Solving the Multi-Pallet Packing Problem

- 1995
- A branch and bound algorithm for solving one-dimensional cutting stock problems exactly
- The solution of packing problems with pieces of variable length and additional allocation constraints
- Numerical investigations on the MIRUP of the 2-stage guillotine cutting stock problem
- The Modified Integer Round-Up Property of the One-Dimensional Cutting Stock Problem

- 1994
- 1993
- 1992

[ Members | Services | Software | Links | Home | email ]

**2013**

** Conservative scales in packing problems**
*Authors:*
Gleb
Belov, Vadim M. Kartak, Heide Rohling, and Guntram
Scheithauer

*Operations Research Spectrum*, 35 (2):505-542, 2013.

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 1 copy of each object can appear in a combination, whereas DFFs
allow several copies. The literature has investigated 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:**
*packing, resource-constrained problems, capacitated problems, conservative
scales, dual-feasible functions, knapsack inequalities, lifting, multilinear programming,
linearization, sequential linear programming, convergence*

Text as PDF

Test instances, results, and problem generators Software

The following talks present some of the paper's results:

- A sequential linear programming heuristic for a multi-linear programming problem
- Extremal and maximal conservative scales
- Fast tightening of knapsack inequalities

[ Back | Members | Services | Software | Links | Home | email ]

**2012**

**A LP bounds in an interval-graph algorithm for orthogonal-packing feasibility**
*Authors:*
Gleb
Belov and Heide Rohling, accepted in *Operations Research*

We consider the feasibility problem OPP 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 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:**
*Packing, branch-and-price, dimension reduction, interval graph.*

PDF
....
3D test instances
Software

** New constraint programming approaches for 3D orthogonal packing**
*Authors:*
Marat Mesyagutov, Guntram Scheithauer, and Gleb
Belov **Preprint MATH-NM-01-2012 ** from January 15, 2012.

We consider the 3D orthogonal feasibility problem (OPP-3). Given a set of rectangular items, OPP-3 is to decide whether all items can be orthogonally packed into the given rectangular container. The problem is considered without items rotation. We propose an approach based on the ideas of the known recent constraint programming (CP) approaches for OPP-2 and adapt 1D relaxation bounds based on linear programming (LP) into the constraint propagation process of the CP. Numerical results demonstrate the efficiency of the proposed strategies and of the combination of CP and LP-based pruning rules.
**Keywords:**
*constraint programming, linear programming, column generation.*

Text as PDF

** LP bounds in various constraint programming approaches for orthogonal packing**
*Authors:*
Marat Mesyagutov, Guntram Scheithauer, and Gleb
Belov *Computers and Operations Research, 39(10): 2425-2438 (2012)*

We consider the 2D orthogonal feasibility problem (OPP-2) and the 2D strip packing problem (SPP-2). Given a set of rectangular items, the OPP-2 is to decide whether all items can be orthogonally packed into the given rectangular container; the SPP-2 is to find a packing of all items occupying the minimal height of the given semi-infinite strip. Both OPP-2 and SPP-2 are considered without items rotation. We investigate the known Constraint Programming (CP) approaches for OPP-2, in particular the dichotomy and disjunctive branching strategies and adapt 1D relaxation bounds based on linear programming (LP) into the constraint propagation process of the CP. Using the dichotomic search procedure the developed methods for OPP-2 are transformed for the case of SPP-2. Numerical results demonstrate the efficiency of the proposed strategies and of the combination of CP and LP-based pruning rules.
**Keywords:**
*constraint programming, linear programming, column generation.*

http://dx.doi.org/10.1016/j.cor.2011.12.010

2D test instances & results (xls)

[ Back | Members | Services | Software | Links | Home | email ]

**2009**

**LP-Based Heuristics for Conservative Scales in Orthogonal Packing**
*Authors:*
Gleb
Belov, H. Rohling, Guntram
Scheithauer**Preprint
MATH-NM-06-2009**, *submitted*

The \emph{$d$-Dimensional Orthogonal Packing Problem} (OPP-$d$, $d\ge2$) asks whether all given boxes can be orthogonally packed into a given container without rotations. Many solution methods use \emph{bounds on the solution value}. For example, the simplest bound for OPP is the \emph{volume bound}: if the total volume of the items exceeds that of the container then the instance is infeasible. \emph{Conservative scales} (CS) are modified item sizes such that if OPP is feasible, it is also feasible with the modified sizes. Thus, the volume bound for the modified instance is valid for the original instance. Up to now, CS have been constructed either (i) completely independently in each dimension using \emph{dual-feasible functions} or (ii) by an exact method in the 2D case. Between (i) and (ii), there are possible heuristic algorithms which construct $d$ conservative scales (in $d$ dimensions) simultaneously. Our first efforts in this direction have shown that a simple LP iteration produces results nearly identical with the exact method in smaller time. 3D results are presented as well.
**Keywords:**
*packing, relaxation, conservative scales, dual-feasible functions*

PDF .... 3D test instances

**One-Dimensional
Relaxations and LP Bounds for Orthogonal Packing **
*Authors:*
Gleb
Belov, V. Kartak, H. Rohling, Guntram
Scheithauer*International
Transactions on Operational Research 16(6) 745-766 (2009)*

We
consider the feasibility problem in d-dimensional orthogonal packing
(d >= 2), called 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 1D relaxations of OPP. The ﬁrst
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 to the commonly-used volume bounds from dual-feasible
functions. Moreover, we test the so-called probing (temporary ﬁxing)
of intersection variables of OPP with the aim to strengthen the
relaxations.**Keywords:**
*packing, relaxation,
modeling, conservative scales, dual-feasible function, probing*

http://dx.doi.org/10.1111/j.1475-3995.2009.00713.x

[ Back | Members | Services | Software | Links | Home | email ]

**2007**

**Gomory
Cuts from a Position-Indexed Formulation of 1D Stock Cutting **

*Authors:* Gleb
Belov, Guntram
Scheithauer, C. Alves, J.M. Valério de Carvalho**Published:**
Intelligent Decision Support, A. Bortfeldt, J. Homberger, H. Kopfer,
G. Pankratz, R. Strangmeier (Eds.) Gabler-Verlag, 2008Most
integer programming problems can be formulated in several ways. Some
formulations are better suited for solution by exact methods, because
they have either (i) a strong LP relaxation, (ii) few symmetries in
the solution space, or both. However, solving one formulation, we can
often branch and/or add cutting planes which are implicitly based on
variables of other formulations, working in fact on intersection of
several polytopes. Traditional examples of this approach can be found
in, e.g., (capacitated) routing and network planning where decomposed
models operate with paths or trees, and thus need to be solved by
column generation, but original models operate on separate edges. We
consider such a ‘capacity-extended formulation’, the
so-called arc-flow model, of the 1D cutting stock problem. Its
variables are known to induce effective branching constraints leading
to small and stable branch&bound trees. In this work we explore
Chvátal-Gomory cuts on its variables. The results are positive
only for small instances. Moreover, we compare the results to the
cuts constructed on the variables of the direct model. The latter are
more involved but also more effective.

**Translational
polygon containment**

*Authors:*
Guntram
Scheithauer, T. Romanova, Y. Stoyan**Preprint
MATH-NM-01-2007**
In this paper we present a natural and simple procedure to compute
all feasible allocation points of a (non-convex) polygon within a
(non-convex) polygonal bounded region.

This procedure can be seen as a basis of more sophisticated and eﬃcient algorithms for the same task, or for related problems such as ﬁnding a single placement point.

[ Back | Members | Services | Software | Links | Home | email ]

**2006**

**One-Dimensional
Heuristics Adapted for Two-Dimensional Rectangular Strip Packing**

*Authors:* Gleb
Belov, Mukhacheva E.A., Guntram
Scheithauer *Journal of the Operational
Research Society* 59:823-832, 2008. Advance online publication
4 April 2007;

We consider two-dimensional rectangular strip packing without rotation of items and without the guillotine cutting constraint. We propose two iterative heuristics. The ﬁrst one, SVC(SubKP), is based on a single-pass heuristic SubKP which ﬁlls every most bottom-left free space in a one-dimensional knapsack fashion, i.e. considering only item widths. It appears especially important to assign suitable “pseudo-proﬁts” in this knapsack problem. The second heuristic BS(BLR) is based on the randomized framework BubbleSearch of Lesh and Mitzenmacher (2006). It generates diﬀerent item sequences and runs Bottom-Left-Right (BLR), a simple modiﬁcation of the Bottom-Left heuristic. We investigate the solution sets of SubKP and BLR and their relation to each other. In the tests, SVC(SubKP) improves the results for larger instances of the waste-free classes of Hopper and Turton and, on average, for the tested non-waste-free classes, compared to Alvarez-Valdes et al. (2006), Bortfeldt (2006), and Lesh and Mitzenmacher (2006). BS(BLR) gives the best results in some classes with smaller number of items (20, 40).

[ Back | Members | Services | Software | Links | Home | email ]

**2005**

**A
Node-Flow Model for One-Dimensional Stock Cutting: Robust Branch &
Cut & Price**

**Keywords:**
*branch and bound; cutting and packing; integer programming
formulations*

PDF

[ Back | Members | Services | Software | Links | Home | email ]

**2003**

**A
Class of Subpattern Formulations for 1D Stock Cutting**

*Authors:* Gleb
Belov and Robert
Weismantel

In the classical
Gilmore-Gomory model for the {\em one-dimensional cutting stock
problem} ({\bf 1D-CSP}) we have to deal implicitly with a huge number
of variables representing all feasible patterns. The advantage is a
strong relaxation and absence of symmetries. To reduce the number of
variables, we can restrict them to {\em subpatterns}, \ie, partial
patterns which are combined to produce whole patterns. Each
subpattern can be a part of different resulting patterns; thus, all
patterns have to be numbered, which brings much symmetry into the
model. Moreover, the continuous relaxation may not only have
non-integer pattern application intensities but also overcapacity
patterns, resulting in a weak bound. However, it is possible to
choose a small set of elementary subpatterns so that standard
optimization software can be applied to the model.

**Keywords:**
*cutting, symmetry*

**Models
with Variable Strip Widths for Two-Dimensional Two-Stage Cutting**

*Authors:* Gleb
Belov and Guntram
Scheithauer **Preprint
MATH-NM-17-2003 **We consider several
formulations of two-dimensional two-stage constrained cutting, where
the number of variables is polynomial. Some new models with {\em
variable strip widths} are developed. Symmetries in the search space
are eliminated by {\em lexicographic constraints} which are already
known from the

literature. However, previously known models with fixed strip widths are shown to be more effective. The models are solved with the branch-and-cut algorithm of ILOG CPLEX.

**Keywords:**
*cutting, guillotine, branch-and-cut, symmetry*

**Setup
and Open-Stacks Minimization in One-Dimensional Stock Cutting**

*Authors:* Gleb
Belov and Guntram
Scheithauer * INFORMS
Journal on Computing*, Vol. 19, No.
1, Winter 2007, pp. 27--35

**Keywords:**
*cutting, setup minimization, open stacks,
branch-and-bound, sequencing*

**The
Number of Setups (Different Patterns) in One-Dimensional Stock
Cutting**

*Authors:* Gleb
Belov and Guntram
Scheithauer **Preprint
MATH-NM-15-2003 **The primary
objective in cutting and packing problems is trim loss or material
input minimization (in stock cutting) or value maximization (when
packing into a knapsack). However, in real-life production we usually
have many other objectives (costs) and constraints, for example, the
number of different patterns. We propose a new simple model for setup
minimization (in fact, an extension of the Gilmore-Gomory model for
trim loss minimization) and develop a branch-and-price algorithm on
its basis. The algorithm is tested on problems with industrially
relevant sizes of up to 150 product types. The behavior is
investigated on a broad range of problem classes and significant
differences between instances of a class are found. Allowing even
0.2\% more material input than the minimum significantly improves the
results, this tradeoff has not been investigated in the earlier
literature. Comparison to a state-of-the art heuristic KOMBI shows
mostly better results; to a previous exact approach of Vanderbeck,
slightly worse solutions and much worse LP bound, which is a
consequence of the simplicity of the model.

**Keywords:**
*cutting, pattern reduction, setup minimization,
branch-and-bound, column generation*

**Packing
of convex polytopes into a parallelepiped ***Authors:*
Y. Stoyan, N. Gil, G. Scheithauer, A. Pankratov, I.Magdalina
**Preprint MATH-NM-04-2003, TU
Dresden, April 2003.**

This paper
deals with the problem of packing convex polytopes into a
parallelepiped of minimal height. It is assumed that the polytopes
are oriented, i. e. rotations are not permitted. A mathematical model
of the problem is developed and peculiarities of them are addressed.
Based on these peculiarities a method to compute local optimal
solutions is constructed. Both an approximate and an exact method to
search for local minima of the problem are discussed. The exact
method is a special modification of the duel simplex method. Some
examples are also given.

Postscript,
PDF

**A
Branch-and-Cut-and-Price Algorithm for One-Dimensional Stock Cutting
and Two-Dimensional Two-Stage Cutting**
*Authors:*
Gleb Belov
and Guntram
Scheithauer **Preprint
MATH-NM-03-2003 --- ****Revised
in October 2004***European Journal of
Operational Research, Volume 171, Issue 1, 16 May 2006, Pages 85-106
*

The one-dimensional cutting stock problem
({\bf 1D-CSP}) and the two-dimensional two-stage guillotine
constrained cutting problem ({\bf 2D-2CP}) are considered in this
paper. The Gilmore-Gomory model of these problems has a very strong
continuous relaxation which provides a good bound in an LP-based
solution approach. In recent years, there have been several efforts
to attack the one-dimensional problem by LP-based branch-and-bound
with column generation (called branch-and-price) and by
general-purpose {\sc Chv\'{a}tal-Gomory} cutting planes. When cutting
planes are added to the LP relaxation, the pricing problem becomes
very complex and often cannot be solved optimally in an acceptable
time. Moreover, the modeling and implementation of its solution
method as well as of the cutting plane apparatus for the chosen kind
of cuts requires much effort. We develop a new upper bound for this
pricing problem. We improve the numerical stability of the cutting
plane algorithm and integrate mixed-integer {\sc Gomory} cuts. For
2D-2CP we propose a pricing procedure which enables the search for
strips of different widths without repetitions. Various branching
strategies and tools such as pseudo-costs and reduced cost bounding
are investigated. Tests show that, for 1D-CSP, general-purpose cuts
are useful only in exceptional cases. However, for 2D-2CP their
combination with branching is more effective than either approach
alone and mostly better than other methods from the literature.
**Keywords:**
*cutting, cutting planes, column
generation, branch-and-bound*

PS PDF Test instances 1D-BPP: hard28 2D-2CP

Why the numerical
results are different than in Belov's thesis

[ Back | Members | Services | Software | Links | Home | email ]

2002

**Construction
of a Phi-function for two convex polytopes ***Authors:*
Y. Stoyan, J. Terno, G. Scheithauer, N. Gil, T. Romanova,
**Applicationes Mathematicae 29.2
(2002) 199 - 218.**

In this paper,
the analytical description of $\Phi $-functions for two convex
polytopes is investigated. These $\Phi $-functions can be used for
mathematical modelling of packing problems in the three-dimensional
space. Only translations of the polytopes are considered. The
approach consists of two stages. At first the 0-level surface of a
$\Phi $-function is constructed, and secondly, the surface is
extended to get the $\Phi $% -function. The method for constructing
the 0-level surface is described in detail, and therefore also for
computing a $\Phi$-function.

Preprint version: Postscript,
PDF,

Back
**Phi-functions for
primary 2D-objects ***Authors:*
Y. Stoyan, J. Terno, G. Scheithauer, N. Gil, T. Romanova, **Studia
Informatica Universalis 2.1 (2002) 1 - 32.**

Within the field of Cutting and Packing problems the placement or
allocation of smaller objects within a larger region has high
importance. In order to develop efficient solution approaches, the
interaction of two placed objects has to be modelled in a suitable
manner. In this paper we follow the concept of Phi-functions. A
comprehensive investigation of all mutual positions of two so-called
primary objects is given and corresponding Phi-functions are
presented for each suitable pair of two such primary objects.

Preprint version: Postscript,
PDF,

Back
**Tighter bounds
for the gap and non-IRUP constructions in the one-dimensional cutting
stock problem** *Authors:*
Jürgen Rietz and Guntram Scheithauer, **Optimization
51.6 (2002) 927 - 963.**

The
one-dimensional cutting stock problem is investigated with respect to
the difference between the optimal function value of the discrete
problem and its continnuous relaxation. A tighter bound for this gap
is presented, followed by some non-IRUP constructions. Finally,
instances with gap 7/6 are constructed, the largest gap known so far.

Preprint version: Postscript,
PDF,

Back
**Phi-functions for
primary 3D-objects** *Authors:*
Y. Stoyan, G. Scheithauer, D. Pridatko, T. Romanova, N. Gil **Preprint
MATH-NM-15-2002, TU Dresden, November 2002.**

Within the field of packing problems the placement of 3D objects
is of great importance. In order to develop efficient solution
approaches, the interaction of two placed objects has to be modelled
in a suitable manner. In this paper we follow the concept of
Phi-functions. Phi-functions are presented for each suitable pair of
so-called primary 3D objects from the collection of objects with
spherical, parallelepipedal or cylindrical frontiers.

Postscript,
PDF,

Back
**Families of
Non-IRUP instances of the one-dimensional cutting stock problem**
*Authors:*
Juergen Rietz, Guntram Scheithauer and Johannes Terbo **Discrete
Appl. Math. 121 (2002) 229--245.**

In
case of the one-dimensional cutting stock problem (CSP) one can
observe for any instance a very small gap between the integer optimal
value and the continuous relaxation bound. These observations have
initiated a series of investigations. An instance possesses the
integer round-up property (IRUP) if its gap is smaller than 1. It is
well-known that there exist instances of the CSP having a gap greater
than 1 but there is not known any instance with gap at least 2. In
this paper, families of non-IRUP instances are presented and methods
to construct such instances are given. Especially, an instance with
gap equal to 10/9 is obtained. Furthermore, an equivalence relation
for instances of the CSP is considered to become independent from the
real size parameters.

Preprint version: Postscript,
PDF,

Back
**A Cutting Plane
Algorithm for the One-Dimensional Cutting Stock Problem with Multiple
Stock Lengths** *Authors:*
Gleb Belov and Guntram Scheithauer **EJOR
141/2 (2002), Psecial Issue on Cutting and Packing, 274--294.**

A cutting
plane approach combining Chvatal-Gomory cutting planes with column
generation is generalized for the case of multiple stock lengths in
the one-dimensional cutting stock problem. Appropriate modifications
of the column generation procedure and the rounding heuristic are
proposed. A comparison with the branch-and-price method for the
problem with one stock type and representative test results are
reported.

Preprint version: Postscript,
PDF,

Back
**Phi-functions for
complex 2D-objects** *Authors:*
Y. Stoyan, M. Gil, T. Romanova and G. Scheithauer **Preprint
MATH-NM-02-2002, TU Dresden, April 2002.**

Within two-dimensional cutting and packing problems with
irregular shaped objects, the concept of Phi-functions has been
proven to be very helpful for several solution approaches. In order
to construct such Phi-functions a previous work, in which so-called
primary objects are considered, is continued. Now Phi-functions are
constructed for pairs of objects which can be represented as a finite
combination (union, intersection, complement) of primary objects
which allows the handling of arbitrary shaped objects by appropriate
approximations of sufficient accuracy.

Postscript,
PDF,

Back
**Solving
One-Dimensional Cutting Stock Problems with Multiple Stock Material
Lengths Using Cutting Plane Approach**
*Authors:*
G. Scheithauer and G. Belov **Operations
Research Proceedings 2001, Springer-Verlag Berlin Heidelberg,
285--292, 2002. **

For exactly solving
the one-dimensional cutting stock problem (CSP) with several stock
material lengths, a cutting plane approach (CPA) is proposed. This
work is a continuation of [12] where firstly column generation
technique and CPA have been combined for the CSP with identical stock
material pieces. In order to ensure efficient implementation of the
generation problems in case of no and of additional cutting planes,
some modifications of known methods have been performed. The
efficiency of the algorithm is demonstrated by extensive numerical
results.

Back

**2001**

**Solving
one-dimensional cutting stock problems exactly with a cutting plane
algorithm** *Authors:*
Guntram Scheithauer, Johannes Terno, Antje Müller and Gleb
Belov, **JORS 52 (2001) 1390-1401**

When solving the one-dimensional cutting stock problem (CSP) as
an integer linear programming problem one has to overcome
computational difficulties arising from the integrality condition and
the huge number of variables. In the usual solution approach the
continuous relaxation is solved via column generation technique
followed by an appropriate rounding of the in general non-integer
solution. Obviously, in this way an optimal solution cannot be
obtained for any instance. In order to compute a proved optimal
solution, techniques like branch-and-bound have to be applied.

In
this paper we present another exact solution approach for the CSP
which is based on the cutting plane method. We investigate how to
compute and how to use suitable cutting planes in an algorithm which
is based on column generation. Results of extensive computational
experiments are reported.

Preprint version: Postscript,
PDF,

Back
**Packing of
various radii solid spheres into a parallelepiped ***Authors:*
Y. Stoyan, G. Yaskov, G. Scheithauer, **Preprint
MATH-NM-17-2001, TU Dresden.**

The
paper considers the optimization problem of packing various solid
spheres into a parallelepiped with minimal height. Based on a
corresponding mathematical model the peculiarities of the problem are
investigated. Regarding these peculiarities a solution method is
offered. The method includes three stages: searching for some
approximations (extreme points) to local minima; improving the
approximations by a neighborhood search; computing local minima using
these approximations as starting points. Preliminary numerical
results for examples with up to 60 spheres are also given.

Postscript, PDF,

Back

**2000**

**A
Cutting Plane Approach for the One-Dimensional Cutting Stock Problem
with Multiple Stock Lengths** *Authors:*
Gleb Belov
and Guntram
Scheithauer, **To
appear***in
EJOR, Special Issue on Cutting and Packing.*

A cutting plane approach combining Chvatal-Gomory cutting planes
with column generation is generalized for the case of multiple stock
lengths in the one-dimensional cutting stock problem. Appropriate
modifications of the column generation procedure and the rounding
heuristic are proposed. A comparison with the branch-and-price method
for the problem with one stock type and representative test results
are reported. * Benchmark results:*
Postscript Test
instances

[ Back | Members | Services | Software | Links | Home | email ]

**Solving
the General One-Dimensional Cutting Stock Problem with a Cutting
Plane Approach** *Authors:*
Gleb Belov and Guntram
Scheithauer, **Preprint
MATH-NM-11-2000, TU Dresden.**

For
exactly solving the one-dimensional cutting stock problem with
several stock material lengths, a cutting plane approach is proposed
and successfully combined with column generation. In order to ensure
an efficient implementation, some modifications of known methods
(Dynamic Programming, Branch-and-Bound, piece dominance criterion)
have been performed. The efficiency of the algorithm is demonstrated
by extensive numerical results. *File:* Postscript

[ Back | Members | Services | Software | Links | Home | email ]

**Tighter
bounds for the gap and non-IRUP constructions in the one-dimensional
cutting stock problem** *Authors:*Jürgen
Rietz and Guntram
Scheithauer, **Preprint
MATH-NM-12-2000, TU Dresden.**

The
one-dimensional cutting stock problem is investigated with respect to
the difference between the optimal function value of the discrete
problem and its continnuous relaxation. A tighter bound for this gap
is presented, followed by some non-IRUP constructions. Finally,
instances with gap 7/6 are constructed, the largest gap known so far.
*File:* Postscript,
DVI

[ Back | Members | Services | Software | Links | Home | email ]

**Construction
of a $\Phi$-function for two convex polytopes**
*Authors:*Yurij
Stoyan, Mikolay Gil, Tatiana Romanova, Johannes Terno and Guntram
Scheithauer, **Preprint
MATH-NM-12-2000, TU Dresden.**

In
this paper, the analytical description of $\Phi $-functions for two
convex polytopes is investigated. These $\Phi $-functions can be used
for mathematical modelling of packing problems in the
three-dimensional space. Only translations of the polytopes are
considered. The approach consists of two stages. At first the 0-level
surface of a $\Phi $-function is constructed, and secondly, the
surface is extended to get the $\Phi $% -function. The method for
constructing the 0-level surface is described in detail, and
therefore also for computing a $\Phi$-function. *File:*
Postscript , DVI

[ Back | Members | Services | Software | Links | Home | email ]

**Facet-defining
inequalities for the cutting stock problem**
*Authors:*
Guntram
Scheithauer and Johannes Terno
**Pesquisa Operational 19/2 (2000)
131-144 (Preprint MATH-NM-10-1997, TU Dresden 1997)**

In this paper the polyhedron of the cutting stock problem is
investigated with respect to facet-defining inequalities. For some
classes of valid inequalities this property is proved. *File
of first version:* Postscript
(42 kb), DVI
(19 kb)

[ Back | Members | Services | Software | Links | Home | email ]

**An
Efficient Approach for the Multi-Pallet Loading Problem**
*Authors:*
Guntram
Scheithauer, Johannes Terno, Uta Sommerweiss and Jan
Riehme **EJOR
123/2 (2000) 372-381**

The
Distributor's or Multi-Pallet Loading Problem is considered in this
paper. This problem is to load a set of distinct products with given
quantities on pallets (or in containers) and to minimize the number
of pallets needed. The theoretical objective of finding the best
space utilization is restricted by a list of practical aspects
(technological constraints, weight distribution over the pallet,
stability aspects, etc.). Keeping in mind a general branch and bound
framework an efficient heuristic for the considered multi-pallet
loading problem is developed. The three-dimensional solution approach
uses in the kernel a layer-wise loading strategy with optimal
two-dimensional loading patterns. Computational experiments show the
efficiency of the proposed algorithms. *File
of first version:* Postscript
, DVI

[ Back | Members | Services | Software | Links | Home | email ]

**1999**

**Solving
one-dimensional cutting stock problems exactly with a cutting plane
algorithm** *Authors:*
Guntram
Scheithauer,Johannes
Terno, Müller, A., Belov, G.
**Preprint MATH-NM-06-1999, TU
Dresden.** **To
appear***in the Journal of the
Operational Research Society.*

When
solving the one-dimensional cutting stock problem (CSP) as an integer
linear programming problem one has to overcome computational
difficulties arising from the integrality condition and the huge
number of variables. In the usual solution approach the continuous
relaxation is solved via column generation technique followed by an
appropriate rounding of the in general non-integer solution.
Obviously, in this way an optimal solution cannot be obtained for any
instance. In order to compute a proved optimal solution, techniques
like branch-and-bound have to be applied.

In this paper we
present another exact solution approach for the CSP which is based on
the cutting plane method. We investigate how to compute and how to
use suitable cutting planes in an algorithm which is based on column
generation. Results of extensive computational experiments are
reported. *Files:*
Postscript (82
kb), DVI (38
kb) Test instances

[ Back | Members | Services | Software | Links | Home | email ]

**Tighter
Relaxations for the Cutting Stock Problem**
*Authors:*
Nitsche, C., Guntram
Scheithauer,Johannes
Terno **EJOR
112 (1999) 654-663 (Preprint MATH-NM-01-1997, TU Dresden).**

In the cutting stock problem (CSP) a given order for smaller
pieces has to be cut from larger stock material in such a way that
the number of stock material needed is minimal. Based on the
classical integer linear programming model the common solution
technique consists of solving the corresponding continuous relaxation
problem followed by several heuristics which construct integer
solutions.

In many cases an optimal solution can be obtained
quickly in this way. But for instances which do not possess the
integer round-up property the optimality of the solution obtained
cannot be verified by means of the LP bound. In order to overcome
this non-satisfactory situation, two tighter relaxations of the CSP
are proposed, and results of theoretical and numerical investigations
are presented. *Files:* Postscript
(50 kb), DVI (22 kb)

[ Back | Members | Services | Software | Links | Home | email ]

**1998**

**4-Block
Heuristic for the Rectangle Packing Problem** *Authors:*
Guntram
Scheithauer,, Uta Sommerweiss **EJOR**
108 (1998), p.509-526

In this paper the rectangle packing problem
(RPP) is considered. The RPP consists in finding a packing pattern of
small rectangles within a larger rectangle such that the area
utilization is maximized.

We develop new heuristics for the RPP
which are based on the G4-heuristic for the pallet loading problem.
In addition to the general RPP we take also into account further
restrictions which are of practical interest. *File:*
Postscript (106
kb)

[ Back | Members | Services | Software | Links | Home | email ]

[ Back | Members | Services | Software | Links | Home | email ]