@misc{Bortoletto2021, type = {Master Thesis}, author = {Bortoletto, Enrico}, title = {The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm}, year = {2021}, abstract = {We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.}, language = {en} } @masterthesis{Kraus2021, type = {Bachelor Thesis}, author = {Kraus, Luitgard}, title = {A Label Setting Multiobjective Shortest Path FPTAS}, year = {2021}, abstract = {Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.}, language = {en} } @misc{Rahmati2021, type = {Master Thesis}, author = {Rahmati, Niloofar}, title = {Resource Constrained APSP-Algorithm with Possible Reloading Stops}, year = {2021}, language = {en} } @misc{PrauseBorndoerfer2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91734}, year = {2023}, abstract = {We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.}, language = {en} } @article{EulerLindnerBorndoerfer2024, author = {Euler, Ricardo and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Price optimal routing in public transportation}, volume = {13}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier BV}, issn = {2192-4376}, doi = {10.1016/j.ejtl.2024.100128}, pages = {1 -- 15}, year = {2024}, 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{TurnerChmielaKochetal.2023, author = {Turner, Mark and Chmiela, Antonia and Koch, Thorsten and Winkler, Michael}, title = {PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93095}, year = {2023}, abstract = {A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.}, language = {en} } @misc{KempkeKoch2025, author = {Kempke, Nils-Christian and Koch, Thorsten}, title = {Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2503.10344}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99612}, year = {2025}, abstract = {We investigate the use of low-precision first-order methods (FOMs) within a fix-and-propagate (FP) framework for solving mixed-integer programming problems (MIPs). FOMs, using only matrix-vector products instead of matrix factorizations, are well suited for GPU acceleration and have recently gained more attention for their application to large-scale linear programming problems (LPs). We employ PDLP, a variant of the Primal-Dual Hybrid Gradient (PDHG) method specialized to LP problems, to solve the LP-relaxation of our MIPs to low accuracy. This solution is used to motivate fixings within our fix-and-propagate framework. We implemented four different FP variants using primal and dual LP solution information. We evaluate the performance of our heuristics on MIPLIB 2017, showcasing that the low-accuracy LP solution produced by the FOM does not lead to a loss in quality of the FP heuristic solutions when compared to a high-accuracy interior-point method LP solution. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million non-zeros and 8 million decision variables) unit-commitment energy-system optimization models created with the modeling framework REMix. For the largest problems, we can generate solutions with under 2\% primal-dual gap in less than 4 hours, whereas commercial solvers cannot generate feasible solutions within two days of runtime. This study represents the first successful application of FOMs in large-scale mixed-integer optimization, demonstrating their efficacy and establishing a foundation for future research in this domain.}, language = {en} } @inproceedings{Kunt2025, author = {Kunt, Tim}, title = {Solving the n-Queens Problem in Higher Dimensions}, booktitle = {Operations Research Proceedings 2024. OR 2024}, doi = {10.1007/978-3-031-92575-7_29}, pages = {205 -- 211}, year = {2025}, abstract = {How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15-70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP.}, language = {en} } @misc{KempkeMaherRehfeldtetal.2026, author = {Kempke, Nils-Christian and Maher, Stephen John and Rehfeldt, Daniel and Gleixner, Ambros and Koch, Thorsten and Uslu, Svenja}, title = {Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-103034}, year = {2026}, abstract = {We present a structure-aware parallel presolve framework specialized to arrowhead linear programs (AHLPs) and designed for high-performance computing (HPC) environments, integrated into the parallel interior point solver PIPS-IPM++. Large-scale LPs arising from automated model generation frequently contain redundancies and numerical pathologies that necessitate effective presolve, yet existing presolve techniques are primarily serial or structure-agnostic and can become time-consuming in parallel solution workflows. Within PIPS-IPM++, AHLPs are stored in distributed memory, and our presolve builds on this to apply a highly parallel, distributed presolve across compute nodes while keeping communication overhead low and preserving the underlying arrowhead structure. We demonstrate the scalability and effectiveness of our approach on a diverse set of AHLPs and compare it against state-of-the-art presolve implementations, including PaPILO and the presolve implemented within Gurobi. Even on a single machine, our presolve significantly outperforms PaPILO by a factor of 18 and Gurobi's presolve by a factor of 6 in terms of shifted geometric mean runtime, while reducing the problems by a similar amount to PaPILO. Using a distributed compute environment, we outperform Gurobi's presolve by a factor of 13.}, language = {en} }