@article{CookKochSteffyetal., author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {A hybrid branch-and-bound approach for exact rational mixed-integer programming}, series = {Mathematical Programming Computation}, volume = {5}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-013-0055-6}, pages = {305 -- 344}, abstract = {We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.}, language = {en} } @misc{ArnoldBertholdHeinzetal., author = {Arnold, Thomas and Berthold, Timo and Heinz, Stefan and Vigerske, Stefan and Henrion, Ren{\´e} and Gr{\"o}tschel, Martin and Koch, Thorsten and Tischendorf, Caren and R{\"o}misch, Werner}, title = {A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs}, series = {MATHEON - Mathematics for Key Technologies}, volume = {1}, journal = {MATHEON - Mathematics for Key Technologies}, editor = {Deuflhard, Peter and Gr{\"o}tschel, Martin and H{\"o}mberg, Dietmar and Horst, Ulrich and Kramer, J{\"u}rg and Mehrmann, Volker and Polthier, Konrad and Schmidt, Frank and Sch{\"u}tte, Christof and Skutella, Martin and Sprekels, J{\"u}rgen}, publisher = {European Mathematical Society}, doi = {10.4171/137}, pages = {135 -- 146}, abstract = {Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de}, language = {en} } @article{BertholdHendelKoch2017, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {From feasibility to improvement to proof: three phases of solving mixed-integer programs}, series = {Optimization Methods and Software}, volume = {33}, journal = {Optimization Methods and Software}, number = {3}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1392519}, pages = {499 -- 517}, year = {2017}, abstract = {Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points.}, language = {en} } @article{Koch, author = {Koch, Thorsten}, title = {The ZIMPL modeling language}, series = {Optima}, volume = {103}, journal = {Optima}, pages = {8 -- 9}, language = {en} } @misc{RehfeldtKoch, 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}, issn = {1438-0064}, doi = {10.1137/17M1145963}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64699}, 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} } @misc{RehfeldtKoch, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65439}, abstract = {This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.}, language = {en} } @misc{GamrathGleixnerKochetal., author = {Gamrath, Gerald and Gleixner, Ambros and Koch, Thorsten and Miltenberger, Matthias and Kniasew, Dimitri and Schl{\"o}gel, Dominik and Martin, Alexander and Weninger, Dieter}, title = {Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming}, issn = {1438-0064}, doi = {10.4208/jcm.1905-m2019-0055}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61107}, abstract = {SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice.}, language = {en} } @misc{RehfeldtKoch, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP}, issn = {1438-0064}, doi = {10.4208/jcm.1709-m2017-0002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59777}, abstract = {Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.}, language = {en} } @misc{GreuelKochPauleetal., author = {Greuel, Martin and Koch, Thorsten and Paule, Peter and Sommese, Andrew}, title = {Mathematical Software - ICMS 2016, 5th Int. Conf. Berlin, Germany, July 11-14, 2016, Proceedings}, series = {Lecture Notes in Computer Science (LNCS)}, volume = {9725}, journal = {Lecture Notes in Computer Science (LNCS)}, publisher = {Springer}, isbn = {978-3-319-42431-6}, doi = {10.1007/978-3-319-42432-3}, pages = {XXIV, 532}, language = {en} } @article{RehfeldtKoch, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP}, series = {Journal of Computational Mathematics}, volume = {36}, journal = {Journal of Computational Mathematics}, number = {3}, doi = {10.4208/jcm.1709-m2017-0002}, pages = {459 -- 468}, abstract = {Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.}, language = {en} } @inproceedings{BertholdGleixnerHeinzetal.2012, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, series = {Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming}, booktitle = {Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming}, pages = {165 -- 192}, year = {2012}, abstract = {この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.}, language = {ja} } @inproceedings{FuegenschuhHillerHumpolaetal., author = {F{\"u}genschuh, Armin and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Schwarz, Robert and Schweiger, Jonas and Szabo, Jacint}, title = {Gas Network Topology Optimization for Upcoming Market Requirements}, series = {International Conference on the European Energy Market (EEM)}, booktitle = {International Conference on the European Energy Market (EEM)}, doi = {10.1109/EEM.2011.5953035}, pages = {346 -- 351}, abstract = {Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed.}, language = {en} } @misc{RehfeldtKoch, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {SCIP-Jack—a solver for STP and variants with parallelization extensions: An update}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66416}, 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{RalphsShinanoBertholdetal., author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62239}, abstract = {In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.}, language = {en} } @inproceedings{AchterbergHeinzKoch2008, author = {Achterberg, Tobias and Heinz, Stefan and Koch, Thorsten}, title = {Counting Solutions of Integer Programs Using Unrestricted Subtree Detection}, series = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008}, volume = {5015}, booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008}, editor = {Perron, Laurent and Trick, Michael}, publisher = {Springer}, pages = {278 -- 282}, year = {2008}, language = {en} } @article{KochAchterbergAndersenetal.2011, author = {Koch, Thorsten and Achterberg, Tobias and Andersen, Erling and Bastert, Oliver and Berthold, Timo and Bixby, Robert E. and Danna, Emilie and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Lodi, Andrea and Mittelmann, Hans and Ralphs, Ted and Salvagnin, Domenico and Steffy, Daniel and Wolter, Kati}, title = {MIPLIB 2010}, series = {Mathematical Programming Computation}, volume = {3}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-011-0025-9}, pages = {103 -- 163}, year = {2011}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, series = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, booktitle = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, doi = {10.1109/IPDPS.2016.56}, abstract = {This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.}, language = {en} } @article{GamrathKochMartinetal., author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in presolving for mixed integer programming}, series = {Mathematical Programming Computation}, volume = {7}, journal = {Mathematical Programming Computation}, number = {4}, doi = {10.1007/s12532-015-0083-5}, pages = {367 -- 398}, abstract = {This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 \% on affected instances while not degrading the performance on the remaining problems.}, language = {en} } @inproceedings{ShinanoRehfeldtKoch, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019}, volume = {11494}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019}, publisher = {Springer}, doi = {10.1007/978-3-030-19212-9_35}, pages = {529 -- 539}, abstract = {SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively parallel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best-known solutions to instances from the benchmark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been considerably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.}, language = {en} } @misc{RehfeldtHobbieSchoenheitetal., author = {Rehfeldt, Daniel and Hobbie, Hannes and Sch{\"o}nheit, David and Gleixner, Ambros and Koch, Thorsten and M{\"o}st, Dominik}, title = {A massively parallel interior-point solver for linear energy system models with block structure}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74321}, abstract = {Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear 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. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement 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 existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million 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 during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.}, language = {en} }