TY - GEN A1 - Pedersen, Jaap A1 - Lindner, Niels A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Comparing Branching Rules for the Quota Steiner Tree Problem with Interference N2 - 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. T3 - ZIB-Report - 25-16 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101250 SN - 1438-0064 ER - TY - GEN A1 - Mehl, Lukas A1 - Lindner, Niels A1 - Bartoszuk, Karolina A1 - Zittel, Janina T1 - Prototypical warm-starts for demand-robust LP-based energy system optimization N2 - 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. T3 - ZIB-Report - 25-15 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101242 SN - 1438-0064 ER - TY - CHAP A1 - Gotzes, Uwe A1 - Buchholz, Annika A1 - Kallrath, Josef A1 - Lindner, Niels A1 - Koch, Thorsten T1 - Flexible Pooling Pattern Design with Integer Programming T2 - Theory, Algorithms and Experiments in Applied Optimization. In Honor of the 70th Birthday of Panos Pardalos N2 - 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. Y1 - 2025 VL - 226 PB - Springer ER - TY - GEN A1 - Pedersen, Jaap A1 - Lindner, Niels A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Integrated Wind Farm Design: Optimizing Turbine Placement and Cable Routing with Wake Effects N2 - 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. T3 - ZIB-Report - 25-01 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99218 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Bartoszuk, Karolina A1 - Debgupta, Srinwanti A1 - Gering, Marie-Claire A1 - Muschner, Christoph A1 - Zittel, Janina T1 - Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area T2 - Operations Research Proceedings 2024. OR 2024 N2 - 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. Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-92575-7_35 SP - 248 EP - 253 ER - TY - JOUR A1 - Riedmüller, Stephanie A1 - Lindner, Niels T1 - Column Generation for Periodic Timetabling N2 - 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. Y1 - 2025 ER - TY - CHAP A1 - Löbel, Fabian A1 - Lindner, Niels ED - Sauer, Jonas ED - Schmidt, Marie T1 - A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing T2 - 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025) N2 - 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. KW - Periodic Timetabling KW - Passenger Routing KW - Polyhedral Complexes Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-247580 SN - 978-3-95977-404-8 SN - 2190-6807 VL - 137 SP - 2:1 EP - 2:19 PB - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik CY - Dagstuhl, Germany ER - TY - JOUR A1 - van Lieshout, Rolf A1 - Lindner, Niels T1 - A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem N2 - 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. Y1 - 2025 ER - TY - JOUR A1 - Masing, Berenike A1 - Lindner, Niels A1 - Bortoletto, Enrico T1 - Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm JF - EURO Journal on Transportation and Logistics N2 - Given a public transportation network, which and how many passenger routes can potentially be shortest paths, when all possible timetables are taken into account? This question leads to shortest path problems on graphs with interval costs on their arcs and is closely linked to multi-objective optimization. We introduce a Dijkstra algorithm based on polynomials over the tropical semiring that computes complete or minimal sets of efficient paths. We demonstrate that this approach is computationally feasible by employing it on the public transport network of the city of Wuppertal and instances of the benchmarking set TimPassLib, and we evaluate the resulting sets of passenger routes. Y1 - 2025 U6 - https://doi.org/10.1016/j.ejtl.2025.100163 VL - 14 ER - TY - JOUR A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - The Tropical and Zonotopal Geometry of Periodic Timetables JF - Discrete & Computational Geometry N2 - The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetables in public transport. A solution to a PESP instance consists of three parts: a periodic timetable, a periodic tension, and integer offset values. While the space of periodic tensions has received much attention in the past, we explore geometric properties of the other two components. The general aim of this paper is to establish novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables as a disjoint union of polytropes. These are 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 neighbourhood relations of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope, and then study its zonotopal tilings. These are related to the hyperrectangle of fractional periodic tensions, as well as the polytropes of the periodic timetable space, and we detail their interplay. To conclude, we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis. Y1 - 2025 U6 - https://doi.org/10.1007/s00454-024-00686-2 VL - 73 SP - 719 EP - 763 ER - TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggemann, Wolfgang ED - Hoberg, Kai ED - Meissner, Jörn T1 - Incremental Heuristics for Periodic Timetabling T2 - Operations Research Proceedings 2023 N2 - We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances. Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-58405-3_59 SP - 461 EP - 467 PB - Springer Nature Switzerland CY - Cham ER - TY - JOUR A1 - Lindner, Niels A1 - Masing, Berenike T1 - On the split closure of the periodic timetabling polytope JF - Mathematical Programming N2 - The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P = NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances. KW - Periodic event scheduling problem KW - Periodic timetabling KW - Split closure KW - Mixed-integer programming Y1 - 2025 U6 - https://doi.org/10.1007/s10107-025-02220-5 SN - 0025-5610 PB - Springer Science and Business Media LLC ER - TY - GEN A1 - Lindner, Niels A1 - Mehl, Lukas A1 - Bartoszuk, Karolina A1 - Berendes, Sarah A1 - Zittel, Janina T1 - Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization N2 - Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability. T3 - ZIB-Report - 25-19 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-102404 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels T1 - A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites N2 - Rescheduling a railway system comprises many aspects, such as line planning, timetabling, track allocation, and vehicle scheduling. For periodic timetables, these features can be integrated into a single mixed-integer program extending the Periodic Event Scheduling Problem (PESP) with a routing component. We develop a multi-commodity-flow-based heuristic that allows to compute better solutions faster than a black-box MIP approach on real construction site scenarios on the S-Bahn Berlin network. T3 - ZIB-Report - 25-02 KW - Railway Timetabling KW - Periodic Timetabling KW - Rescheduling KW - Railway Track Allocation Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99449 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - A two-stage model for periodic timetabling with fixed line activities N2 - The timetable is a central pillar of any public transportation system. Constructing and optimizing periodic timetables in terms of passenger comfort and operational efficiency leads to NP-hard optimization problems that are also computationally challenging in applications. The Periodic Event Scheduling Problem (PESP) as standard mathematical tool benefits from its succinct formulation and rich combinatorial structure, but suffers from poor linear programming relaxations and weak dual bounds. These difficulties persist in a reduced version, where driving and dwelling activities of the lines are assumed to be fixed. In this case, fixing the initial departure time of each line fully determines the timetable, and for each pair of lines, the resulting (weighted) transfer durations can be expressed in terms of a piecewise linear non-convex function in terms of the difference of the initial times. When the number of activities between two lines is bounded, this function can be computed in polynomial time. By inserting precomputed piecewise linear functions into a mixed-integer program with the initial departure times as variables, we introduce an equivalent formulation for reduced PESP instances. The model bears analogies with quadratic semi-assignment approaches and offers alternative ways to compute primal and dual bounds. We evaluate the computational behavior of our approach on realistic benchmarking instances. T3 - ZIB-Report - 25-14 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101234 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Mehl, Lukas A1 - Bartoszuk, Karolina A1 - Berendes, Sarah A1 - Zittel, Janina T1 - Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization T2 - Proceedings of the 38th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems N2 - Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability. Y1 - 2025 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggemann, Wolfgang ED - Hoberg, Kai ED - Meissner, Jörn T1 - Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times T2 - Operations Research Proceedings 2023 N2 - 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. Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-58405-3_51 SP - 397 EP - 402 ER - TY - CHAP A1 - Ebert, Patricia A1 - Masing, Berenike A1 - Lindner, Niels A1 - Gleixner, Ambros T1 - Sorting Criteria for Line-based Periodic Timetabling Heuristics T2 - Operations Research Proceedings 2024. OR 2024 N2 - 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%. Y1 - 2025 SP - 348 EP - 354 ER -