TY - GEN A1 - Bestuzheva, Ksenia A1 - Völker, Helena A1 - Gleixner, Ambros T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds N2 - Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89510 SN - 1438-0064 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Völker, Helena T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds N2 - Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches. T3 - ZIB-Report - 22-23 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88306 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Witzig, Jakob T1 - Conflict Analysis for MINLP N2 - The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality. T3 - ZIB-Report - 20-20 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78964 SN - 1438-0064 ER - TY - GEN A1 - Schweiger, Jonas T1 - Exploiting structure in non-convex quadratic optimization 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 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. T3 - ZIB-Report - 18-35 KW - Nonconvexity KW - Quadratic Programming KW - Relaxations KW - Cutting Planes KW - Standard Quadratic Programming KW - Pooling Problem Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69476 SN - 1438-0064 ER - TY - GEN A1 - Luedtke, James A1 - D'Ambrosio, Claudia A1 - Linderoth, Jeff A1 - Schweiger, Jonas T1 - Strong Convex Nonlinear Relaxations of the Pooling Problem: Extreme Points N2 - 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. T3 - ZIB-Report - 18-13 KW - Pooling Problem KW - Relaxation KW - Extreme Points Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67801 SN - 1438-0064 ER - TY - GEN A1 - Luedtke, James A1 - D'Ambrosio, Claudia A1 - Linderoth, Jeff A1 - Schweiger, Jonas T1 - Strong Convex Nonlinear Relaxations of the Pooling Problem N2 - 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. T3 - ZIB-Report - 18-12 KW - Pooling Problem KW - Relaxation KW - Valid Inequalities Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67824 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 - Maher, Stephen J. A1 - Fischer, Tobias A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schenker, Sebastian A1 - Schwarz, Robert A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Weninger, Dieter A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 4.0 N2 - 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. T3 - ZIB-Report - 17-12 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62170 SN - 1438-0064 ER - TY - GEN A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework N2 - 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. T3 - ZIB-Report - 16-24 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59377 SN - 1438-0064 ER - TY - THES A1 - Berthold, Timo T1 - Heuristic algorithms in global MINLP solvers N2 - 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. KW - mixed integer nonlinear programming KW - primal heuristic KW - mixed integer programming KW - branching rule KW - large neighborhood search KW - solver software Y1 - 2014 UR - http://www.zib.de/berthold/Berthold2014.pdf SN - 978-3-8439-1931-9 PB - Dr. Hut Verlag ER -