TY - THES A1 - Eifler, Leon T1 - Algorithms and Certificates for Exact Mixed Integer Programming N2 - Mixed Integer Programming (MIP) is a powerful tool for solving optimization problems with discrete decisions. Although the problem class of mixed integer programs is NP-hard, MIP solvers have made significant progress in solving large-scale instances through decades of dedicated research and complex algorithmic improvements. In practice, virtually all algorithms to solve MIP problems are based on floating-point arithmetic due to its rapid computation times and robust numerical capabilities. Using error tolerances, MIP solvers avoid numerical issues and maintain a solution quality that is sufficient for most practical applications. There are, however, applications where exact solutions are required, such as when MIPs are employed as a tool in computer-assisted proofs. In such cases, exact, certified MIP solvers are a necessity. This thesis delves into the study and development of exact, certified mixed integer programming methods. The primary contribution of this thesis is an algorithmic framework for exact rational mixed integer programming. This framework incorporates safe dual bounding techniques, exact rational presolving, an exact repair step for heuristic solutions, and a novel exact Gomory mixed integer cut generator. We validate the effectiveness of our framework through experiments on a diverse set of benchmark instances. We take great care to measure the similarities and differences with corresponding techniques in the floating-point setting. Furthermore, we incorporate certification techniques into the framework to provide rigorous guarantees on the correctness of the computed solutions. We also provide a comprehensive algorithmic and computational study of the solver-independent verification of these certficates. We also present a framework for applying exact MIP as a tool for computer-assisted mathematics, using Chvátals conjecture as an illustrative example. Another significant contribution of this thesis is a new algorithm for solving linear programs exactly. This algorithm combines two state-of-the-art techniques for exact linear programming: precision boosting and LP iterative refinement. Combining these techniques can significantly improve the performance of exact linear programming solvers, and we prove that the algorithm is theoretically guaranteed to terminate with an exact solution. Y1 - 2024 U6 - https://doi.org/https://doi.org/10.14279/depositonce-23941 ER - TY - CHAP A1 - Lindner, Niels A1 - Masing, Berenike A1 - Liebchen, Christian T1 - Integrierte Baufahrplanoptimierung auf dem Netz der S-Bahn Berlin T2 - HEUREKA'24 - Optimierung in Verkehr und Transport N2 - Zur Instandhaltung von Eisenbahnnetzen sind regelmäßig Baumaßnahmen erforderlich. Diese erfordern stets Anpassungen der Fahrpläne. Um den Fahrgästen trotz der Baumaßnahme weiterhin einen möglichst großen Teil des Regelangebotes bieten zu können, bewegen sich die resultierenden Baufahrpläne insbesondere in Schnellbahnnetzen mit ihren dichten Zugfolgen häufig nahe der Kapazitätsgrenze der Infrastruktur. Etablierte Verfahren zur Taktfahrplanoptimierung können diesen Anforderungen nicht genügen, da in der Praxis Anpassungen von Laufwegen der Linien, sowie der Gleisbelegungen häufig Teil der realisierten Lösungen sind. Für diese Aufgabe haben die Autoren zuletzt ein Optimierungsmodell vorgestellt, welches diese Möglichkeiten ausschöpft. In dem vorliegenden Beitrag wird erstmalig dessen Anwendung auf ein unmittelbar der Praxis der Baufahrplanung entnommenes Beispiel aus dem Netz der Berliner S-Bahn im Detail beschrieben. Y1 - 2024 VL - 002/140 ER - TY - CHAP A1 - Lindner, Niels A1 - Masing, Berenike T1 - SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice T2 - hEART 2024: 12th Symposium of the European Association for Research in Transportation N2 - Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turn-arounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network. KW - Periodic Timetabling KW - Railway Timetabling KW - Railway Track Allocation KW - Boolean Satisfiability Problem KW - Rescheduling KW - Line Planning Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98066 UR - https://transp-or.epfl.ch/heart/2024/abstracts/hEART_2024_paper_3685.pdf ER - TY - CHAP A1 - Bortoletto, Enrico A1 - van Lieshout, Rolf Nelson A1 - Masing, Berenike A1 - Lindner, Niels T1 - Periodic Event Scheduling with Flexible Infrastructure Assignment T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances. Y1 - 2024 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2024.4 VL - 123 SP - 4:1 EP - 4:18 ER - TY - CHAP A1 - Euler, Ricardo A1 - Borndörfer, Ralf A1 - Puchert, Christian A1 - Takkula, Tuomo T1 - ULD Build-Up Scheduling with Logic-Based Benders Decomposition T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - We study a complex planning and scheduling problem arising from the build-up process of air cargo pallets and containers, collectively referred to as unit load devices (ULD), in which ULDs must be assigned to workstations for loading. Since air freight usually becomes available gradually along the planning horizon, ULD build-ups must be scheduled neither too early to avoid underutilizing ULD capacity, nor too late to avoid resource conflicts with other flights. Whenever possible, ULDs should be built up in batches, thereby giving ground handlers more freedom to rearrange cargo and utilize the ULD's capacity efficiently. The resulting scheduling problem has an intricate cost function and produces large time-expanded models, especially for longer planning horizons. We propose a logic-based Benders decomposition approach that assigns batches to time intervals and workstations in the master problem, while the actual schedule is decided in a subproblem. By choosing appropriate intervals, the subproblem becomes a feasibility problem that decomposes over the workstations. Additionally, the similarity of many batches is exploited by a strengthening procedure for no-good cuts. We benchmark our approach against a time-expanded MIP formulation from the literature on a publicly available data set. It solves 15% more instances to optimality and decreases run times by more than 50% in the geometric mean. This improvement is especially pronounced for longer planning horizons of up to one week, where the Benders approach solves over 50% instances more than the baseline Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60597-0_17 VL - 14742 SP - 259 EP - 276 ER - TY - JOUR A1 - Euler, Ricardo A1 - Maristany de las Casas, Pedro T1 - Labeling methods for partially ordered paths JF - European Journal of Operational Research N2 - The landscape of applications and subroutines relying on shortest path computations continues to grow steadily. This growth is driven by the undeniable success of shortest path algorithms in theory and practice. It also introduces new challenges as the models and assessing the optimality of paths become more complicated. Hence, multiple recent publications in the field adapt existing labeling methods in an ad hoc fashion to their specific problem variant without considering the underlying general structure: they always deal with multi-criteria scenarios, and those criteria define different partial orders on the paths. In this paper, we introduce the partial order shortest path problem (POSP), a generalization of the multi-objective shortest path problem (MOSP) and in turn also of the classical shortest path problem. POSP captures the particular structure of many shortest path applications as special cases. In this generality, we study optimality conditions or the lack of them, depending on the objective functions’ properties. Our final contribution is a big lookup table summarizing our findings and providing the reader with an easy way to choose among the most recent multi-criteria shortest path algorithms depending on their problems’ weight structure. Examples range from time-dependent shortest path and bottleneck path problems to the electric vehicle shortest path problem with recharging and complex financial weight functions studied in the public transportation community. Our results hold for general digraphs and, therefore, surpass previous generalizations that were limited to acyclic graphs. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.05.002 VL - 318 IS - 1 SP - 19 EP - 30 PB - Elsevier BV ET - 1 ER - TY - GEN A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen T1 - Electric Bus Scheduling with Non-Linear Charging, Power Grid Bottlenecks, and Dynamic Recharge Rates N2 - Public transport operators are gradually electrifying their bus fleets, predominantly with battery-powered drive trains. These buses commonly have to be scheduled to recharge in-service, which gives rise to a number of challenges. A major problem is that the relationship between charging time and replenished driving range is non-linear, which is often approximately modeled. We examine the associated approximation error and show how it can result in a gross over- or underestimation of the fleet size. Moreover, we demonstrate that commonly used piecewise linear underestimations of the charge curve do not result in an underestimation of the predicted charge states in electric vehicle scheduling and routing models. Furthermore, since power grid upgrades are currently not keeping up with an ever growing electricity demand, operators are introducing active charge management tools to dynamically adjust the charging speed depending on the amount of available energy. It is therefore imperative to extend electric bus scheduling models to account for these developments. We propose a novel mixed-integer programming formulation for the electric bus scheduling problem featuring an improved approximation of the non-linear battery charging behavior as well as dynamic recharge speeds to accommodate grid load limits. The idea is to linearly interpolate what we call the charge increment function, which is closely related to the derivative of the commonly used charge curve. This provides very good error control and integrates easily into integer programming models. We demonstrate the practical usefulness of our model on a diverse library of real-life instances. Y1 - 2024 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Löbel, Fabian A1 - Weider, Steffen T1 - Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - Attractive and cost-efficient public transport requires solving computationally difficult optimization problems from network design to crew rostering. While great progress has been made in many areas, new requirements to handle increasingly complex constraints are constantly coming up. One such challenge is a new type of resource constraints that are used to deal with the state-of-charge of battery-electric vehicles, which have limited driving ranges and need to be recharged in-service. Resource constrained vehicle scheduling problems can classically be modelled in terms of either a resource constrained (multi-commodity) flow problem or in terms of a path-based set partition problem. We demonstrate how a novel integrated version of both formulations can be leveraged to solve resource constrained vehicle scheduling with replenishment in general and the electric bus scheduling problem in particular by Lagrangian relaxation and the proximal bundle method. Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-211992 VL - 123 SP - 11:1 EP - 11:16 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik CY - Dagstuhl, Germany ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance N2 - The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances. Y1 - 2024 ER - TY - CHAP A1 - Prause, Felix T1 - A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance T2 - Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024 N2 - We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subsequently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables. Y1 - 2024 U6 - https://doi.org/10.48786/inoc.2024.11 SP - 58 EP - 63 ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating rolling stock rotations with integrated predictive maintenance JF - Journal of Rail Transport Planning & Management N2 - We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions. Y1 - 2024 U6 - https://doi.org/10.1016/j.jrtpm.2024.100434 VL - 30 SP - 100434 ER - TY - JOUR A1 - Euler, Ricardo A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - Price optimal routing in public transportation JF - EURO Journal on Transportation and Logistics KW - Management Science and Operations Research KW - Transportation KW - Modeling and Simulation Y1 - 2024 U6 - https://doi.org/10.1016/j.ejtl.2024.100128 SN - 2192-4376 VL - 13 SP - 1 EP - 15 PB - Elsevier BV ER -