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 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components N2 - We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. T3 - ZIB-Report - 13-08 KW - mixed-integer quadratically constrained programming KW - mixed-integer programming KW - branch-and-cut KW - nonconvex KW - global optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17754 SN - 1438-0064 ER - TY - JOUR A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components JF - Numerical Algebra, Control and Optimization N2 - We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. Y1 - 2012 U6 - https://doi.org/10.3934/naco.2012.2.739 VL - 2 IS - 4 SP - 739 EP - 748 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - On the computational impact of MIQCP solver components N2 - We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. T3 - ZIB-Report - 11-01 KW - MIQCP KW - MIP KW - mixed-integer quadratically constrained programming KW - computational KW - nonconvex Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11998 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vigerske, Stefan T1 - Large Neighborhood Search beyond MIP N2 - Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics. T3 - ZIB-Report - 11-21 KW - Large Neighborhood Search KW - Primal Heuristic KW - MIP KW - MIQCP KW - Pseudo-Boolean Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12989 ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vigerske, Stefan T1 - Large Neighborhood Search beyond MIP T2 - Proceedings of the 9th Metaheuristics International Conference (MIC 2011) N2 - Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics. Y1 - 2011 SN - 978-88-900984-3-7 SP - 51 EP - 60 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Extending a CIP framework to solve MIQCPs N2 - This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach. T3 - ZIB-Report - 09-23 KW - mixed integer quadratically constrained programming KW - constraint integer programming KW - convex relaxation KW - nonconvex Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11371 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan ED - Lee, Jon ED - Leyffer, Sven T1 - Extending a CIP framework to solve MIQCPs T2 - Mixed Integer Nonlinear Programming N2 - This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach. Y1 - 2012 SN - 978-1-4614-1927-3 VL - 154 SP - 427 EP - 444 PB - Springer 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 -