Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-975
Main Title: Rapid Mathematical Programming
Author(s): Koch, Thorsten
Advisor(s): Grötschel, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Die Dissertation befaßt sich mit der Verwendung von Modellierungssprachen zur schnellen Umsetzung praktischer Probleme in mathematische Modelle. Anhand verschiedener Beispiele wird gezeigt, daß es heute möglich ist, die auf diese Weise erzeugten gemischt-ganzzahligen Probleme mit Standard-MIP-Lösern zu lösen und so Problemstellungen zu bearbeiten, die noch vor wenigen Jahren die Implementierung spezieller Branch-and-Cut Algorithmen benötigten. Im ersten Teil der Arbeit wird die Modellierungssprache Zimpl vorgestellt. Kapitel 2 enthält eine vollständige Beschreibung der Sprache. Im nachfolgenden Kapitel werden Details der Implementierung von Zimpl, sowohl aus theoretischer als auch aus praktischer Sicht beschrieben. Dabei wird besonders auf Methoden des Software-Engineering zur Fehlerentdeckung und Vermeidung eingegangen. Im zweiten Teil werden mehrere Projekte beschrieben, bei denen die angeführte Methodik eingesetzt wurde. Kapitel 4 beschreibt drei Standortplanungsprojekte aus dem Telekommunikationsbereich. Kapitel 5 geht auf Fragestellungen bei der UMTS-Planung ein. Es werden die Problemstellungen, Modellierungen und die Lösungen erörtert, dabei wird besonders auf die Abhängigkeit der Ergebnisse von den Eingangsdaten und auf unerwartete bzw. unerwünschte Lösungen eingegangen. Abschließend wird ein bekanntes schweres kombinatorisches Problem, das Steinerbaumpackungsproblem in Graphen, aufgegriffen. Es wird eine bekannte, aber bisher nicht genutze Modellierung verwendet, die das klassische Switchbox-Verdrahtungsproblem und das Via-Minimierungsproblem vereint. Es gelingt, alle in der Literatur bekannten, sowie einige neu erzeugte, größere Probleminstanzen zu lösen.
The thesis deals with the implementation and application of out-of-the-box tools in linear and mixed integer programming. It documents the lessons learned and conclusions drawn from five years of implementing, maintaining, extending, and using several computer codes to solve real-life industrial problems. By means of several examples it is demonstrated how to apply algebraic modeling languages to rapidly devise mathematical models of real-world problems. It is shown that today's MIP solvers are capable of solving the resulting mixed integer programs, leading to an approach that delivers results very quickly. Even though, problems are tackled that not long ago required the implementation of specialized branch-and-cut algorithms. In the first part of the thesis the modeling language Zimpl is introduced. Chapter 2 contains a complete description of the language. In the subsequent chapter details of the implementation are described. Both theoretical and practical considerations are discussed. Aspects of software engineering, error prevention, and detection are addressed. In the second part several real-world projects are examined that employed the methodology and the tools developed in the first part. Chapter 4 presents three projects from the telecommunication industry dealing with facility location problems. Chapter 5 characterizes questions that arise in UMTS planning. Problems, models, and solutions are discussed. Special emphasis is put on the dependency of the precision of the input data and the results. Possible reasons for unexpected and undesirable solutions are explained. Finally, the Steiner tree packing problem in graphs, a well-known hard combinatorial problem, is revisited. A formerly known, but not yet used model is applied to combine switchbox wire routing and via minimization. All instances known from the literature are solved by this approach, as are some newly generated bigger problem instances.
URI: urn:nbn:de:kobv:83-opus-8754
http://depositonce.tu-berlin.de/handle/11303/1272
http://dx.doi.org/10.14279/depositonce-975
Exam Date: 6-Dec-2004
Issue Date: 26-Jan-2005
Date Available: 26-Jan-2005
DDC Class: 510 Mathematik
Subject(s): Lineare gemischtganzzahlige Programmierung
MIP
Modellierungssprachen
Standortplanung
Steinerbaumpackungsprobleme in Graphen
UMTS-Planung
ZIMPL
Facility location planning
Linear mixed integer programming
MIP
Modeling languages
Steiner tree packing problems in graphs
UMTS-planning
ZIMP
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Publications

Files in This Item:
File Description SizeFormat 
Dokument_32.pdf7.62 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.