@misc{BorndoerferNeumann2010, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Linienoptimierung - reif f{\"u}r die Praxis?}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11832}, number = {10-20}, year = {2010}, abstract = {Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege ber{\"u}cksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 f{\"u}r Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es m{\"o}glich, durch Ver{\"a}nderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen {\"u}ber minimale Kosten und Fahrzeiten zu machen.}, language = {de} } @misc{Hoppmann2016, author = {Hoppmann, Heide}, title = {An Extended Formulation for the Line Planning Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-42902-1_2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57467}, year = {2016}, abstract = {In this paper we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.}, language = {en} } @misc{BertholdHeinzVigerske2009, author = {Berthold, Timo and Heinz, Stefan and Vigerske, Stefan}, title = {Extending a CIP framework to solve MIQCPs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11371}, number = {09-23}, year = {2009}, abstract = {This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.}, language = {en} } @misc{BorndoerferCardonha2009, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Set Partitioning Approach to Shunting}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11326}, number = {09-18}, year = {2009}, abstract = {The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.}, language = {en} } @misc{Bley2009, author = {Bley, Andreas}, title = {On the Hardness of Finding Small Shortest Path Routing Conflicts}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11276}, number = {09-15}, year = {2009}, abstract = {Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6.}, language = {en} } @misc{BorndoerferNeumannPfetsch2009, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Steiner Connectivity Problem}, issn = {1438-0064}, doi = {10.1007/s10107-012-0564-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11171}, number = {09-07}, year = {2009}, abstract = {The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.}, language = {en} } @misc{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11076}, number = {08-53}, year = {2008}, abstract = {Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.}, language = {en} } @misc{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {On the Line Planning Problem in Tree Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11069}, number = {08-52}, year = {2008}, abstract = {We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported.}, language = {en} } @misc{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10869}, number = {08-35}, year = {2008}, abstract = {Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.}, language = {en} } @misc{Stephan2008, author = {Stephan, R{\"u}diger}, title = {Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11026}, number = {08-48}, year = {2008}, abstract = {Given a combinatorial optimization problem and a subset \$N\$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of \$N\$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.}, language = {en} } @misc{Borndoerfer2003, author = {Bornd{\"o}rfer, Ralf}, title = {Combinatorial Packing Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7255}, number = {03-03}, year = {2003}, abstract = {This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.}, language = {en} } @misc{GamrathKochRehfeldtetal.2014, author = {Gamrath, Gerald and Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A massively parallel STP solver}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52293}, year = {2014}, abstract = {In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.}, language = {en} } @misc{HeismannBorndoerfer2014, author = {Heismann, Olga and Bornd{\"o}rfer, Ralf}, title = {A Generalization of Odd Set Inequalities for the Set Packing Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-07001-8_26}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51010}, year = {2014}, abstract = {The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Passenger Routing for Periodic Timetable Optimization}, issn = {1438-0064}, doi = {10.1007/s12469-016-0132-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56739}, year = {2015}, abstract = {The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, journal = {Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55305}, year = {2015}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2017, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Umsteigen ohne Warten}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62006}, year = {2017}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrpl{\"a}nen vor, bei dem die Umsteigezeiten unter Ber{\"u}cksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Bef{\"o}rderungsqualit{\"a}t.}, language = {de} } @misc{Karbstein2014, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, issn = {1438-0064}, doi = {10.1007/978-3-319-28697-6_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52986}, year = {2014}, abstract = {The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.}, language = {en} } @misc{BortolettoLindnerMasing2022, author = {Bortoletto, Enrico and Lindner, Niels and Masing, Berenike}, title = {The Tropical and Zonotopal Geometry of Periodic Timetables}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2204.13501}, doi = {https://doi.org/10.1007/s00454-024-00686-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86708}, year = {2022}, abstract = {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.}, language = {en} } @misc{BorndoerferDaneckerWeiser2020, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Free Flight Planning}, issn = {1438-0064}, doi = {10.3390/a14010004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81343}, year = {2020}, abstract = {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.}, language = {en} }