TY - GEN A1 - Arnold, Thomas A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Henrion, René A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Tischendorf, Caren A1 - Römisch, Werner ED - Deuflhard, Peter ED - Grötschel, Martin ED - Hömberg, Dietmar ED - Horst, Ulrich ED - Kramer, Jürg ED - Mehrmann, Volker ED - Polthier, Konrad ED - Schmidt, Frank ED - Schütte, Christof ED - Skutella, Martin ED - Sprekels, Jürgen T1 - A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs T2 - MATHEON - Mathematics for Key Technologies N2 - 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 Y1 - 2014 U6 - https://doi.org/10.4171/137 VL - 1 SP - 135 EP - 146 PB - European Mathematical Society ER - TY - GEN A1 - Arnold, Thomas A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Henrion, René A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Tischendorf, Caren A1 - Römisch, Werner T1 - A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs N2 - 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 T3 - ZIB-Report - 14-14 KW - gas transport optimization KW - mixed integer nonlinear programming Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-49947 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - 制約整数計画ソルバ SCIP の並列化 T1 - Parallelizing the Constraint Integer Programming Solver SCIP N2 - 制約整数計画(CIP: Constraint Integer Programming)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming), 充足可能性問題(SAT: Satisfiability Problems)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP (Solving Constraint Integer Programs)は,CIPを解くソルバとして実装され,Zuse Institute Berlin (ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発されたSCIP に対する2種類の並列化拡張を紹介する. 一つは,複数計算ノード間で大規模に並列動作するParaSCIP である. もう一つは,複数コアと共有メモリを持つ1台の計算機上で(スレッド)並列で動作するFiberSCIP である. ParaSCIP は,HLRN IIスーパーコンピュータ上で, 一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある.また,統計数理研究所のFujitsu PRIMERGY RX200S5上でも,最大512コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5上 では,これまでに最適解が得られていなかったMIPLIB2010のインスタンスであるdg012142に最適解を与えた. N2 - The paradigm of Constraint Integer Programming (CIP) combines modeling and solving techniques from the fields of Constraint Programming (CP), Mixed Integer Programming (MIP) and Satisfiability Problems (SAT). The paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now continuously extended by a group of researchers centered at Zuse Institute Berlin (ZIB). This paper introduces two parallel extensions of SCIP. One is ParaSCIP, which is intended to run on a large scale distributed memory computing environment, and the other is FiberSCIP, intended to run on shared memory computing environments. ParaSCIP has successfully been run on the HLRN II supercomputer utilizing up to 7,168 cores to solve a single difficult MIP. It has also been tested on an ISM supercomputer (Fujitsu PRIMERGY RX200S5 using up to 512 cores). The previously unsolved instance dg012142 from MIPLIB2010 was solved by using the ISM supercomputer. T2 - Parallelizing the Constraint Integer Programming Solver SCIP T3 - ZIB-Report - 13-22 KW - Mixed Integer Programming KW - Constraint Integer Programming KW - Parallel Computing KW - Distributed Memory Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18130 SN - 1438-0064 ER - TY - JOUR A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - 制約整数計画ソルバ SCIP の並列化 JF - 統計数理 N2 - 制約整数計画(CIP: Constraint Integer Programs)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming),充足可能性問題(SAT: Satisfability Problem)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP(Solving Constraint Integer Programs)は,CIP を解くソルバとして実装され,Zuse Institute Berlin(ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発された SCIP に対する2 種類の並列化拡張を紹介する.一つは,複数計算ノード間で大規模に並列動作する ParaSCIPである.もう一つは,複数コアと共有メモリを持つ 1 台の計算機上で(スレッド)並列で動作する FiberSCIP である.ParaSCIP は,HLRN II スーパーコンピュータ上で,一つのインスタンスを解くために最大 7,168 コアを利用した動作実績がある.また,統計数理研究所の Fujitsu PRIMERGY RX200S5 上でも,最大 512 コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5 上では,これまでに最適解が得られていなかった MIPLIB2010のインスタンスである dg012142 に最適解を与えた. N2 - The paradigm of constraint integer programming (CIP) combines modeling and solving techniques from the fields of constraint programming (CP), mixed-integer programming (MIP) and satisfability problem (SAT). This paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now being continuously extended by a group of researchers centered at Zuse Institute Berlin (ZIB). This paper introduces two parallel extensions of SCIP. One is ParaSCIP, which is intended to run on a large scale distributed memory computing environment, and the other is FiberSCIP, intended to run on a shared memory computing environment. ParaSCIP has been run successfully on the HLRN II supercomputer utilizing up to 7,168 cores to solve a single difficult MIP. It has also been tested on an ISM supercomputer (Fujitsu PRIMERGY RX200S5 using up to 512 cores). The previously unsolved instance dg012142 from MIPLIB2010 was solved by using the ISM supercomputer. Y1 - 2013 UR - https://www.ism.ac.jp/editsec/toukei/pdf/61-1-047.pdf VL - 61 IS - 1 SP - 47 EP - 78 ER - TY - GEN A1 - Bley, Andreas A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Vigerske, Stefan T1 - Comparing MIQCP solvers to a specialised algorithm for mine production scheduling N2 - In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm. T3 - ZIB-Report - 09-32 Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11507 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Wolter, Kati T1 - Constraint Integer Programming: Techniques and Applications N2 - This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques. T3 - ZIB-Report - 08-43 KW - constraint programming KW - mixed integer programming KW - branch-and-cut KW - optimization software KW - chip verification Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10950 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Heinz, Stefan A1 - Koch, Thorsten T1 - Counting solutions of integer programs using unrestricted subtree detection N2 - In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection. T3 - ZIB-Report - 08-09 KW - Zählen KW - ganzzahlige Programme KW - IP KW - counting KW - integer programming KW - IP Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10632 SN - 1438-0064 ER - TY - GEN A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Voß, Stefan T1 - SteinLib: An Updated Library on Steiner Tree Problems in Graphs N2 - In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances. T3 - ZIB-Report - 00-37 KW - Steiner Trees KW - Mathematical Programming Testdata Library Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6056 ER - TY - GEN A1 - Koch, Thorsten A1 - Achterberg, Tobias A1 - Andersen, Erling A1 - Bastert, Oliver A1 - Berthold, Timo A1 - Bixby, Robert E. A1 - Danna, Emilie A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Lodi, Andrea A1 - Mittelmann, Hans A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Steffy, Daniel A1 - Wolter, Kati T1 - MIPLIB 2010 N2 - This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic. T3 - ZIB-Report - 10-31 KW - Mixed Integer Programming KW - Problem Instances KW - IP KW - MIP KW - MIPLIB Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12953 ER - TY - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten T1 - ParaSCIP - a parallel extension of SCIP N2 - Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer. T3 - ZIB-Report - 10-27 KW - massive parallization KW - mixed integer programming KW - ParaSCIP KW - branch-and-cut KW - branch-and-bound Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11921 UR - http://www.springerlink.com/content/t2160206253v7661/ ER - TY - GEN A1 - Wiebel, Alexander A1 - Koch, Stefan A1 - Scheuermann, Gerik ED - Peikert, Ronald ED - Hauser, Helwig ED - Carr, Hamish ED - Fuchs, Raphael T1 - Glyphs for Non-Linear Vector Field Singularities T2 - Topological Methods in Data Analysis and Visualization II Y1 - 2011 SP - 177 EP - 190 PB - Springer CY - Berlin ER - TY - CHAP A1 - Koch, Stefan A1 - Wiebel, Alexander A1 - Kasten, Jens A1 - Hlawitschka, Mario T1 - Visualizing Linear Neighborhoods in Non-Linear Vector Fields T2 - Proceedings of the IEEE Pacific Visualization Symposium Y1 - 2013 SP - 249 EP - 256 CY - Sydney, Australia ER - TY - JOUR A1 - Pfetsch, Marc A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Geißler, Nina A1 - Gollmer, Ralf A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Vigerske, Stefan A1 - Willert, Bernhard T1 - Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions JF - Optimization Methods and Software N2 - In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before. Y1 - 2014 U6 - https://doi.org/10.1080/10556788.2014.888426 PB - Taylor & Francis ER - TY - CHAP A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 T2 - Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming N2 - この論文ではソフトウェア・パッケージ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 の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる. N2 - This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how in concert these can be used to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview over available interfaces, and outline plans for future development. Y1 - 2012 SP - 165 EP - 192 ER - TY - CHAP A1 - Bley, Andreas A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Vigerske, Stefan T1 - Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling T2 - Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam N2 - In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-25707-0_3 SP - 25 EP - 39 ER - TY - CHAP A1 - Achterberg, Tobias A1 - Heinz, Stefan A1 - Koch, Thorsten ED - Perron, Laurent ED - Trick, Michael T1 - Counting Solutions of Integer Programs Using Unrestricted Subtree Detection T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008 Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2008/1092/ VL - 5015 SP - 278 EP - 282 PB - Springer ER - TY - JOUR A1 - Koch, Thorsten A1 - Achterberg, Tobias A1 - Andersen, Erling A1 - Bastert, Oliver A1 - Berthold, Timo A1 - Bixby, Robert E. A1 - Danna, Emilie A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Lodi, Andrea A1 - Mittelmann, Hans A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Steffy, Daniel A1 - Wolter, Kati T1 - MIPLIB 2010 JF - Mathematical Programming Computation Y1 - 2011 UR - http://mpc.zib.de/index.php/MPC/article/view/56 U6 - https://doi.org/10.1007/s12532-011-0025-9 VL - 3 IS - 2 SP - 103 EP - 163 ER - TY - CHAP A1 - Dorndorf, Ulrich A1 - Droste, Stefan A1 - Koch, Thorsten ED - Kallrath, Josef T1 - Using ZIMPL for Modeling Production Planning Problems T2 - Algebraic Modeling Systems Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-23592-4 SP - 145 EP - 158 PB - Springer ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten ED - Bischof, Christian ED - Hegering, Heinz-Gerd ED - Nagel, Wolfgang ED - Wittum, Gabriel T1 - ParaSCIP: a parallel extension of SCIP T2 - Competence in High Performance Computing 2010 Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-24025-6_12 SP - 135 EP - 148 PB - Springer ER - TY - CHAP A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Voß, Stefan ED - Du, D.-Z. ED - Cheng, X. T1 - SteinLib: An Updated Library on Steiner Tree Problems in Graphs T2 - Steiner Trees in Industry Y1 - 2001 U6 - https://doi.org/10.1007/978-1-4613-0255-1_9 SP - 285 EP - 325 PB - Kluwer ER -