TY - GEN A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Koch, Thorsten A1 - Koster, Arie M.C.A. A1 - Martin, Alexander A1 - Pfender, Tobias A1 - Wegel, Oliver A1 - Wessäly, Roland T1 - Modelling Feasible Network Configurations for UMTS N2 - A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations. T3 - ZIB-Report - 02-16 KW - UMTS KW - radio interface KW - network planning KW - configuration KW - perfect power control KW - mathematical model KW - mixed integer programming KW - MOMENTUM KW - IST-20 Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6837 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Optimization Methods for UMTS Radio Network Planning N2 - The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results. T3 - ZIB-Report - 03-41 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7637 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Szabó, Jácint T1 - Gas Network Topology Optimization for Upcoming Market Requirements N2 - Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed. T3 - ZIB-Report - 11-09 KW - Mathematical Optimization KW - Gas Distribution Networks KW - Topology Planning Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12348 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Fügenschuh, Armin A1 - Klug, Torsten A1 - Schang, Thilo A1 - Schlechte, Thomas A1 - Schülldorf, Hanno T1 - The Freight Train Routing Problem N2 - We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of complex real-world structures are into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We give a mixed-integer nonlinear programming~(MINLP) formulation for FTRP, which is a multi-commodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities are due to an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP) by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances. T3 - ZIB-Report - 13-36 KW - Mixed-Integer Nonlinear Programming KW - multi-commodity flows KW - freight train routing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18991 ER - TY - GEN A1 - Brose, Achim A1 - Fügenschuh, Armin A1 - Gausemeier, Pia A1 - Vierhaus, Ingmar A1 - Seliger, Günther T1 - A System Dynamic Enhancement for the Scenario Technique N2 - The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method. T3 - ZIB-Report - 13-24 KW - Scenario Technique; System Dynamics Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18150 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/4026 SN - 1438-0064 ER - TY - GEN A1 - Vierhaus, Ingmar A1 - Fügenschuh, Armin A1 - Gottwald, Robert Lion A1 - Grösser, Stefan N. T1 - Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models N2 - We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems. T3 - ZIB-Report - 14-08 KW - System Dynamics KW - Optimal Control KW - Nonlinear Optimization KW - Spline Interpolation Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-48159 SN - 1438-0064 ER - TY - GEN A1 - Humpola, Jesco A1 - Fügenschuh, Armin A1 - Lehmann, Thomas T1 - A Primal Heuristic for MINLP based on Dual Information N2 - We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP. T3 - ZIB-Report - 13-49 KW - Mixed-Integer Nonlinear Programming KW - Relaxations KW - Heuristics KW - Duality KW - Nonlinear Network Design Applications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43110 SN - 1438-0064 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Grösser, Stefan N. A1 - Vierhaus, Ingmar T1 - A Global Approach to the Control of an Industry Structure System Dynamics Model N2 - We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps. T3 - ZIB-Report - 13-67 KW - System Dynamics; Mixed-Integer Nonlinear Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42932 SN - 1438-0064 ER - TY - GEN A1 - Dittel, Agnes A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Polyhedral Aspects of Self-Avoiding Walks N2 - In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach. T3 - ZIB-Report - 11-11 KW - Polyhedral Combinatorics KW - Integer Programming KW - Self-Avoiding Path KW - Protein Folding Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12576 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Junosza-Szaniawski, Konstanty A1 - Klug, Torsten A1 - Kwasiborski, Slawomir A1 - Schlechte, Thomas T1 - Fastest, average and quantile schedule N2 - We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question. T3 - ZIB-Report - 14-49 KW - eulerian multigraphs KW - scheduling Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53592 SN - 1438-0064 ER -