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 - 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 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover Branching N2 - 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. T3 - ZIB-Report - 13-14 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18030 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP N2 - 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. T3 - ZIB-Report - 12-07 KW - Primal Heuristic KW - Mixed-Integer Nonlinear Programming KW - Large Neighborhood Search KW - Mixed-Integer Quadratically Constrained Programming KW - Nonconvex Optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14631 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Weltge, Stefan T1 - Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming N2 - 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. T3 - ZIB-Report - 13-04 KW - MINLP KW - optimization-based bound tightening KW - optimality-based bound tightening KW - OBBT KW - propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17631 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 - GEN A1 - Berthold, Timo T1 - Primal MINLP Heuristics in a nutshell N2 - 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. T3 - ZIB-Report - 13-42 KW - Primal Heuristic KW - MINLP KW - Mixed Integer Nonlinear Programming KW - Feasibility Pump KW - Large Neighborhood Search Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42170 SN - 1438-0064 ER - TY - THES A1 - Schweiger, Jonas T1 - Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty N2 - 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. N2 - Der bemerkenswerte Erfolg der angewandten mathematischen Optimierung in den letzten Dekaden ist mehr auf Einsichten in mathematische Strukturen zurückzuführen, als auf eine Steigerung der Rechenleistung. In diesem Sinne adressieren wir Anwendungen, in denen Nichtkonvexität und Unsicherheit in den Daten die Hauptschwierigkeiten darstellen. Der erste Teil dieser Arbeit beschäftigt sich mit nichtkonvexen quadratischen Optimierungsproblemen. Relaxierungen sind integraler Bestandteil von \BranchAndBound{}-Lösungsmethoden für diese Problemkategorie. Wir leisten folgende Beiträge: Erstens beschreiben wir eine neue Art fehlende Linearisierungsvariablen, in der so genannten Reformulation-Linearization-Technique (RLT), zu behandeln. Diese wird inzwischen in der kommerziellen Software CPLEX verwendet. Zweitens beschäftigen wir uns mit der Optimierung einer quadratischen Zielfunktion über die Standardsimplex oder einen so genannten Knapsack-Constraint. Solche grundlegenden Strukturen sind Teil vieler komplexer Modelle. Wir benutzen bekannte Verbindungen zum maximalen Cliquenproblem sowie zu RLT, um neue gültige Ungleichungen herzuleiten, die die Relaxierung verstärken. Drittens beschäftigen wir uns mit dem Pooling Problem, das z.B. in der Erdölindustrie relevant ist. Wie leiten eine neue Relaxierung her, die die wesentliche nicht-konvexe Struktur des Problems erfasst, aber klein genug für eine grundlegende Untersuchung ist. Wir geben eine innere Beschreibung in Form der Extrempunkte, sowie eine äußere Beschreibung in Form von Ungleichungen, die die konvexe Hülle (welche im Allgemeinen kein Polyeder ist) beschreiben, an. Wir zeigen, dass neuen die Ungleichungen die Relaxierung des Pooling Problems erheblich verstärken. Der zweite Teil der Arbeit befasst sich mit einer weiteren Herausforderung in realen Anwendungen, nämlich Unsicherheit in den Eingabedaten. Konkret untersuchen wir die Optimierung des Ausbaus eines Gastransportnetzes, wie z.B. von unserem Projektpartner Open Grid Europe GmbH. Dieses Problem ist bereits bei gegebenen Eingabedaten ein schweres nicht-konvexes gemischt-ganzzahliges Optimierungsproblem. Da zukünftige Nutzungsmuster des Netzes mit großer Unsicherheit behaftet sind, beschreiben wir ein robustes Modell, um den Netzbetreiber gegen verschiedene Szenarien abzusichern. Wir entwickeln einen speziellen Dekompositionsalgorithmus unter Berücksichtigung der hierarchischen Struktur der Ausbauten und der schwachen Kopplung zwischen den Szenarien. Unser Ansatz liefert primale und duale Schranken für Instanzen mit bis zu 256 Szenarien und löst viele beweisbar optimal. Umfangreiche Rechnungen bestätigen die Effizient der vorgestellten Methoden. KW - Nonconvexity KW - Uncertainty KW - Quadratic Programming KW - Relaxations KW - Cutting Planes KW - Standard Quadratic Programming KW - Pooling Problem KW - Gas Network Planning KW - Robust Optimization KW - Decomposition KW - Computations Y1 - 2017 UR - http://dx.doi.org/10.14279/depositonce-6015 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 T1 - Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite 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. T3 - ZIB-Report - 12-24 KW - SCIP, MIP, MINLP, CIP, LP, modeling, optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15598 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Held, Harald A1 - Huang, Wei A1 - Vigerske, Stefan T1 - Towards globally optimal operation of water supply networks N2 - 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. T3 - ZIB-Report - 12-25 KW - MINLP, global optimization, operative planning, water supply networks Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15603 SN - 1438-0064 ER -