1463
eng
reportzib
0
2012-02-06
2012-02-06
--
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.
1438-0064
12-07
urn:nbn:de:0297-zib-14631
10.1007/s10107-013-0635-2
Mathematical Programming
urn:nbn:de:0297-zib-14631
Timo Berthold
Timo Berthold
Ambros M. Gleixner
ZIB-Report
12-07
eng
uncontrolled
Primal Heuristic
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Large Neighborhood Search
eng
uncontrolled
Mixed-Integer Quadratically Constrained Programming
eng
uncontrolled
Nonconvex Optimization
Mixed integer programming
Quadratic programming
Nonconvex programming, global optimization
Nonlinear programming
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07.pdf
https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07_rev.pdf
1803
eng
reportzib
0
2013-04-16
2013-04-16
--
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.
1438-0064
urn:nbn:de:0297-zib-18030
10.1007/978-3-642-38527-8_20
Appeared in: Experimental Algorithms. 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings
Timo Berthold
Ambros Gleixner
Ambros M. Gleixner
ZIB-Report
13-14
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1803/ZR-13-14.pdf
1560
eng
reportzib
0
2012-07-25
2012-07-25
--
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.
1438-0064
urn:nbn:de:0297-zib-15603
10.3934/naco.2012.2.695
Appeared in: Numerical Algebra, Control and Optimization 2 (2012) 695-711
Ambros M. Gleixner
Ambros Gleixner
Harald Held
Wei Huang
Stefan Vigerske
ZIB-Report
12-25
eng
uncontrolled
MINLP, global optimization, operative planning, water supply networks
Mixed integer programming
Nonconvex programming, global optimization
Applications of mathematical programming
Mathematical Optimization
Gleixner, Ambros
Vigerske, Stefan
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1560/zibreport.pdf
6217
eng
reportzib
0
--
2017-08-03
--
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.
1438-0064
urn:nbn:de:0297-zib-62170
Stephen J. Maher
Ambros Gleixner
Tobias Fischer
Tristan Gally
Gerald Gamrath
Ambros Gleixner
Robert Lion Gottwald
Gregor Hendel
Thorsten Koch
Marco E. Lübbecke
Matthias Miltenberger
Benjamin Müller
Marc E. Pfetsch
Christian Puchert
Daniel Rehfeldt
Sebastian Schenker
Robert Schwarz
Felipe Serrano
Yuji Shinano
Dieter Weninger
Jonas T. Witt
Jakob Witzig
ZIB-Report
17-12
Computer aspects of numerical algorithms
Linear programming
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Witzig, Jakob
Maher, Stephan
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6217/scipoptsuite-40.pdf
https://opus4.kobv.de/opus4-zib/files/6217/scipoptsuite-401.pdf
6780
eng
reportzib
0
--
2018-03-08
--
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.
1438-0064
urn:nbn:de:0297-zib-67801
James Luedtke
Jonas Schweiger
Claudia D'Ambrosio
Jeff Linderoth
Jonas Schweiger
ZIB-Report
18-13
eng
uncontrolled
Pooling Problem
eng
uncontrolled
Relaxation
eng
uncontrolled
Extreme Points
Quadratic programming
Nonconvex programming, global optimization
Programming involving graphs or networks [See also 90C27]
Mathematical Optimization
MODAL-GasLab
MODAL-Gesamt
Schweiger, Jonas
Energy Network Optimization
https://opus4.kobv.de/opus4-zib/files/6780/ZR-18-13.pdf
6782
eng
reportzib
0
--
2018-03-08
--
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.
1438-0064
urn:nbn:de:0297-zib-67824
James Luedtke
Jonas Schweiger
Claudia D'Ambrosio
Jeff Linderoth
Jonas Schweiger
ZIB-Report
18-12
eng
uncontrolled
Pooling Problem
eng
uncontrolled
Relaxation
eng
uncontrolled
Valid Inequalities
Quadratic programming
Nonconvex programming, global optimization
Programming involving graphs or networks [See also 90C27]
Mathematical Optimization
MODAL-GasLab
MODAL-Gesamt
Schweiger, Jonas
Energy Network Optimization
https://opus4.kobv.de/opus4-zib/files/6782/ZR-18-12.pdf
1565
eng
reportzib
0
2012-07-31
2012-07-31
--
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.
1438-0064
urn:nbn:de:0297-zib-15654
Timo Berthold
Ambros Gleixner
Gerald Gamrath
Ambros M. Gleixner
Stefan Heinz
Thorsten Koch
Yuji Shinano
ZIB-Report
12-27
eng
uncontrolled
LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl
Linear programming
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Berthold, Timo
Gamrath, Gerald
Gleixner, Ambros
Heinz, Stefan
Koch, Thorsten
Shinano, Yuji
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1565/ZR-12-27.pdf
5937
eng
reportzib
0
--
2016-08-05
--
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.
1438-0064
urn:nbn:de:0297-zib-59377
10.1080/10556788.2017.1335312
Optimization Methods & Software
Stefan Vigerske
Ambros Gleixner
Ambros Gleixner
ZIB-Report
16-24
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Vigerske, Stefan
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5937/ZR-16-24.pdf
https://opus4.kobv.de/opus4-zib/files/5937/ZR-16-24-revised.pdf
1559
jpn
reportzib
0
2012-07-25
2012-07-25
--
SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法
Solving mixed integer linear and nonlinear problems using the 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 の利用方法を示すとともに，利用可能なインタフェースの概要を示す．最後に，将来の開
発計画の概要について述べる．
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.
1438-0064
urn:nbn:de:0297-zib-15598
Appeared in: Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming. Masakazu Muramatsu (ed. ) 2012, pp. 165-192
Timo Berthold
Ambros Gleixner
Ambros M. Gleixner
Stefan Heinz
Thorsten Koch
Yuji Shinano
ZIB-Report
12-24
mul
uncontrolled
SCIP, MIP, MINLP, CIP, LP, modeling, optimization
Linear programming
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
Heinz, Stefan
Koch, Thorsten
Shinano, Yuji
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1559/ZR-12-24.pdf
4217
eng
reportzib
0
2013-08-23
2013-08-23
--
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.
1438-0064
urn:nbn:de:0297-zib-42170
Timo Berthold
Timo Berthold
ZIB-Report
13-42
eng
uncontrolled
Primal Heuristic
eng
uncontrolled
MINLP
eng
uncontrolled
Mixed Integer Nonlinear Programming
eng
uncontrolled
Feasibility Pump
eng
uncontrolled
Large Neighborhood Search
Mixed integer programming
Nonconvex programming, global optimization
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
https://opus4.kobv.de/opus4-zib/files/4217/Berthold_MINLP_heuristics.pdf