TY - CHAP A1 - Chmiela, Antonia A1 - Muñoz, Gonzalo A1 - Serrano, Felipe T1 - On the implementation and strengthening of intersection cuts for QCQPs T2 - Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021 N2 - The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments. Y1 - 2021 U6 - https://doi.org/10.1007/978-3-030-73879-2_10 VL - 22 SP - 134 EP - 147 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 - TY - CHAP A1 - Ghannam, Mohammed A1 - Gleixner, Ambros T1 - Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows T2 - Operations Research Proceedings 2023. OR 2023 Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-58405-3_35 ER - TY - CHAP A1 - Pedersen, Jaap A1 - Lindner, Niels A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Comparing Branching Rules for the Quota Steiner Tree Problem with Interference T2 - Operations Research Proceedings 2025 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 whose cumulative profit meets or exceeds a given quota. The 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. Unlike classical STP variants, large QSTPI instances 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. Y1 - 2026 ER - TY - CHAP A1 - Franke, Paula A1 - Hamacher, Kay A1 - Manns, Paul T1 - Minimizing and Maximizing the Shannon Entropy for Fixed Marginals T2 - Operations Research Proceedings 2025 N2 - The mutual information (MI) between two random variables is an important correlation measure in data analysis. The Shannon entropy of a joint probability distri- bution is the variable part under fixed marginals. We aim to minimize and maximize it to obtain the largest and smallest MI possible in this case, leading to a scaled MI ratio for better comparability. We present algorithmic approaches and optimal solutions for a set of problem instances based on data from molecular evolution. We show that this allows us to construct a sensible, systematic correction to raw MI values. Y1 - 2026 ER - TY - CHAP A1 - Mexi, Gioni A1 - Besançon, Mathieu A1 - Bolusani, Suresh A1 - Chmiela, Antonia A1 - Hoen, Alexander A1 - Gleixner, Ambros T1 - Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization T2 - Proceedings of Conference of the Society for Operations Research in Germany Y1 - 2023 ER - TY - CHAP A1 - Iravani, Sahar A1 - Conrad, Tim ED - Holzinger, A. ED - Kieseberg, P. ED - Tjoa, A. ED - Weippl, E. T1 - Deep Learning for Proteomics Data for Feature Selection and Classification T2 - Machine Learning and Knowledge Extraction. CD-MAKE 2019 Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-29726-8_19 VL - 11713 PB - Springer, Cham ER - TY - CHAP A1 - Koch, Thorsten A1 - Kempke, Nils-Christian A1 - Lindner, Niels A1 - Mehl, Lukas A1 - Wetzel, Manuel A1 - Zittel, Janina T1 - High-Performance Robust Energy System Planning with Storage: A Single-LP Approach T2 - Proceedings of URBSENSE 2026 - 1st International Workshop on URBan SENSEmaking and Intelligence for Safer Cities Y1 - 2026 ER - TY - CHAP A1 - Sengupta, Agniva A1 - Kuş, Dilara A1 - Li, Jianning A1 - Zachow, Stefan T1 - Globally Optimal Pose from Orthographic Silhouettes N2 - We solve the problem of determining the pose of known shapes in R^3 from their unoccluded silhouettes. The pose is determined up to global optimality using a simple yet under-explored property of the area-of-silhouette: its continuity w.r.t trajectories in the rotation space. The proposed method utilises pre-computed silhouette-signatures, modelled as a response surface of the area-of-silhouettes. Querying this silhouette-signature response surface for pose estimation leads to a strong branching of the rotation search space, making resolution-guided candidate search feasible. Additionally, we utilise the aspect ratio of 2D ellipses fitted to projected silhouettes as an auxiliary global shape signature to accelerate the pose search. This combined strategy forms the first method to efficiently estimate globally optimal pose from just the silhouettes, without being guided by correspondences, for any shape, irrespective of its convexity and genus. We validate our method on synthetic and real examples, demonstrating significantly improved accuracy against comparable approaches. Y1 - 2026 ER - TY - CHAP A1 - Riccardi, Gabor A1 - Lindner, Niels T1 - On The Minimum-Weight Forward (Weakly) Fundamental Cycle Basis Problem in Directed Graphs T2 - International Network Optimization Conference 2026 (INOC 2026) N2 - The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs have to follow the given direction. We study the existence, structure, and computational complexity of minimum-weight forward cycle bases in directed graphs. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases, showing that this holds if and only if every block is either strongly connected or a single arc. We further provide an easily verifiable characterization of when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique and computable in polynomial time, and nonexistence can likewise be certified efficiently. Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is NP-hard via a polynomial-time reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights. Y1 - 2026 ER - TY - CHAP A1 - Riedmüller, Stephanie A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Warm-starting Strategies in Scalarization Methods for Multi-Objective Optimization T2 - Operations Research Proceedings 2025 N2 - We explore how warm-starting strategies can be integrated into scalarization-based approaches for multi-objective optimization in (mixed) integer linear programming. Scalarization methods remain widely used classical techniques to compute Pareto-optimal solutions in applied settings. They are favored due to their algorithmic simplicity and broad applicability across continuous and integer programs with an arbitrary number of objectives. While warm-starting has been applied in this context before, a systematic methodology and analysis remain lacking. We address this gap by providing a theoretical characterization of warm-starting within scalarization methods, focusing on the sequencing of subproblems. However, optimizing the order of subproblems to maximize warm-start efficiency may conflict with alternative criteria, such as early identification of infeasible regions. We quantify these trade-offs through an extensive computational study. Y1 - 2026 ER -