1199
eng
reportzib
0
2011-03-16
2011-03-16
--
On the computational impact of MIQCP solver components
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 linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.
11-01
urn:nbn:de:0297-zib-11998
Timo Berthold
-empty- (Opus4 user: )
Ambros M. Gleixner
Timo Berthold
Stefan Heinz
Stefan Vigerske
ZIB-Report
11-01
deu
uncontrolled
MIQCP
deu
uncontrolled
MIP
deu
uncontrolled
mixed-integer quadratically constrained programming
deu
uncontrolled
computational
deu
uncontrolled
nonconvex
MATHEMATICAL SOFTWARE
Mathematical programming methods [See also 90Cxx]
Mixed integer programming
Nonconvex programming, global optimization
Nonlinear programming
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
Heinz, Stefan
Vigerske, Stefan
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1199/ZR-11-01.pdf
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
1137
eng
reportzib
0
2009-07-09
2009-07-09
--
Extending a CIP framework to solve MIQCPs
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.
09-23
1438-0064
1186
urn:nbn:de:0297-zib-11371
App. in: Mixed Integer Nonlinear Programming. Jon Lee, Sven Leyffer (eds.) The IMA Volumes in Mathematics and its Applications, 154. Springer 2011, pp. 427-444
Timo Berthold
unknown unknown
Stefan Heinz
Stefan Vigerske
ZIB-Report
09-23
eng
uncontrolled
mixed integer quadratically constrained programming
eng
uncontrolled
constraint integer programming
eng
uncontrolled
convex relaxation
eng
uncontrolled
nonconvex
Mathematik
Mixed integer programming
Quadratic programming
Nonconvex programming, global optimization
Combinatorial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Mathematical Optimization
Berthold, Timo
Heinz, Stefan
Vigerske, Stefan
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.pdf
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.pdf
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.ps
https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.ps
1150
eng
reportzib
ZIB
0
2009-10-15
2009-10-15
--
Comparing MIQCP solvers to a specialised algorithm for mine production scheduling
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.
09-32
1438-0064
1206
urn:nbn:de:0297-zib-11507
10.1007/978-3-642-25707-0
Appeared in: Modeling, Simulation and Optimization of Complex Processes, Proc. of the 4th Int. Conf. on High Performance Scientific Computing, 2009, Hanoi, Vietnam. H. G. Bock et al. (eds.) 2012, pp. 25-39
Andreas Bley
unknown unknown
Ambros M. Gleixner
Thorsten Koch
Stefan Vigerske
ZIB-Report
09-32
Informatik, Informationswissenschaft, allgemeine Werke
Production models
Scheduling theory, deterministic [See also 68M20]
Mixed integer programming
Nonconvex programming, global optimization
Applications of mathematical programming
Mathematical Optimization
Gleixner, Ambros
Koch, Thorsten
Vigerske, Stefan
MATHEON-B19:MINLP
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1150/ZR_09_32.pdf
https://opus4.kobv.de/opus4-zib/files/1150/ZR_09_32.ps
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
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
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
1763
eng
reportzib
0
2013-10-01
2013-10-01
--
Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming
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.
1438-0064
urn:nbn:de:0297-zib-17631
10.1007/978-3-642-38171-3_26
Appeared in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013
Ambros M. Gleixner
Ambros Gleixner
Stefan Weltge
ZIB-Report
13-04
eng
uncontrolled
MINLP
eng
uncontrolled
optimization-based bound tightening
eng
uncontrolled
optimality-based bound tightening
eng
uncontrolled
OBBT
eng
uncontrolled
propagation
Nonconvex programming, global optimization
Mathematical Optimization
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1763/ZR-13-04.pdf
1775
eng
reportzib
0
2013-02-14
2013-02-14
--
Analyzing the computational impact of MIQCP solver components
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.
1438-0064
urn:nbn:de:0297-zib-17754
10.3934/naco.2012.2.739
Appeared in: Numerical Algebra, Control and Optimization vol. 2, no. 4 (2012) pp. 739-748
Timo Berthold
Timo Berthold
Ambros M. Gleixner
Stefan Heinz
Stefan Vigerske
ZIB-Report
13-08
eng
uncontrolled
mixed-integer quadratically constrained programming
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
branch-and-cut
eng
uncontrolled
nonconvex
eng
uncontrolled
global optimization
Mixed integer programming
Nonconvex programming, global optimization
Nonlinear programming
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
Heinz, Stefan
Vigerske, Stefan
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1775/ZR-13-08.pdf
5448
2014
eng
366
doctoralthesis
Dr. Hut Verlag
0
--
--
2014-11-06
Heuristic algorithms in global MINLP solvers
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.
978-3-8439-1931-9
http://www.zib.de/berthold/Berthold2014.pdf
Martin Grötschel
Timo Berthold
Timo Berthold
Thorsten Koch
Andrea Lodi
eng
uncontrolled
mixed integer nonlinear programming
eng
uncontrolled
primal heuristic
eng
uncontrolled
mixed integer programming
eng
uncontrolled
branching rule
eng
uncontrolled
large neighborhood search
eng
uncontrolled
solver software
Mixed integer programming
Nonconvex programming, global optimization
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
1764
eng
reportzib
0
2013-01-14
2013-01-14
--
Linear Underestimators for bivariate functions with a fixed convexity behavior
This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with
fixed convexity behavior over a box.
Computational results comparing our cut-generation algorithms with
state-of-the-art global
optimization software on a series of randomly generated test instances are reported and discussed.
1438-0064
urn:nbn:de:0297-zib-17641
urn:nbn:de:0297-zib-17641
Martin Ballerstein
Stefan Vigerske
Dennis Michaels
Stefan Vigerske
ZIB-Report
13-02
eng
uncontrolled
bivariate functions
eng
uncontrolled
convex envelope
eng
uncontrolled
global optimization
eng
uncontrolled
linear underestimator
Global optimization (NEW)
Nonconvex programming, global optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Mathematical Optimization
Mathematical Optimization Methods
Vigerske, Stefan
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/1764/ZR-13-02.pdf
https://opus4.kobv.de/opus4-zib/files/1764/ZR-13-02_testset.tgz
https://opus4.kobv.de/opus4-zib/files/1764/ZR-13-02revised.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
6691
2017
eng
411
doctoralthesis
0
--
--
2017-02-03
Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty
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.
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.
http://dx.doi.org/10.14279/depositonce-6015
Creative Commons - CC BY - Namensnennung 4.0 International
Thorsten Koch
Jonas Schweiger
Jonas Schweiger
Andrea Lodi
eng
uncontrolled
Nonconvexity
eng
uncontrolled
Uncertainty
eng
uncontrolled
Quadratic Programming
eng
uncontrolled
Relaxations
eng
uncontrolled
Cutting Planes
eng
uncontrolled
Standard Quadratic Programming
eng
uncontrolled
Pooling Problem
eng
uncontrolled
Gas Network Planning
eng
uncontrolled
Robust Optimization
eng
uncontrolled
Decomposition
eng
uncontrolled
Computations
Research exposition (monographs, survey articles)
Quadratic programming
Nonconvex programming, global optimization
Applications of mathematical programming
Mathematical Optimization
MODAL-GasLab
Schweiger, Jonas
Energy Network Optimization
Technische Universität Berlin
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
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
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
Schweiger, Jonas
Energy Network Optimization
https://opus4.kobv.de/opus4-zib/files/6782/ZR-18-12.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
Schweiger, Jonas
Energy Network Optimization
https://opus4.kobv.de/opus4-zib/files/6780/ZR-18-13.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
6947
eng
reportzib
0
--
2018-07-16
--
Exploiting structure in non-convex quadratic optimization
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.
1438-0064
urn:nbn:de:0297-zib-69476
Jonas Schweiger
Jonas Schweiger
ZIB-Report
18-35
eng
uncontrolled
Nonconvexity
eng
uncontrolled
Quadratic Programming
eng
uncontrolled
Relaxations
eng
uncontrolled
Cutting Planes
eng
uncontrolled
Standard Quadratic Programming
eng
uncontrolled
Pooling Problem
Quadratic programming
Nonconvex programming, global optimization
Mathematical Optimization
MODAL-GasLab
MODAL-Gesamt
Schweiger, Jonas
Energy Network Optimization
https://opus4.kobv.de/opus4-zib/files/6947/ZR-18-35.pdf