@misc{PedersenLindnerRehfeldtetal.2025, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Comparing Branching Rules for the Quota Steiner Tree Problem with Interference}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101250}, year = {2025}, abstract = {Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this paper, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The Quota Steiner Tree Problem (QSTP) generalizes the classical Steiner Tree Problem (STP) in graphs by seeking a minimum-cost tree that connects a subset of profit-associated vertices to meet a given quota. The extended version, QSTPI, introduces interference among vertices: Selecting certain vertices simultaneously reduces their individual contributions to the overall profit. This problem arises, for example, in positioning and connecting wind turbines, where turbines possibly shadow other turbines, reducing their energy yield. While exact solvers for standard STP-related problems often rely heavily on reduction techniques and cutting-plane methods - rarely generating large branch-and-bound trees - experiments reveal that large instances of QSTPI require significantly more branching to compute provably optimal solutions. In contrast to branching on variables, we utilize the combinatorial structure of the QSTPI by branching on the graph's vertices. We adapt classical and problem-specific branching rules and present a comprehensive computational study comparing the effectiveness of these branching strategies.}, language = {en} } @misc{MehlLindnerBartoszuketal.2025, author = {Mehl, Lukas and Lindner, Niels and Bartoszuk, Karolina and Zittel, Janina}, title = {Prototypical warm-starts for demand-robust LP-based energy system optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101242}, year = {2025}, abstract = {The expressiveness of energy system optimization models (ESOMs) depends on a multitude of exogenous parameters. For example, sound estimates of the future energy demand are essential to enable qualified decisions on long-term investments. However, the enormous demand fluctuations even on a fine-grained scale diminish the computational performance of large-scale ESOMs. We therefore propose a clustering-and-decomposition method for linear programming based ESOMs that first identifies and solves prototypical demand scenarios with the dual simplex algorithm, and then composes dual optimal prototype bases to a warm-start basis for the full model. We evaluate the feasibility and computational efficiency our approach on a real-world case study, using a sector-coupled ESOM with hourly resolution for the Berlin-Brandenburg area in Germany, based on the oemof framework.}, language = {en} } @incollection{GotzesBuchholzKallrathetal.2025, author = {Gotzes, Uwe and Buchholz, Annika and Kallrath, Josef and Lindner, Niels and Koch, Thorsten}, title = {Flexible Pooling Pattern Design with Integer Programming}, volume = {226}, booktitle = {Theory, Algorithms and Experiments in Applied Optimization. In Honor of the 70th Birthday of Panos Pardalos}, publisher = {Springer}, year = {2025}, abstract = {Sample pooling has the potential to significantly enhance large-scale screening procedures, especially in scenarios like the COVID-19 pandemic, where rapid and widespread PCR testing has been crucial. Efficient strategies are essential to increase the testing capacity, i.e., the number of tests that can be processed within a given timeframe. Non-adaptive pooling strategies can further streamline the testing process by reducing the required testing rounds. In contrast to adaptive strategies, where subsequent tests depend on prior results, non-adaptive pooling processes all samples in a single round, eliminating the need for sequential retesting and reducing delays. This paper presents a highly flexible method based on integer programming to design optimized pooling patterns suitable for various applications, including medical diagnostics and quality control in industrial production. Using coronavirus testing as a case study, we formulate and solve optimization and satisfiability models that compute efficient pool designs. Our optimized pooling does not only increase testing capacity, but also accelerates the testing process and reduces overall costs. The proposed method is adaptable and can be seamlessly integrated into automated testing systems.}, language = {en} } @misc{LindnerBartoszukDebguptaetal.2024, author = {Lindner, Niels and Bartoszuk, Karolina and Debgupta, Srinwanti and Gering, Marie-Claire and Muschner, Christoph and Zittel, Janina}, title = {Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-97835}, year = {2024}, abstract = {Energy system optimization models are key to investigate energy transition paths towards a decarbonized future. Since this approach comes with intrinsic uncertainties, it is insufficient to compute a single optimal solution assuming perfect foresight to provide a profound basis for decision makers. The paradigm of modeling to generate alternatives enables to explore the near-optimal solution space to a certain extent. However, large-scale energy models require a non-negligible computation time to be solved. We propose to use warm start methods to accelerate the process of finding close-to-optimal alternatives. In an extensive case study for the energy transition of the Berlin-Brandenburg area, we make use of the sector-coupled linear programming oemof-B3 model to analyze a scenario for the year 2050 with a resolution of one hour and 100\% reduction of greenhouse gas emissions. We demonstrate that we can actually achieve a significant computational speedup.}, language = {en} } @inproceedings{LindnerLiebchen2019, author = {Lindner, Niels and Liebchen, Christian}, title = {New Perspectives on PESP: T-Partitions and Separators}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2019.2}, pages = {2:1 -- 2:18}, year = {2019}, abstract = {In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.}, language = {en} } @article{BorndoerferHoppmannKarbsteinetal.2020, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of cycle inequalities in periodic timetabling}, journal = {Discrete Optimization}, number = {35}, doi = {10.1016/j.disopt.2019.100552}, pages = {100552}, year = {2020}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @article{BorndoerferLindnerRoth2020, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, journal = {Journal of Rail Transport Planning \& Management}, number = {15}, issn = {2210-9706}, doi = {10.1016/j.jrtpm.2019.100175}, pages = {100175}, year = {2020}, abstract = {We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.}, language = {en} } @misc{LindnerLiebchen2019, author = {Lindner, Niels and Liebchen, Christian}, title = {New Perspectives on PESP: T-Partitions and Separators}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2019.2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73853}, year = {2019}, abstract = {In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.}, language = {en} } @misc{LoebelLindnerBorndoerfer2019, author = {L{\"o}bel, Fabian and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing}, issn = {1438-0064}, doi = {https://doi.org/https://doi.org/10.1007/978-3-030-48439-2_92}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73868}, year = {2019}, abstract = {The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.}, language = {en} } @misc{BorndoerferLindnerRoth2019, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71907}, year = {2019}, abstract = {We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.}, language = {en} } @misc{BorndoerferKarbsteinLiebchenetal.2018, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2018.16}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69688}, year = {2018}, abstract = {We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.}, language = {en} } @misc{SchieweGoerigkLindner2023, author = {Schiewe, Philine and Goerigk, Marc and Lindner, Niels}, title = {Introducing TimPassLib - A library for integrated periodic timetabling and passenger routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89741}, year = {2023}, abstract = {Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing.}, language = {en} } @misc{PedersenLindnerRehfeldtetal.2025, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Integrated Wind Farm Design: Optimizing Turbine Placement and Cable Routing with Wake Effects}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99218}, year = {2025}, abstract = {An accelerated deployment of renewable energy sources is crucial for a successful transformation of the current energy system, with wind energy playing a key role in this transition. This study addresses the integrated wind farm layout and cable routing problem, a challenging nonlinear optimization problem. We model this problem as an extended version of the Quota Steiner Tree Problem (QSTP), optimizing turbine placement and network connectivity simultaneously to meet specified expansion targets. Our proposed approach accounts for the wake effect - a region of reduced wind speed induced by each installed turbine - and enforces minimum spacing between turbines. We introduce an exact solution framework in terms of the novel Quota Steiner Tree Problem with interference (QSTPI). By leveraging an interference-based splitting strategy, we develop an advanced solver capable of tackling large-scale problem instances. The presented approach outperforms generic state-of-the-art mixed integer programming solvers on our dataset by up to two orders of magnitude. Moreover, we demonstrate that our integrated method significantly reduces the costs in contrast to a sequential approach. Thus, we provide a planning tool that enhances existing planning methodologies for supporting a faster and cost-efficient expansion of wind energy.}, language = {en} } @inproceedings{LindnerBartoszukDebguptaetal.2025, author = {Lindner, Niels and Bartoszuk, Karolina and Debgupta, Srinwanti and Gering, Marie-Claire and Muschner, Christoph and Zittel, Janina}, title = {Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area}, booktitle = {Operations Research Proceedings 2024. OR 2024}, doi = {10.1007/978-3-031-92575-7_35}, pages = {248 -- 253}, year = {2025}, abstract = {Energy system optimization models are key to investigate energy transition paths towards a decarbonized future. Since this approach comes with intrinsic uncertainties, it is insufficient to compute a single optimal solution assuming perfect foresight to provide a profound basis for decision makers. The paradigm of modeling to generate alternatives enables to explore the near-optimal solution space to a certain extent. However, large-scale energy models require a non-negligible computation time to be solved. We propose to use warm start methods to accelerate the process of finding close-to-optimal alternatives. In an extensive case study for the energy transition of the Berlin-Brandenburg area, we make use of the sector-coupled linear programming oemof-B3 model to analyze a scenario for the year 2050 with a resolution of one hour and 100\% reduction of greenhouse gas emissions. We demonstrate that we can actually achieve a significant computational speedup.}, language = {en} } @misc{LindnerReisch2020, author = {Lindner, Niels and Reisch, Julian}, title = {Parameterized Complexity of Periodic Timetabling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78314}, year = {2020}, abstract = {Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib.}, language = {en} } @inproceedings{BorndoerferKarbsteinLiebchenetal.2018, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}, volume = {65}, booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, doi = {10.4230/OASIcs.ATMOS.2018.16}, pages = {16:1 -- 16:15}, year = {2018}, abstract = {We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal.2018, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of Cycle Inequalities in Periodic Timetabling}, issn = {1438-0064}, doi = {https://doi.org/10.1016/j.disopt.2019.100552}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69746}, year = {2018}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @article{RiedmuellerLindner2025, author = {Riedm{\"u}ller, Stephanie and Lindner, Niels}, title = {Column Generation for Periodic Timetabling}, arxiv = {http://arxiv.org/abs/2510.12466}, year = {2025}, abstract = {Periodic timetabling for public transportation networks is typically modelled as a Periodic Event Scheduling Problem (PESP). Solving instances of the benchmark library PESPlib to optimality continues to pose a challenge. As a further approach towards this goal, we remodel the problem by a time discretization of the underlying graph and consider arc-based as well as path-based integer programming formulations. For the path-based case, we use cycles on the graph expansion of the operational lines as variables and, therefore, include more of the problem inherent structure into the model. A consequence is the validity of several known inequalities and a lower bound on the LP-relaxation, that is the best known to date. As an extension we integrate passenger routing into the new model. The proposed models have an advantage in the linear programming relaxation, on the one hand, but have an increased problem size, on the other hand. We define the corresponding pricing problems for the use of column generation to handle the size. Both models are practically tested on different problem instances.}, language = {en} } @inproceedings{LoebelLindner2025, author = {L{\"o}bel, Fabian and Lindner, Niels}, title = {A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}, volume = {137}, booktitle = {25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)}, editor = {Sauer, Jonas and Schmidt, Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-404-8}, issn = {2190-6807}, doi = {10.4230/OASIcs.ATMOS.2025.2}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-247580}, pages = {2:1 -- 2:19}, year = {2025}, abstract = {We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.}, language = {en} } @article{vanLieshoutLindner2025, author = {van Lieshout, Rolf and Lindner, Niels}, title = {A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem}, arxiv = {http://arxiv.org/abs/2507.17566}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is a fundamental model in periodic timetabling for public transport systems, assuming a common period across all events. However, real-world networks often feature heterogeneous service frequencies. This paper studies the Multiperiodic Event Scheduling Problem (MPESP), a generalization of PESP that allows each event to recur at its own individual period. While more expressive, MPESP presents new modeling challenges due to the loss of a global period. We present a cycle-based formulation for MPESP that extends the strongest known formulation for PESP and, in contrast to existing approaches, is valid for any MPESP instance. Crucially, the formulation requires a cycle basis derived from a spanning tree satisfying specific structural properties, which we formalize and algorithmically construct, extending the concept of sharp spanning trees to rooted instances. We further prove a multiperiodic analogue of the cycle periodicity property. Our new formulation solves nearly all tested instances, including several large-scale real-world public transport networks, to optimality or with small optimality gaps, dramatically outperforming existing arc-based models. The results demonstrate the practical potential of MPESP in capturing heterogeneous frequencies without resorting to artificial event duplication.}, language = {en} }