TY - GEN
A1 - Berthold, Timo
A1 - Gleixner, Ambros M.
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 - Berthold, Timo
A1 - Gleixner, Ambros M.
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 - Gleixner, Ambros M.
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 -
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 E.
A1 - Miltenberger, Matthias
A1 - Müller, Benjamin
A1 - Pfetsch, Marc E.
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 - 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 - GEN
A1 - Berthold, Timo
A1 - Gamrath, Gerald
A1 - Gleixner, Ambros M.
A1 - Heinz, Stefan
A1 - Koch, Thorsten
A1 - Shinano, Yuji
T1 - Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite
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 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.
T3 - ZIB-Report - 12-27
KW - LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl
Y1 - 2012
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15654
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 - GEN
A1 - Berthold, Timo
A1 - Gleixner, Ambros M.
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 を紹介し，その３つの構成要素：モデリン
グ言語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 の利用方法を示すとともに，利用可能なインタフェースの概要を示す．最後に，将来の開
発計画の概要について述べる．
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 - 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 -