@inproceedings{BorndoerferDaneckerWeiser2022, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.2}, pages = {1 -- 13}, year = {2022}, abstract = {We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen's algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage.}, language = {en} } @inproceedings{BorndoerferSchwartzSurau2022, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, booktitle = {Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7-10, 2022}, doi = {10.48786/inoc.2022.12}, pages = {63 -- 68}, year = {2022}, abstract = {Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts.}, language = {en} } @article{LindnerLiebchen2022, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable merging for the Periodic Event Scheduling Problem}, volume = {11}, journal = {EURO Journal on Transportation and Logistics}, doi = {10.1016/j.ejtl.2022.100081}, pages = {100081}, year = {2022}, abstract = {We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.}, language = {en} } @misc{MasingLindnerBorndoerfer2021, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84195}, year = {2021}, abstract = {Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC, we observe that the two cost functions are qualitatively comparable.}, language = {en} } @misc{Schwartz2020, author = {Schwartz, Stephan}, title = {An Overview of Graph Covering and Partitioning}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79431}, year = {2020}, abstract = {While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, our review extends to the corresponding partioning problems.}, 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} } @misc{MaristanydelasCasasBorndoerferKrausetal.2020, author = {Maristany de las Casas, Pedro and Bornd{\"o}rfer, Ralf and Kraus, Luitgard and Sede{\~n}o-Noda, Antonio}, title = {An FPTAS for Dynamic Multiobjective Shortest Path Problems}, doi = {https://doi.org/10.3390/a14020043}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80954}, year = {2020}, abstract = {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.}, language = {en} } @article{SchienleMaristanydelasCasasBlanco2019, author = {Schienle, Adam and Maristany de las Casas, Pedro and Blanco, Marco}, title = {A Priori Search Space Pruning in the Flight Planning Problem}, issn = {1438-0064}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2019.8}, year = {2019}, abstract = {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.}, language = {en} } @misc{Masing2021, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83238}, year = {2021}, abstract = {We formulate the line planning problem in public transport as a mixed integer linear program (MILP), which selects both passenger and vehicle routes, such that travel demands are met with respect to minimized travel times for both operators and users. We apply MILP to the Parametric City, a generic city model developed by Fielbaum et al. While the infrastructure graph and demand are entirely rotation symmetric, asymmetric optimal line plans can occur. Using group theory, we analyze the properties of symmetric solutions and introduce a symmetry gap to measure their deviation of the optimum. We also develop a 1+(1+\sqrt{2})/g-approximation algorithm, depending only on the cost related parameter g. Supported by computational experiments, we conclude that in practice symmetric line plans provide good solutions for the line planning problem in the Parametric City.}, language = {en} } @inproceedings{GamrathReutherSchlechteetal.2021, author = {Gamrath, Gerwin and Reuther, Markus and Schlechte, Thomas and Swarat, Elmar}, title = {An LP-based heuristic for Inspector Scheduling}, volume = {1}, booktitle = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I}, pages = {77 -- 86}, year = {2021}, abstract = {We present a heuristic based on linear programming (LP) for the integrated tour and crew roster planning of toll enforcement inspectors. Their task is to enforce the proper paying of a distance-based toll on German motorways. This leads to an integrated tour planning and duty rostering problem; it is called Toll Enforcement Problem (TEP). We tackle the TEP by a standard multi-commodity flow model with some extensions in order to incorporate the control tours. The heuristic consists of two variants. The first, called Price \& Branch, is a column generation approach to solve the model's LP relaxation by pricing tour and roster arc variables. Then, we compute an integer feasible solution by restricting to all variables that were priced. The second is a coarse-to-fine approach. Its basic idea is projecting variables to an aggregated variable space, which is much smaller. The aim is to spend as much algorithmic effort in this coarse model as possible. For both heuristic procedures we will show that feasible solutions of high quality can be computed even for large scale industrial instances.}, language = {en} } @article{PronzatoSagnol2021, author = {Pronzato, Luc and Sagnol, Guillaume}, title = {Removing inessential points in c- and A-optimal design}, volume = {213}, journal = {Journal of Statistical Planning and Inference}, doi = {10.1016/j.jspi.2020.11.011}, pages = {233 -- 252}, year = {2021}, abstract = {A design point is inessential when it does not contribute to an optimal design, and can therefore be safely discarded from the design space. We derive three inequalities for the detection of such inessential points in c-optimal design: the first two are direct consequences of the equivalence theorem for c-optimality; the third one is derived from a second-order cone programming formulation of c-optimal design. Elimination rules for A-optimal design are obtained as a byproduct. When implemented within an optimization algorithm, each inequality gives a screening test that may provide a substantial acceleration by reducing the size of the problem online. Several examples are presented with a multiplicative algorithm to illustrate the effectiveness of the approach.}, language = {en} } @article{Lindner2020, author = {Lindner, Niels}, title = {Hypersurfaces with defect}, volume = {555}, journal = {Journal of Algebra}, arxiv = {http://arxiv.org/abs/1610.04077}, doi = {10.1016/j.jalgebra.2020.02.022}, pages = {1 -- 35}, year = {2020}, abstract = {A projective hypersurface X⊆P^n has defect if h^i(X) ≠ h^i(P^n) for some i∈{n,…,2n-2} in a suitable cohomology theory. This occurs for example when X⊆P^4 is not Q-factorial. We show that hypersurfaces with defect tend to be very singular: In characteristic 0, we present a lower bound on the Tjurina number, where X is allowed to have arbitrary isolated singularities. For X with mild singularities, we prove a similar result in positive characteristic. As an application, we obtain an estimate on the asymptotic density of hypersurfaces without defect over a finite field.}, language = {en} } @inproceedings{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, doi = {10.4230/OASIcs.ATMOS.2024.13}, pages = {13:1 -- 13:19}, year = {2024}, abstract = {We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach.}, language = {en} } @inproceedings{BortolettoLindner2025, author = {Bortoletto, Enrico and Lindner, Niels}, title = {Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times}, booktitle = {Operations Research Proceedings 2023}, editor = {Voigt, Guido and Fliedner, Malte and Haase, Knut and Br{\"u}ggemann, Wolfgang and Hoberg, Kai and Meissner, J{\"o}rn}, doi = {10.1007/978-3-031-58405-3_51}, pages = {397 -- 402}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.}, language = {en} } @inproceedings{EbertMasingLindneretal.2025, author = {Ebert, Patricia and Masing, Berenike and Lindner, Niels and Gleixner, Ambros}, title = {Sorting Criteria for Line-based Periodic Timetabling Heuristics}, booktitle = {Operations Research Proceedings 2024. OR 2024}, pages = {348 -- 354}, year = {2025}, abstract = {It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2\%.}, language = {en} }