TY - CHAP A1 - Gleixner, Ambros A1 - Kempke, Nils-Christian A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Uslu, Svenja T1 - First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method T2 - Operations Research Proceedings 2019 N2 - In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix. KW - block structure KW - energy system models KW - interior-point method KW - high performance computing KW - linear programming KW - parallelization KW - presolving KW - preprocessing Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-48439-2_13 SP - 105 EP - 111 PB - Springer International Publishing ET - 1 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - On the exact solution of prize-collecting Steiner tree problems T3 - ZIB-Report - 20-11 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78174 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Franz, Henriette A1 - Koch, Thorsten T1 - Optimal Connected Subgraphs: Formulations and Algorithms T3 - ZIB-Report - 20-23 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79094 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - On the exact solution of prize-collecting Steiner tree problems JF - INFORMS Journal on Computing Y1 - 2021 U6 - https://doi.org/10.1287/ijoc.2021.1087 ER - TY - CHAP A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Implications, conflicts, and reductions for Steiner trees T2 - Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021 Y1 - 2021 U6 - https://doi.org/10.1007/978-3-030-73879-2_33 SP - 473 EP - 487 ER - TY - CHAP A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - An exact high performance solver for Steiner tree problems in graphs and related problems T2 - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 Y1 - 2020 PB - Springer ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Implications, conflicts, and reductions for Steiner trees T3 - ZIB-Report - 20-28 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80039 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - Faster exact solution of sparse MaxCut and QUBO problems T3 - ZIB-Report - 22-02 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85715 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Franz, Henriette A1 - Koch, Thorsten T1 - Optimal Connected Subgraphs: Integer Programming Formulations and Polyhedra JF - Networks Y1 - 2022 U6 - https://doi.org/10.1002/net.22101 VL - 80 IS - 3 SP - 314 EP - 332 PB - Wiley ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Implications, Conflicts, and Reductions for Steiner Trees JF - Mathematical Programming Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01757-5 VL - 197 SP - 903 EP - 966 PB - Springer ER - TY - CHAP A1 - Rehfeldt, Daniel T1 - Faster Algorithms for Steiner Tree and related Problems: From Theory to Practice T2 - Operations Research Proceedings 2022 Y1 - 2022 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Fujisawa, Katsuki A1 - Koch, Thorsten A1 - Nakao, Masahiro A1 - Shinano, Yuji T1 - Computing single-source shortest paths on graphs with over 8 trillion edges N2 - This paper introduces an implementation for solving the single-source shortest path problem on distributed-memory machines. It is tailored to power-law graphs and scales to trillions of edges. The new implementation reached 2nd and 10th place in the latest Graph500 benchmark in June 2022 and handled the largest and second-largest graphs among all participants. T3 - ZIB-Report - 22-22 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88180 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Hobbie, Hannes A1 - Schönheit, David A1 - Koch, Thorsten A1 - Möst, Dominik A1 - Gleixner, Ambros T1 - A massively parallel interior-point solver for LPs with generalized arrowhead structure, and applications to energy system models JF - European Journal of Operational Research N2 - Linear energy system models are a crucial component of energy system design and operations, as well as energy policy consulting. If detailed enough, such models lead to large-scale linear programs, which can be intractable even for the best state-of-the-art solvers. This article introduces an interior-point solver that exploits common structures of energy system models to efficiently run in parallel on distributed-memory systems. The solver is designed for linear programs with doubly-bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. In order to handle the large number of linking constraints and variables commonly observed in energy system models, a distributed Schur complement preconditioner is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the solver PIPS-IPM. We evaluate the computational performance on energy system models with up to four billion nonzero entries in the constraint matrix—and up to one billion columns and one billion rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market-clearing. It has been widely applied in the literature on energy system analyses in recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models. Y1 - 2022 U6 - https://doi.org/10.1016/j.ejor.2021.06.063 VL - 296 IS - 1 SP - 60 EP - 71 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - Faster exact solution of sparse MaxCut and QUBO problems JF - Mathematical Programming Computation N2 - The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality. Y1 - 2023 U6 - https://doi.org/10.1007/s12532-023-00236-6 VL - 15 SP - 445 EP - 470 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Besançon, Mathieu A1 - Chen, Wei-Kun A1 - Chmiela, Antonia A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Gaul, Oliver A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc E. A1 - Rehfeldt, Daniel A1 - Schlein, Steffan A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Sofranac, Boro A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Wellner, Philipp A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 8.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack. T3 - ZIB-Report - 21-41 KW - Constraint integer programming KW - Linear programming KW - Mixed-integer linear programming KW - Mixed-integer nonlinear programming KW - Optimization solver KW - Branch-and-cut KW - Branch-and-price KW - Column generation KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85309 SN - 1438-0064 ER - TY - CHAP A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - On the state of QUBO solving T2 - Operations Research Proceedings 2023 N2 - It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization (QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate- scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights regarding current benchmark instances and modeling. Y1 - 2023 ER - TY - GEN A1 - Pedersen, Jaap A1 - Weinand, Jann Michael A1 - Syranidou, Chloi A1 - Rehfeldt, Daniel T1 - An efficient solver for multi-objective onshore wind farm siting and network integration N2 - Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. Although our case studies in selected regions of Germany show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, network integration must be simultaneously optimized in order to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision making and help optimize wind farms in large regions in the future. T3 - ZIB-Report - 23-10 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-90590 SN - 1438-0064 ER - TY - JOUR A1 - Pedersen, Jaap A1 - Weinand, Jann Michael A1 - Syranidou, Chloi A1 - Rehfeldt, Daniel T1 - An efficient solver for large-scale onshore wind farm siting including cable routing JF - European Journal of Operational Research N2 - Existing planning approaches for onshore wind farm siting and grid integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an exact approach for the integrated layout and cable routing problem of onshore wind farm planning using the Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. In selected regions of Germany, the trade-offs between minimizing costs and landscape impact of onshore wind farm siting are investigated. Although our case studies show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, grid integration must be simultaneously optimized to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision-making and help optimize wind farms in large regions in the future. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.04.026 VL - 317 IS - 2 SP - 616 EP - 630 ER -