TY - GEN A1 - Burgschweiger, Jens A1 - Gnädig, Bernd A1 - Steinbach, Marc T1 - Nonlinear Programming Techniques for Operative Planning in Large Drinking Water Networks N2 - Mathematical decision support for operative planning in water supply systems is highly desirable but leads to very difficult optimization problems. We propose a nonlinear programming approach that yields practically satisfactory operating schedules in acceptable computing time even for large networks. Based on a carefully designed model supporting gradient-based optimization algorithms, this approach employs a special initialization strategy for convergence acceleration, special minimum up and down time constraints together with pump aggregation to handle switching decisions, and several network reduction techniques for further speed-up. Results for selected application scenarios at Berliner Wasserbetriebe demonstrate the success of the approach. T3 - ZIB-Report - 05-31 KW - Water supply KW - large-scale nonlinear programming KW - convergence enhancement KW - discrete decisions KW - network reduction Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8657 ER - TY - GEN A1 - Burgschweiger, Jens A1 - Gnädig, Bernd A1 - Steinbach, Marc T1 - Optimierte Tagesplanung im Berliner Trinkwassernetz N2 - Der Artikel beschreibt ein mathematisches Optimierungssystem zur Betriebsplanung in großen Wassernetzen, das bei den Berliner Wasserbetrieben eingesetzt wird. Für das Berliner Versorgungsnetz werden Optimierungsergebnisse vorgestellt. T3 - ZIB-Report - 05-32 KW - Trinkwasserversorgung KW - kostenminimale Betriebsplanung KW - nichtlineare Optimierung KW - diskrete Entscheidungen Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8668 ER - TY - GEN A1 - Burgschweiger, Jens A1 - Gnädig, Bernd A1 - Steinbach, Marc T1 - Optimization Models for Operative Planning in Drinking Water Networks N2 - The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe. T3 - ZIB-Report - 04-48 KW - Drinking water supply KW - distribution network KW - minimum cost operative planning KW - continuous time model KW - mixed integer model KW - nonlinear programming m Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8237 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Provably Good Solutions for Wavelength Assignment in Optical Networks N2 - In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically. T3 - ZIB-Report - 04-40 KW - wavelength assignment KW - integer programming KW - column generation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8155 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks N2 - In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value. T3 - ZIB-Report - 04-41 KW - optical networks KW - wavelength assignment KW - integer programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8160 ER - TY - GEN A1 - Koch, Thorsten A1 - Wessäly, Roland T1 - Hierarchical Infrastructure Planning in Networks N2 - In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur Förderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods. T3 - ZIB-Report - 04-42 KW - Facility Location KW - Telecommunication KW - Mixed Integer Programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8174 ER - TY - GEN A1 - Froyland, Gary A1 - Koch, Thorsten A1 - Megow, Nicole A1 - Duane, Emily A1 - Wren, Howard T1 - Optimizing the Landside Operation of a Container Terminal N2 - This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas. A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most~8\% above a lower bound on optimal RMG utilization. T3 - ZIB-Report - 06-06 KW - Integer Programming KW - Container Terminal KW - Intermediate Storage Area KW - Landside operation KW - Yard crane scheduling KW - Storage space allocation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9004 ER - TY - GEN A1 - Grötschel, Martin A1 - Hinrichs, Hinrich A1 - Schröer, Klaus A1 - Tuchscherer, Andreas T1 - Ein gemischt-ganzzahliges lineares Optimierungsmodell für ein Laserschweißproblem im Karosseriebau N2 - Wir beschäftigen uns mit dem Problem der Betriebsplanung von Laserschweißrobotern im Karosseriebau. Gegeben ist eine Menge von Schweißnähten, die innerhalb einer Fertigungszelle an einem Karosserieteil gefertigt werden müssen. Die Schweißnähte werden durch mehrere parallel betriebene Roboter bearbeitet. Die Aufgabe besteht darin, für jeden Roboter eine Reihenfolge und eine zeitliche Koordinierung seiner Bewegungen zu finden, so dass alle Schweißnähte innerhalb der Taktzeit der Fertigungszelle bearbeitet werden und so wenig Laserquellen wie möglich eingesetzt werden. Dabei müssen einige Nebenbedingungen berücksichtigt werden. Für dieses spezielle Schweißproblem haben wir eine Formulierung als gemischt-ganzzahliges lineares Programm entwickelt, welches sich für die untersuchten praktischen Fälle sehr schnell lösen lässt. T3 - ZIB-Report - 06-21 KW - Laserschweißen KW - Gemischt-ganzzahlige Optimierung Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9141 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 - Bley, Andreas A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Design of Broadband Virtual Private Networks: Model and Heuristics for the B–WiN N2 - We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data. T3 - ZIB-Report - SC-98-13 KW - Telecommunication Network Design KW - Survivable Networks KW - Network Capacity Planning KW - OSPF Routing KW - Shortest Path Routing KW - Heuristics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3565 ER -