@misc{RehfeldtKoch2020, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, conflicts, and reductions for Steiner trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80039}, year = {2020}, language = {en} } @misc{RehfeldtFranzKoch2020, author = {Rehfeldt, Daniel and Franz, Henriette and Koch, Thorsten}, title = {Optimal Connected Subgraphs: Formulations and Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79094}, year = {2020}, language = {en} } @misc{RehfeldtKochShinano2022, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85715}, year = {2022}, language = {en} } @article{RehfeldtKoch2019, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem}, volume = {29}, journal = {SIAM Journal on Optimization}, number = {1}, publisher = {Society for Industrial and Applied Mathematics}, doi = {10.1137/17M1145963}, pages = {369 -- 398}, year = {2019}, abstract = {Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.}, language = {en} } @inproceedings{BreuerBussieckCaoetal.2018, author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Cebulla, Felix and Fiand, Frederik and Gils, Hans Christian and Gleixner, Ambros and Khabi, Dmitry and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_85}, pages = {641 -- 647}, year = {2018}, abstract = {Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.}, language = {en} } @inproceedings{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {SCIP-Jack—a solver for STP and variants with parallelization extensions: An update}, booktitle = {Operations Research Proceedings 2017}, pages = {191 -- 196}, year = {2018}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.}, language = {en} } @misc{GleixnerBastubbeEifleretal.2018, author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, year = {2018}, abstract = {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 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @inproceedings{BreuerBussieckCaoetal.2020, author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Fiand, Fred and Gils, Hans-Christian and Gleixner, Ambros and Khabi, Dmitry and Kempke, Nils and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {BEAM-ME: Accelerating Linear Energy Systems Models by a Massively Parallel Interior Point Method}, volume = {50}, booktitle = {NIC Symposium 2020}, pages = {345 -- 352}, year = {2020}, language = {en} } @misc{MaherFischerGallyetal.2017, author = {Maher, Stephen J. and Fischer, Tobias and Gally, Tristan and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Robert Lion and Hendel, Gregor and Koch, Thorsten and L{\"u}bbecke, Marco and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 4.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62170}, year = {2017}, abstract = {The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.}, language = {en} } @misc{GamrathFischerGallyetal.2016, author = {Gamrath, Gerald and Fischer, Tobias and Gally, Tristan and Gleixner, Ambros and Hendel, Gregor and Koch, Thorsten and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Vigerske, Stefan and Weninger, Dieter and Winkler, Michael and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 3.2}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57675}, year = {2016}, abstract = {The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.}, language = {en} }