TY - CHAP A1 - Ascheuer, Norbert A1 - Escudero, Laureano A1 - Grötschel, Martin A1 - Stoer, Mechthild ED - Kannan, Ravi ED - Pulleyblank, William T1 - On Identifying in Polynomial Time Violated Subtour Elimination and Precedence Forcing Constraints for the Sequential Ordering Problem T2 - Integer Programming and Combinatorial Optimization, Proceeedings of a Conference held at the University of Waterloo, May 28-30, 1990 Y1 - 1990 SP - 19 EP - 28 PB - University of Waterloo Press ER - TY - GEN A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - A polyhedral study of the asymmetric travelling salesman problem with time windows N2 - The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances. T3 - ZIB-Report - SC-97-11 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2807 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Schorer, Herbert T1 - Simulation und Optimierung einer PC-Fertigung unter Echtzeitbedingungen N2 - Die Business Unit PC in Augsburg ist die zentrale Produktionsstätte der Siemens--Nixdorf Informationssysteme (SNI) AG für Personal Computer sowie für einige Periphärgeräte. Das Werk, entworfen nach modernen CIM/CAI--Konzepten (Computer Integrated Manufacturing/ Computer Aided Industry), wurde 1987 errichtet. Bald zeigte sich jedoch, daß es für ein zu geringes Produktionsvolumen ausgelegt war und einige Komponenten des Systems Engpässe im Produktionsbetrieb darstellen. Das Management suchte nach Möglichkeiten, den Produktionsfluß zu verbessern, ohne teure technische Änderungen am System vornehmen zu müssen. Eine Forschungsgruppe des Konrad--Zuse--Zentrums für Informationstechnik (die ehemals an der Universität Augsburg ansässig war) analysierte, unterstützt von einigen Studenten und Ingenieuren der SNI, den Produktionsfluß und lokalisierte Schwachstellen. Basierend auf diesen Erkenntnissen wurden mathematische Fragestellungen erarbeitet und auf mathematischen Optimierungsverfahren basierende Softwarepakete entwickelt, die jetzt teilweise bei SNI im Einsatz sind. Im folgenden werden einige dieser Fragestellungen, deren Modellierung und mathematische Behandlung beschrieben. Einige der Ansätze, die hier dargestellt werden sollen, sind teilweise schon in Grötschel [Grö92] angesprochen worden. T3 - ZIB-Report - SC-95-04 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1700 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Combinatorial Online Optimization N2 - In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material. T3 - ZIB-Report - SC-98-24 KW - Online Optimization KW - competitiveness KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3674 ER - TY - GEN A1 - Abdel-Hamid, Atef Abdel-Aziz A1 - Ascheuer, Norbert A1 - Grötschel, Martin T1 - Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs N2 - We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an \emph{online} Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40~\%. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems. T3 - ZIB-Report - SC-98-08 KW - Traveling Salesman Problem KW - Online-Algorithm KW - Automatic Storage System Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3519 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - Solving the Asymmetric Travelling Salesman Problem with Time Windows by Branch-and-Cut N2 - Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions. T3 - ZIB-Report - SC-99-31 KW - Asymmetric Travelling Salesman Problem KW - Time Windows KW - Integer Programs KW - Branch&Cut-Algorithm KW - Heuristics KW - Control of Stacker Cranes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4191 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Kamin, Nicola A1 - Rambau, Jörg T1 - Combinatorial Online Optimization in Practice N2 - This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems. T3 - ZIB-Report - SC-98-07 KW - Online optimization KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3508 ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Kamin, Nicola A1 - Rambau, Jörg T1 - Combinatorial online optimization in practice JF - OPTIMA Y1 - 1998 VL - 57 SP - 1 EP - 6 ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Abdel-Hamid, Atef Abdel-Aziz T1 - Order picking in an automatic warehouse JF - Mathematical Methods of Operations Research Y1 - 1999 VL - 49 IS - 3 SP - 501 EP - 515 ER - TY - JOUR A1 - Ascheuer, Norbert A1 - Fischetti, Matteo A1 - Grötschel, Martin T1 - Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut JF - Mathematical Programming, Series A Y1 - 2001 VL - 90 IS - 3 SP - 475 EP - 506 PB - Springer ER -