2002
[ Members | Services | Software | Links | Home | email ]
2012
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
[ Back | Members | Services | Software | Links | Home | email ]
2011
Conservative scales in packing problems
Authors:
Gleb
Belov, Vadim M. Kartak, Heide Rohling, and Guntram
Scheithauer
Preprint
MATH-NM-03-2011 from August 4, 2011, accepted in Operations Research Spectrum
Updated on November 25, 2011: fast MCS heuristics, geometric interpretations
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
The following talks present some of the paper's results:
[ Back | Members | Services | Software | Links | Home | email ]
2009
A Branch-and-Price Graph-Theoretical Algorithm for Orthogonal-Packing Feasibility
Authors:
Gleb
Belov and Heide Rohling
Preprint
MATH-NM-10-2009, submitted
We consider the feasibility problem OPP in higher-dimensional orthogonal packing: given a set of $d$-dimensional ($d\ge2$) rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. The well-known 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 the 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 significant speedup and stabilization of the algorithm.
Keywords:
Packing, branch-and-price, dimension reduction, interval graph
PDF .... 3D test instances
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 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 to 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:
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, 2008
Most
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.
Keywords:
integer programming, cutting, cutting planes,
column generation
PDF
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 efficient
algorithms for the same task, or for related problems such as finding
a single placement point.
Keywords:
mathematical modelling, cutting and packing,
optimization
PDF
[ 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; doi: 10.1057/palgrave.jors.2602393
We consider two-dimensional rectangular strip
packing without rotation of items and without the guillotine cutting
constraint. We propose two iterative heuristics. The first one,
SVC(SubKP), is based on a single-pass heuristic SubKP which fills
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-profits” in
this knapsack problem. The second heuristic BS(BLR) is based on the
randomized framework BubbleSearch of Lesh and Mitzenmacher (2006). It
generates different item sequences and runs Bottom-Left-Right
(BLR), a simple modification 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).
Keywords:
strip packing, heuristics, greedy, stochastic
search, knapsack
PDF
[ Back | Members | Services | Software | Links | Home | email ]
2005
A
Node-Flow Model for One-Dimensional Stock Cutting: Robust Branch &
Cut & Price
Authors: Gleb
Belov, Adam Letchford, Eduardo Uchoa
Tech.
report RPEP Vol.5 no.7, Universidade Federal Fluminense, Engenharia
de Produ\c{c}\~ao, Niter\'oi, Brazil
Branch-and-Cut-and-Price
(BCP) algorithms are branch-and-bound algorithms where both row
generation (separation) and column generation (pricing) are
performed. We say that such an algorithm is *robust* when the
separation and pricing subproblems are guaranteed to remain tractable
during its execution. However, this depends on the choice of the
underlying model for the problem. The first such model for 1D stock
cutting, to our knowledge, was the Arc-Flow Formulation of V. de
Carvalho. We propose another model based on graphs, a Node-Flow Model
which is in fact a CVRP model. We investigate its theoretical
properties and present numerical results for BCP.
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
Preprint
MATH-NM-16-2003 -- Revised in November
2004
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. Probably
the most complex auxiliary criteria of a solution are the number of
different cutting patterns (setups) and the maximum number of open
stacks during the cutting process. There are applications where the
number of stacks is restricted to two. We design a sequential
heuristic to minimize material input and show its high effectiveness
for this purpose. Then we extend it to restrict the number of open
stacks to any given limit. Then, the heuristic is simplified and
integrated into a setup minimization approach in order to combine
setup and open stacks minimization. To get a smaller number of open
stacks, we may split up the problem into several parts of smaller
dimension. Different solutions are evaluated in relation to the
multiple objectives using the {\sc Pareto} criterion.
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) 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 ]