Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen
OPUS4-1199 misc Berthold, Timo; Gleixner, Ambros M.; Heinz, Stefan; Vigerske, Stefan On the computational impact of MIQCP solver components 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. urn:nbn:de:0297-zib-11998 Mathematical Optimization
OPUS4-1463 misc Berthold, Timo; Gleixner, Ambros M. Undercover: a primal MINLP heuristic exploring a largest sub-MIP We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. urn:nbn:de:0297-zib-14631 10.1007/s10107-013-0635-2 Mathematical Optimization
OPUS4-1137 misc Berthold, Timo; Heinz, Stefan; Vigerske, Stefan Extending a CIP framework to solve MIQCPs 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. urn:nbn:de:0297-zib-11371 Mathematical Optimization
OPUS4-1150 misc Bley, Andreas; Gleixner, Ambros M.; Koch, Thorsten; Vigerske, Stefan Comparing MIQCP solvers to a specialised algorithm for mine production scheduling 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. urn:nbn:de:0297-zib-11507 10.1007/978-3-642-25707-0 Mathematical Optimization
OPUS4-1559 misc Berthold, Timo; Gleixner, Ambros M.; Heinz, Stefan; Koch, Thorsten; Shinano, Yuji SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し，その３つの構成要素：モデリン グ言語Zimpl, 線形計画（LP: linear programming) ソルバSoPlex, そして，制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる．本論文では，この３つの 構成要素を利用して，どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する．SCIP は，現在，最も高速なMIP,MINLP ソルバの１つである．いくつかの例により， Zimpl, SCIP, SoPlex の利用方法を示すとともに，利用可能なインタフェースの概要を示す．最後に，将来の開 発計画の概要について述べる． urn:nbn:de:0297-zib-15598 Mathematical Optimization
OPUS4-1560 misc Gleixner, Ambros M.; Held, Harald; Huang, Wei; Vigerske, Stefan Towards globally optimal operation of water supply networks This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms. In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem. urn:nbn:de:0297-zib-15603 10.3934/naco.2012.2.695 Mathematical Optimization
OPUS4-1565 misc Berthold, Timo; Gamrath, Gerald; Gleixner, Ambros M.; Heinz, Stefan; Koch, Thorsten; Shinano, Yuji Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite 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 these can be used in concert 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 of available interfaces, and outline plans for future development. urn:nbn:de:0297-zib-15654 Mathematical Optimization
OPUS4-1763 misc Gleixner, Ambros M.; Weltge, Stefan Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times. urn:nbn:de:0297-zib-17631 10.1007/978-3-642-38171-3_26 Mathematical Optimization
OPUS4-1775 misc Berthold, Timo; Gleixner, Ambros M.; Heinz, Stefan; Vigerske, Stefan Analyzing the computational impact of MIQCP solver components 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. urn:nbn:de:0297-zib-17754 10.3934/naco.2012.2.739 Mathematical Optimization
OPUS4-5448 Dissertation Berthold, Timo Heuristic algorithms in global MINLP solvers In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are: - Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation, - a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP, - an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures, - RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution, - Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP, - Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs, - Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection. Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes. The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress. Dr. Hut Verlag 366 978-3-8439-1931-9 Mathematical Optimization
OPUS4-1764 misc Ballerstein, Martin; Michaels, Dennis; Vigerske, Stefan Linear Underestimators for bivariate functions with a fixed convexity behavior This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with fixed convexity behavior over a box. Computational results comparing our cut-generation algorithms with state-of-the-art global optimization software on a series of randomly generated test instances are reported and discussed. urn:nbn:de:0297-zib-17641 Mathematical Optimization
OPUS4-1803 misc Berthold, Timo; Gleixner, Ambros M. Undercover Branching In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved. urn:nbn:de:0297-zib-18030 10.1007/978-3-642-38527-8_20 Mathematical Optimization
OPUS4-6691 Dissertation Schweiger, Jonas Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model and uncertainty in the data pose principal difficulties. The first part of the thesis deals with non-convex quadratic programs. Branch&Bound methods for this problem class depend on tight relaxations. We contribute in several ways: First, we establish a new way to handle missing linearization variables in the well-known Reformulation-Linearization-Technique (RLT). This is implemented into the commercial software CPLEX. Second, we study the optimization of a quadratic objective over the standard simplex or a knapsack constraint. These basic structures appear as part of many complex models. Exploiting connections to the maximum clique problem and RLT, we derive new valid inequalities. Using exact and heuristic separation methods, we demonstrate the impact of the new inequalities on the relaxation and the global optimization of these problems. Third, we strengthen the state-of-the-art relaxation for the pooling problem, a well-known non-convex quadratic problem, which is, for example, relevant in the petrochemical industry. We propose a novel relaxation that captures the essential non-convex structure of the problem but is small enough for an in-depth study. We provide a complete inner description in terms of the extreme points as well as an outer description in terms of inequalities defining its convex hull (which is not a polyhedron). We show that the resulting valid convex inequalities significantly strengthen the standard relaxation of the pooling problem. The second part of this thesis focuses on a common challenge in real world applications, namely, the uncertainty entailed in the input data. We study the extension of a gas transport network, e.g., from our project partner Open Grid Europe GmbH. For a single scenario this maps to a challenging non-convex MINLP. As the future transport patterns are highly uncertain, we propose a robust model to best prepare the network operator for an array of scenarios. We develop a custom decomposition approach that makes use of the hierarchical structure of network extensions and the loose coupling between the scenarios. The algorithm used the single-scenario problem as black-box subproblem allowing the generalization of our approach to problems with the same structure. The scenario-expanded version of this problem is out of reach for today's general-purpose MINLP solvers. Yet our approach provides primal and dual bounds for instances with up to 256 scenarios and solves many of them to optimality. Extensive computational studies show the impact of our work. 411 Mathematical Optimization
OPUS4-4217 misc Berthold, Timo Primal MINLP Heuristics in a nutshell Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver. urn:nbn:de:0297-zib-42170 Mathematical Optimization
OPUS4-5937 misc Vigerske, Stefan; Gleixner, Ambros SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. urn:nbn:de:0297-zib-59377 10.1080/10556788.2017.1335312 Mathematical Optimization
OPUS4-6782 misc Luedtke, James; D'Ambrosio, Claudia; Linderoth, Jeff; Schweiger, Jonas Strong Convex Nonlinear Relaxations of the Pooling Problem We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound. urn:nbn:de:0297-zib-67824 Mathematical Optimization
OPUS4-6780 misc Luedtke, James; D'Ambrosio, Claudia; Linderoth, Jeff; Schweiger, Jonas Strong Convex Nonlinear Relaxations of the Pooling Problem: Extreme Points We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. In this technical report, we characterize the extreme points of the convex hull of our non-convex set, and show that they are not finite, i.e., the convex hull is not polyhedral. This analysis was used to derive valid nonlinear convex inequalities and show that, for a specific case, they characterize the convex hull of our set. The new valid inequalities and computational results are presented in ZIB Report 18-12. urn:nbn:de:0297-zib-67801 Mathematical Optimization
OPUS4-6217 misc Maher, Stephen J.; Fischer, Tobias; Gally, Tristan; Gamrath, Gerald; Gleixner, Ambros; Gottwald, Robert Lion; Hendel, Gregor; Koch, Thorsten; Lübbecke, Marco E.; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc E.; Puchert, Christian; Rehfeldt, Daniel; Schenker, Sebastian; Schwarz, Robert; Serrano, Felipe; Shinano, Yuji; Weninger, Dieter; Witt, Jonas T.; Witzig, Jakob The SCIP Optimization Suite 4.0 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. urn:nbn:de:0297-zib-62170 Mathematical Optimization
OPUS4-6947 misc Schweiger, Jonas Exploiting structure in non-convex quadratic optimization The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties. This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases. urn:nbn:de:0297-zib-69476 Mathematical Optimization