@misc{BorndoerferNeumann2010, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Models for Line Planning with Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11742}, number = {10-11}, year = {2010}, abstract = {We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by "connection capacities" into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.}, language = {en} } @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{Gamrath2010, type = {Master Thesis}, author = {Gamrath, Gerald}, title = {Generic Branch-Cut-and-Price}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57543}, pages = {208}, year = {2010}, abstract = {In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG.}, language = {en} } @misc{BlancoBorndoerferHoangetal.2017, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Maristany de las Casas, Pedro and Schlechte, Thomas and Schlobach, Swen}, title = {Cost Projection Methods for the Shortest Path Problem with Crossing Costs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64817}, year = {2017}, abstract = {Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good {\`a} posteriori error bounds.}, language = {en} } @misc{BorndoerferReutherSchlechteetal.2015, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56070}, year = {2015}, abstract = {Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.}, language = {en} } @misc{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {A Case Study on Optimizing Toll Enforcements on Motorways}, issn = {1438-0064}, doi = {10.4230/OASIcs.SCOR.2012.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15498}, year = {2012}, abstract = {In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.}, language = {en} } @misc{MaherMiltenbergerPedrosoetal.2016, author = {Maher, Stephen J. and Miltenberger, Matthias and Pedroso, Jo{\~a}o Pedro and Rehfeldt, Daniel and Schwarz, Robert and Serrano, Felipe}, title = {PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite}, issn = {1438-0064}, doi = {10.1007/978-3-319-42432-3_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61348}, year = {2016}, abstract = {SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.}, language = {en} } @misc{Beckenbach2017, author = {Beckenbach, Isabel}, title = {A Hypergraph Network Simplex Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64539}, year = {2017}, abstract = {We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutell{\`a} who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal.2017, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {A Propagation Approach to Acyclic Rolling Stock Rotation Optimization}, booktitle = {Proceedings of the IAROR conference RailLille}, year = {2017}, abstract = {The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.}, language = {en} } @article{GleixnerMaherMuelleretal.2020, author = {Gleixner, Ambros and Maher, Stephen and M{\"u}ller, Benjamin and Pedroso, Jo{\~a}o Pedro}, title = {Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition}, volume = {284}, journal = {Annals of Operations Research}, number = {2}, publisher = {Springer US}, doi = {10.1007/s10479-018-3115-5}, pages = {527 -- 555}, year = {2020}, abstract = {Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.}, language = {en} }