TY - GEN A1 - Orlowski, Sebastian A1 - Pióro, Michal T1 - On the complexity of column generation in survivable network design with path-based survivability mechanisms N2 - This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures. T3 - ZIB-Report - 08-51 KW - Netzplanung KW - Dimensionierung KW - Spaltengenerierung KW - Mehrfachausfälle KW - survivable network design KW - routing KW - column generation KW - pricing KW - complexity Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11058 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - A Discrete-Continuous Algorithm for Free Flight Planning JF - Algorithms N2 - We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach. KW - shortest path KW - flight planning KW - free flight KW - discrete-continuous algorithm KW - optimal control KW - discrete optimization Y1 - 2020 U6 - https://doi.org/10.3390/a14010004 SN - 1438-0064 VL - 14 IS - 1 SP - 4 PB - MDPI ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - The Tropical and Zonotopal Geometry of Periodic Timetables N2 - The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis. T3 - ZIB-Report - 22-09 KW - periodic event scheduling KW - tropical geometry KW - zonotopal tilings Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86708 SN - 1438-0064 ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling N2 - Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [3]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [4]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances. T3 - ZIB-Report - 22-13 KW - Periodic Timetabling KW - Tropical Geometry KW - Neighbourhood Search KW - Mixed-Integer Programming Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-87385 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - A Discrete-Continuous Algorithm for Free Flight Planning N2 - We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach. T3 - ZIB-Report - 20-33 KW - shortest path KW - flight planning KW - free flight KW - discrete-continuous algorithm KW - optimal control KW - discrete optimization Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81343 SN - 1438-0064 ER - TY - GEN A1 - Maristany de las Casas, Pedro A1 - Borndörfer, Ralf A1 - Kraus, Luitgard A1 - Sedeño-Noda, Antonio T1 - An FPTAS for Dynamic Multiobjective Shortest Path Problems N2 - We propose in this paper the Dynamic Multiobjective Shortest Problem. It features multidimensional states that can depend on several variables and not only on time; this setting is motivated by flight planning and electric vehicle routing applications. We give an exact algorithm for the FIFO case and derive from it an FPTAS, which is computationally efficient. It also features the best known complexity in the static case. T3 - ZIB-Report - 20-31 KW - Multiobjective Shortest Paths KW - Time Dependent Shortest Paths KW - Multiobjective Approximation Algorithms KW - Flight Planning Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80954 ER - TY - JOUR A1 - Schienle, Adam A1 - Maristany de las Casas, Pedro A1 - Blanco, Marco T1 - A Priori Search Space Pruning in the Flight Planning Problem N2 - We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra's algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft's tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs. We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90\% in our setting. T3 - ZIB-Report - 20-32 Y1 - 2019 U6 - https://doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2019.8 SN - 1438-0064 ER -