Publications of the CaPaD-group


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


Abstracts & Full Texts

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:


[ 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 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

PS    PDF    



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

PS    PDF    



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

PS    PDF     Test instances

 

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

PS    PDF     Test instances    

 

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 ]