Publications of Dr. Guntram Scheithauer

  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1982

  • Back

    Abstracts

    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
    4OR 2/1 (2004) 69-84.
    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.
    Postscript
    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.
    CEJOR 11/4 (2003) 389-408.
    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

    Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm
    Author: Guntram Scheithauer,
    Inderfurth, K. (ed.) et al., Operations research proceedings 1999. Selected papers of the symposium (SOR '99), Magdeburg, Germany, September 1-3, 1999. Berlin: Springer. 86-91 (2000).
    Postscript
    Back
    Facet-defining inequalities for the cutting stock problem
    Authors: Guntram Scheithauer and Johannes Terno
    Pesquisa Operational 19/2 (2000) 131-144
    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.
    Preprint version: Postscript, PDF
    Back
    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.
    Preprint version: Postscript, PDF
    Back
    Class of 0-level $\Phi$-functions of point sets which have circumferential or polygonal frontiers (in Russian),
    Authors: Y.Y. Stoyan, G. Scheithauer, N.I. Gil, T.E. Romanova and I.V. Magdalina
    J. of Mech. Engineering 3 (2000) 1-2, 117--123.
    A structural approach for constructing the 0-level surface of Phi-functions of point sets in two-dimensional space which have circumferential or polygonal frontiers is considered. The approach can be used for solving optimization problems of geometric design for constructing Phi-functions of a pair of geometric objects having arbitrary spatial shapes.
    Back
    1999

    Tighter Relaxations for the Cutting Stock Problem
    Authors: Christiph Nitsche, Guntram Scheithauer and Johannes Terno
    EJOR 112 (1999) 654-663
    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.
    PDF
    Back
    Numerical investigations on the MIRUP of the 2-stage guillotine cutting stock problem
    Authors: Jan Riehme, Guntram Scheithauer and Johannes Terno
    J. of Math. Eng. 2 (1999) 3/4, 101-107
    The MIRUP (Modified Integer Round-Up Property) leads to an upper bound for the gap between the optimal value of the integer problem and that of the corresponding continuous relaxation rounded up. This property is known to hold for many instances of the one-dimensional cutting stock problem but there are not known so far any results with respect to the two-dimensional case.
    In this paper we investigate numerically three variants of the so-called 2-stage guillotine cutting stock problem with respect to the MIRUP. The variants differ by allowing either only horizontal or only vertical or horizontal and vertical guillotine cuts in the first stage.
    Within a sample of 900 randomly generated instances there did not arise any instance with gap larger than 1. Moreover, for more than 60% of the instances an optimal solution was found.
    Postscript
    Back
    LP-based bounds for the Container and Multi-Container Loading Problem
    Author: Guntram Scheithauer
    Int. Trans. in Op. Res. 6 (1999) 199-213
    In this paper we develop new bounds for problems of optimal packing of small (rectangular-shaped) pieces within one or several larger containers, that are bounds for the Container Loading Problem (CLP) and the Multi-Container Loading Problem (MCLP).
    We propose new relaxations for the CLP and MCLP which lead to linear programming problems. We discuss a solution approach based on a column generation technique. Results of computational tests are also given.
    Postscript
    Back
    Optimale Positionierung beim Vollholzzuschnitt durch automatisierte Fehlererkennung
    Authors: Guntram Scheithauer und Johannes Terno
    Wiss. Z. TU Dresden 46 (1999) 2, 78--81.
    The progress in automatic defect detection in the wood industry allows now the usage of improved optimization models and solution methods in order to get a higher yield in cutting processes.
    Since the wooden material contains defects, quality restrictions of the products are of high importance which have to be fulfilled in the rip- and/or cross-cutting process.
    This is done traditionally by human labour.
    By using automated defect detection and corresponding image analysis, now it is possible to integrate this quality control into the optimization process.
    In this paper, the modelling of one- and two-dimensional cutting problems is considered as well as efficient solution approaches are discussed.
    Postscript
    Back
    1998

    4-Block Heuristic for the Rectangle Packing Problem
    Authors: Guntram Scheithauer and Uta Sommerweiss
    EJOR 108 (1998), 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.
    PDF
    Back
    New Cases of the Cutting Stock Problem Having MIRUP
    Authors: Christoph Nitsche, Guntram Scheithauer and Johannes Terno
    Math. Meth. of OR (ZOR) 48.1 (1998) 105--116.
    The modified integer round-up property (MIRUP) for a linear integer minimization problem means that the optimal value of this problem is not greater than the optimal value of the corresponding LP relaxation rounded up plus one.
    In earlier papers the MIRUP was shown to hold for the so-called divisible case and some other subproblems of the one-dimensional cutting stock problem.
    In this paper we extent the results by using special transformations, proving the existence of non-elementary patterns in the solution, and involving more detailed greedy techniques.
    PDF
    Back
    Families of Non-IRUP instances of the one-dimensional cutting stock problem
    Authors: Guntram Scheithauer, Johannes Terno and Jürgen Rietz
    Preprint MATH-NM-09-1998, TU Dresden 1998
    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 we present families of non-IRUP instances and give methods to construct such instances. Furthermore, an equivalence relation for instances of the CSP is considered to become independent from the real size parameters.
    Postscript
    Back
    1997

    Equivalence and Dominance for Problems of Optimal Packing of Rectangles
    Author: Guntram Scheithauer
    Ricerca Operativa 27 (1997) 83, 3--34.
    In this paper we consider the problem of optimal packing of small rectangles within a larger rectangle.
    The topic consists of a comprehensive investigation of equivalence and dominance of packing patterns. Using suitable kinds of equivalence and dominance, the goal is to develop an efficient branch and bound algorithm with which problems of practical interest may be solved exactly.
    Postscript
    Back
    A Heuristic Approach for Solving the Multi-Pallet Packing Problem
    Authors: Guntram Scheithauer and Johannes Terno
    Decision making under conditions of uncertanty (cutting-packing problems), Ufa State Aviation Technical Univ. 1997, 140-154.
    We consider the Distributer's Pallet Packing Problem. This problem is to pack a set of distinct products with given quantities in greater volumes (pallets, containers) and to minimize the number of used volumes.
    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 packing problem is developed.
    The three-dimensional solution approach uses in the kernel a layer-wise packing strategy with optimal two-dimensional packing patterns.
    Linear Programming lower bounds for the number of pallets needed to pack the total consignment are developed. Computational experiments show the efficiency of the proposed algorithms.
    Postscript
    Back
    The Properties IRUP and MIRUP for the Cutting Stock Problem
    Authors: Guntram Scheithauer and Johannes Terno
    Decision making under conditions of uncertanty (cutting-packing problems), Ufa State Aviation Technical Univ. 1997, 16-32.
    The integer round-up property (IRUP) holds for an integer linear minimization problem if, for any instance, the optimal value equals the linear programming (LP) relaxation lower bound rounded up, and the modified integer round-up property (MIRUP) holds if the optimal value is not greater than the optimal value of the corresponding LP relaxation rounded up plus one.
    In recent years, the well known cutting stock problem gets a growing interest with respect to investigations for IRUP and MIRUP.
    In this paper we summarize work done and discuss open questions.
    Postscript
    Back
    The value correction method for packing of irregular shapes
    Authors: Guntram Scheithauer, Oksana Y. Sergeyeva and Johannes Terno
    Decision making under conditions of uncertanty (cutting-packing problems), Ufa State Aviation Technical Univ. 1997, 261-269.
    We consider the packing of irregular shapes in a strip of given width such that the length of the occupied part is minimized. Starting with a first allocation of the objects with a greedy-like technique the placement of every object is evaluated and with respect to the evaluation a new packing pattern is generated. Continueing this foregoing we select the best pattern. Numerical experience show a good performance of the algorithm.
    Postscript
    Back
    Cutting and Packing: An Annotated Bibliography
    Authors: Harald Dyckhoff (RWTH Aachen), Guntram Scheithauer and Johannes Terno
    in: Annotated Bibliographies in Combinatorial Optimization, M. Dell'Amico, F. Maffioli, S. Martello (eds.), Wiley 1997, 393--412.
    In drawing up this bibliography, we have concentrated on publications that appeared in 1990 or later (with some exceptions). For the literature prior to 1990 we refer to the books and surveys listed in the first section, especially to the book of Dyckhoff/Finke(1992).
    In this paper we have included more than 130 annotated references. A BiBTeX data base containing more than 1100 entries related to C&P can be obtained from the authors.
    Postscript
    Back
    Theoretical Investigations on the Modified Integer Round-Up Property for the One-Dimensional Cutting Stock Problem
    Authors: Guntram Scheithauer and Johannes Terno
    Oper. Res. Lett. 20 (1997) 93--100.
    Many numerical computations show a small difference only between the optimal value of the one-dimensional cutting stock problem and that of its corresponding linear programming relaxation.
    In this paper we investigate the one-dimensional cutting stock problem with respect to the modified integer round-up property (MIRUP) and present some results on subproblems having the MIRUP.
    PDF, Postscript
    Back
    LP-bounds for the container and multi-container loading problem
    Author: Guntram Scheithauer
    Zimmermann, Uwe (ed.) et al., Operations research proceedings 1996. Selected papers of the symposium, SOR'96, Braunschweig, Germany, September 3-6, 1996. Berlin: Springer. 123-128 (1997).
    Postscript
    Back
    1996

    The G4-Heuristic for the Pallet Loading Problem
    Authors: Guntram Scheithauer and Johannes Terno
    JORS 47 (1996) 511--522
    A new heuristic to the well-known (two-dimensional orthogonal) pallet loading problem (PLP) is proposed in this paper. This heuristic referred to as G4-heuristic is based on the definition of the so-called G4-structure of packing patterns. The G4-structure is a generalization of the common used block structure of packing patterns which requires the same orientation of packed boxes within each block.
    The G4-heuristic yields in approximately 99% of the test instances an optimal solution and solves all instances exactly where at most 50 boxes are contained in an optimal packing.
    Although the algorithm is pseudo-polynomial the computational experiments reported show that also instances with more than 200 packed boxes in an optimal solution can be handled with a small amount of computational time. Moreover, so far there is not known any instance where the gap between optimal value and the value obtained by the G4-heuristic is larger than 1 box.
    Postscript
    Back
    The Solution of Two-stage Guillotine Cutting Stock Problems Having Extremely Varying Order Demands
    Authors: Jan Riehme, Guntram Scheithauer and Johannes Terno
    EJOR 91 (1996) 543-552
    In this paper the solution of two-stage guillotine cutting stock problems is considered. Especially such problems are under investigation where the sizes of the order demands differ in a large range.
    We propose a new approach dealing with such situations and compare it with the classical Gilmore/Gomory approach. We report results of extensive numerical experiments which show the advantages of the new approach.
    Postscript
    Back
    A new heuristic for the Pallet Loading Problem
    Authors: Guntram Scheithauer and Johannes Terno
    Operations Research Proceedings 1995, Springer-Verlag Berlin Heidelberg (1996) 84--89
    In this paper we analyse the structure of optimal packing patterns and we introduce the denotation of G4-structure. Then we propose a new heuristic for solving the PLP. Since the algorithm is based on dynamic programming it is of pseudo-polynomial type. The computational experiments show that instances having more than 200 items in an (optimal) packing pattern can be handled with small computational amount of time.
    Postscript
    Back
    Auftragsoptimierung bei Zuschnitt- und Packungsproblemen als ganzzahliges lineares Optimierungsmodell
    Authors: Guntram Scheithauer and Johannes Terno
    Wiss. Z. TU Dresden, 45 (1996) 6, 44-48.
    The paper deals with the modelling of various cutting and packing problems as an integer linear programming problem. For this the column generation method is an efficient solution method especially to get a so-called residual problem. An integer feasible solution for the initial problem is found with a greedy-solution of the residual problem. Thereby the introduced Modified Integer Round-Up Property is helpful. The general framework is illustrated by results for various special problems.
    Postscript
    Back
    Dreidimensionale Packungsprobleme (Auftragsoptimierung auf Europaletten) (in German)
    Authors: Johannes Terno, Guntram Scheithauer, Jan Riehme und Uta Sommerweiss
    Working Paper 1996, Dresden University of Technology
    We consider the Multi-Pallet Loading Problem. This problem is to pack a set of distinct products with given quantities in greater volumes (pallets, containers) and to minimize the number of used volumes.
    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 generalized layer-wise packing strategy with optimal two-dimensional packing patterns. Computational experiments show the efficiency of the proposed algorithms.
    Back
    A New Heuristic Approach for Solving the Multi-Pallet Packing Problem
    Authors: Guntram Scheithauer and Johannes Terno
    Preprint MATH-NM-03-1996, Dresden University of Technology
    We consider the Distributer's Pallet Packing Problem. This problem is to pack a set of distinct products with given quantities in greater volumes (pallets, containers) and to minimize the number of used volumes.
    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 packing problem is developed.
    The three-dimensional solution approach uses in the kernel a layer-wise packing strategy with optimal two-dimensional packing patterns.
    Linear Programming lower bounds for the number of pallets needed to pack the total consignment are developed. Computational experiments show the efficiency of the proposed algorithms.
    Postscript
    Back
    1995

    A branch and bound algorithm for solving one-dimensional cutting stock problems exactly
    Authors: Guntram Scheithauer and Johannes Terno
    APLICATIONES MATHEMATICAE 23, 2 (1995) 151--167
    Many numerical computations reported in the literature show an only small difference between the optimal value of the one-dimensional cutting stock problem (1CSP) and that of its corresponding linear programming relaxation. Moreover, theoretical investigations have proven that this difference is smaller than 2 for a wide range of subproblems of the general 1CSP.
    In this paper we give a branch and bound algorithm to compute optimal solutions for instances of the 1CSP. Numerical results are presented of about 900 randomly generated instances with up to 100 small pieces and all of them are solved to optimality.
    Postscript
    Back
    Numerical investigations on the MIRUP of the 2-stage guillotine cutting stock problem
    Authors:Jan Riehme, Guntram Scheithauer and Johannes Terno
    Preprint MATH - NM - 17 - 1995, TU Dresden.
    The MIRUP (Modified Integer Round-Up Property) leads to an upper bound for the gap between the optimal value of the integer problem and that of the corresponding continuous relaxation rounded up. This property is known to hold for many instances of the one-dimensional cutting stock problem but there are not known so far any results with respect to the two-dimensional case. In this paper we investigate numerically three variants of the so-called 2-stage guillotine cutting stock problem with respect to the MIRUP. The variants differ by allowing either only horizontal or only vertical or horizontal and vertical guillotine cuts in the first stage. Within a sample of 900 randomly generated instances there did not arise any instance with gap larger than 1. Moreover, for more than 60 percent of the instances an optimal solution was found.
    PDF, Postscript
    Back
    The solution of packing problems with pieces of variable length and additional allocation constraints
    Author: Guntram Scheithauer
    Optimization 34 (1995) 81--96
    In this paper one-dimensional partitioning and packing problems of the following type are investigated. The pieces, which are to be packed, are assumed to have a variable length in a given range. Furthermore, the placement of any packed piece has to fulfill additional allocation constraints. The value of a piece is dependent affine linearly on its length. Find a feasible partition or packing, resp., with maximum total value.
    For these problems mixed-integer optimization models with linear constraints are developed and suitable solution methods are discussed. Especially, a branch and bound algorithm and an algorithm based on the so-called forward state strategy are proposed.
    Postscript
    Back
    The Modified Integer Round-Up Property of the One-Dimensional Cutting Stock Problem
    Authors: Guntram Scheithauer and Johannes Terno
    EJOR 84 (1995) 562--571
    A linear integer minimization problem (IP) has the modified integer round-up property (MIRUP) if the optimal value of any instance of IP is not greater than the optimal value of the corresponding LP relaxation problem rounded up plus one.
    The aim of this paper is to investigate numerically whether the MIRUP holds for the one-dimensional cutting stock problem. The computational experiments carried out with a lot of randomly generated instances of the one-dimensional cutting stock problem show, that for all instances an integer solution fulfills the MIRUP. Moreover, in most cases the optimal value equals the round-up optimal value of the corresponding LP relaxation.
    Similarly, the approach proposed to verify the MIRUP is usable as a new heuristic procedure for solving one-dimensional cutting stock problems. This heuristic always leads to very good solutions being optimal in the most cases.
    PDF, Postscript
    Back
    1994

    A Polynomial Time Algorithm for the Guillotine Pallet Loading Problem
    Authors: Alexander G. Tarnowski, Johannes Terno and Guntram Scheithauer
    INFOR 32 (1994) 275--287
    A polynomial time algorithm is presented for solving the two-dimensional guillotine cutting stock problem where all small rectangles are of the same dimensions (generating pallet loading patterns). It is based on the initial problem decomposition into three subproblems. Two of these subproblems are solved by dynamic programming recurrence in polynomial time and the third subproblem is solved during constant time. This algorithm requires the minimization of linear modulo functions. A polynomial time algorithm is used for this purpose.
    Postscript
    Back
    On the MAXGAP Problem for Cutting Stock Problems
    Author: Guntram Scheithauer
    J.Inform.Process.Cybernet.(EIK) 30 (1994) 2, 111--117
    The MAXGAP problem of a linear integer optimization problem P consists in determining the maximum difference (gap) d(P) between the optimal value z*(E) of an instance E in P. and the LP bound z_c(E) with respect to all E in P.
    In the case of the one-dimensional cutting stock problem (1D CSP) it is known that d(1D CSP)>= 1 + 5/132 but there is also a conjecture that d(1D CSP) <= 2.
    In this paper we show that in the case of the restricted exact 2-stage two-dimensional cutting stock problem (RE2 CSP) the maximum gap increases at least linearly in the number m of pieces. It holds d(RE2 CSP)> m/3.
    For the (non-restricted) exact 2-stage two-dimensional cutting stock problem (E2 CSP) an example is given such that d(E2 CSP)>= 2 (1 + 5/132 )> 2.075 follows which yields also a lower bound for the general two-dimensional cutting stock problem.
    Furthermore some consequences for higher-dimensional cutting stock problems and with respect to applications are discussed.
    Postscript
    Back
    1993

    Theoretical Investigations on the Modified Integer Round-Up Property for the One-Dimensional Cutting Stock Problem
    Authors: Guntram Scheithauer and Johannes Terno
    Preprint MATH - NM - 12 - 1993, TU Dresden.
    Many numerical computations show a small difference only between the optimal value of the one-dimensional cutting stock problem and that of its corresponding linear programming relaxation.
    In this paper we investigate the one-dimensional cutting stock problem with respect to the modified integer round-up property (MIRUP) and present some results on subproblems having the MIRUP.
    PDF, Postscript
    Back
    Modelling of Packing Problems
    Authors: Guntram Scheithauer and Johannes Terno
    Optimization 28 (1993) 63--84
    In this paper we develop linear optimization models with continuous and 0/1-variables for packing problems with convex and non-convex polygons.
    The number of 0/1-variables is essentially reduced in comparison to Beasley (1985). This reduction is based on the use of very helpful tools - the so-called (outer) hodograph and the inner hodograph of two polygons. The hodograph can be used to handle the non-overlapping condition of two packed objects. The containment of a polygon in an other polygon can be characterized by using the inner hodograph.
    Postscript
    Back
    Computation of optimal phi-simple guillotine cutting patterns
    Authors: Guntram Scheithauer
    J. Inf. Process. Cybern. 29, No.2, 115-128 (1993).
    Postscript
    Back
    1992

    Algorithms for the container loading problem
    Author: Guntram Scheithauer
    Operations Research Proceedings 1991, Springer-Verlag Berlin Heidelberg (1992) 445--452
    In this paper we consider the three-dimensional problem of optimal packing of a container with rectangular pieces. We propose an approximation algorithm based on the "forward state strategy" of dynamic programming. A suitable description of packings is developed for the implementation of the approximation algorithm, and some computational experience is reported.
    Postscript
    Back
    About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem
    Authors: Guntram Scheithauer and Johannes Terno
    Operations Research Proceedings 1991, Springer-Verlag Berlin Heidelberg (1992) 439--444
    The purpose of this paper is to show that the gap is possibly smaller than 2. Some helpful results are summarized.
    PDF, Postscript
    Back
    1991

    A new branch and bound algorithm for product scheduling with ressource constraints
    Authors: Guntram Scheithauer and Johannes Terno
    Applicationes Mathematicae 21 (1991) 273-282
    Back
    A note on handling residual lengths
    Author: Guntram Scheithauer
    Optimization 22 (1991) 3, 361-366 PDF
    Back
    A three-dimensional bin packing algorithm
    Author: Guntram Scheithauer
    J. Inf. Process. Cybern. EIK 27 (1991) 5/6, 263-271 PDFt
    Back
    1990

    Optimaler Zuschnitt trapezf"ormiger Teile
    Author: Guntram Scheithauer
    Wiss. Z. TU Dresden 39 (1990) 1, 191-195 PDFt
    Back
    1989

    On the stochastic complexity of the asymmetric traveling salesman problem
    Authors: H.-U.Dost, G. Scheithauer and J.Terno
    EJOR 43 (1989) 313-316 Back
    1988

    Guillotine cutting of defective boards
    Authors: Guntram Scheithauer and Johannes Terno
    Optimization 19 (1988) 1, 111-121 PDF
    Back
    The partition of a square in rectangles with equal areas
    Authors: Guntram Scheithauer and Johannes Terno
    J. Inf. Process. Cybern. EIK 24 (1988) 189-200 PDF
    Back
    1987

    Zuschnittprobleme und ihre praktische L"osung
    Authors: Johannes Terno, Rudolf Lindemann und Guntram Scheithauer
    Fachbuchverlag Leipzig und Verlag Harry Deutsch Thun und Frankfurt/Main 1987
    Back
    Zur Ermittlung eines restringierten k"urzesten Weges
    Author: Guntram Scheithauer
    Seminarberichte der HU Berlin, Nr. 90 (1987) 107-114 PDF
    Back
    1986

    Complexity investigations on the ellipsoid algorithm
    Authors: Johannes Terno und Guntram Scheithauer
    Optimization 17 (1986) 2, 203-207
    Back
    Effektive L"osung von Guillotine-Zuschnittproblemen
    Authors: Guntram Scheithauer und Johannes Terno
    Wiss. Z. TU Dresden 35 (1986) 4, 35-40
    Back
    1985

    On recursive computation of minimum spanning trees for special partial graphs
    Author: Guntram Scheithauer
    Optimization 16 (1985) 1, 41-49
    Back
    On recursive computation of minimum spanning trees for special partial and subgraphs
    Author: Guntram Scheithauer
    Graphs, hypergraphs and applications, Proc. Conf. Graph Theory, Eyba/GDR 1984, Teubner-Texte Math. 73, 141-144 (1985).
    Back
    Rekursive Berechnung von Minimalger"usten f"ur spezielle Subgraphen
    Author: Guntram Scheithauer
    J. Inf. Process. Cybern. EIK 21 (1985) 12, 613-624 PDF
    Back
    1982

    A new extension principle algorithm for the traveling salesman problem
    Authors: Guntram Scheithauer and Johannes Terno
    Optimization 13 (1982) 2, 231-245
    Back

    This page is under construction and is subject to change. Last modified: January 19, 2015
    Impressum