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-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-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-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-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-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-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-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-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-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-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