6735
2017
eng
6:1
6:11
75
conferenceobject
0
--
--
--
Distributed Domain Propagation
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
16th International Symposium on Experimental Algorithms (SEA 2017)
10.4230/LIPIcs.SEA.2017.6
Leibniz International Proceedings in Informatics (LIPIcs)
yes
urn:nbn:de:0297-zib-61380
Robert Lion Gottwald
Robert Lion Gottwald
Stephen J. Maher
Yuji Shinano
Mathematical Optimization
Gottwald, Robert
Shinano, Yuji
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
6138
eng
reportzib
0
--
2016-12-07
--
Distributed domain propagation
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
1438-0064
urn:nbn:de:0297-zib-61380
10.4230/LIPIcs.SEA.2017.6
16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics, Volume 75, SEA 2017, June 21–23, 2017 - London, UK Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman (Eds.)
Robert Lion Gottwald
Robert Lion Gottwald
Stephen J. Maher
Yuji Shinano
ZIB-Report
16-71
eng
uncontrolled
mixed integer programming
eng
uncontrolled
parallelization
eng
uncontrolled
domain propagation
eng
uncontrolled
portfolio solvers
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gottwald, Robert
Shinano, Yuji
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6138/16-71.pdf
6291
2016
eng
masterthesis
0
--
--
--
Experiments with Concurrency and Heuristics in SCIP
Thorsten Koch
Robert Lion Gottwald
Ambros Gleixner
Mathematical Optimization
Mathematical Optimization Methods
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
Freie Universität Berlin
6836
eng
reportzib
0
--
2018-04-10
--
Feature-Based Algorithm Selection for Mixed Integer Programming
Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance.
In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out.
We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.
1438-0064
urn:nbn:de:0297-zib-68362
Alexander Georges
Gregor Hendel
Ambros Gleixner
Gorana Gojic
Robert Lion Gottwald
David Haley
Gregor Hendel
Bartlomiej Matejczyk
ZIB-Report
18-17
eng
uncontrolled
algorithm selection
eng
uncontrolled
mixed integer programming
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
ASTfSCM
MODAL-SynLab
Siemens
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6836/main.pdf
4815
eng
reportzib
0
--
2014-03-20
--
Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models
We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.
1438-0064
urn:nbn:de:0297-zib-48159
Ingmar Vierhaus
Armin Fügenschuh
Armin Fügenschuh
Robert Lion Gottwald
Stefan N. Grösser
ZIB-Report
14-08
eng
uncontrolled
System Dynamics
eng
uncontrolled
Optimal Control
eng
uncontrolled
Nonlinear Optimization
eng
uncontrolled
Spline Interpolation
ORDINARY DIFFERENTIAL EQUATIONS
DYNAMICAL SYSTEMS AND ERGODIC THEORY [See also 26A18, 28Dxx, 34Cxx, 34Dxx, 35Bxx, 46Lxx, 58Jxx, 70-XX]
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES
Mathematical Optimization
Gottwald, Robert
CRC1026
https://opus4.kobv.de/opus4-zib/files/4815/ZR-14-08.pdf
5303
2014
eng
conferenceobject
0
--
--
--
Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models
We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.
Proceedings of the 32nd International Conference of the System Dynamics Society
yes
urn:nbn:de:0297-zib-48159
Ingmar Vierhaus
Ingmar Vierhaus
Armin Fügenschuh
Robert Lion Gottwald
Stefan Grösser
Mathematical Optimization
Fügenschuh, Armin
Gottwald, Robert
CRC1026
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 Lübbecke
Matthias Miltenberger
Benjamin Müller
Marc 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
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
6629
eng
reportzib
0
--
2017-12-21
--
The SCIP Optimization Suite 5.0
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.
1438-0064
urn:nbn:de:0297-zib-66297
Ambros Gleixner
Gregor Hendel
Leon Eifler
Tristan Gally
Gerald Gamrath
Patrick Gemander
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Matthias Miltenberger
Benjamin Müller
Marc Pfetsch
Christian Puchert
Daniel Rehfeldt
Franziska Schlösser
Felipe Serrano
Yuji Shinano
Jan Merlin Viernickel
Stefan Vigerske
Dieter Weninger
Jonas T. Witt
Jakob Witzig
ZIB-Report
17-61
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear programming
eng
uncontrolled
mixed-integer linear programming
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
optimization solver
eng
uncontrolled
branch-and-cut
eng
uncontrolled
branch-and-price
eng
uncontrolled
column generation framework
eng
uncontrolled
parallelization
eng
uncontrolled
mixed-integer semidefinite programming
eng
uncontrolled
Steiner tree optimization
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
https://opus4.kobv.de/opus4-zib/files/6629/scipopt-50.pdf
6936
eng
reportzib
0
--
2018-07-02
--
The SCIP Optimization Suite 6.0
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders’ decomposition in a generic framework. GCG’s detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added
to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders’ framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.
1438-0064
urn:nbn:de:0297-zib-69361
Matthias Miltenberger
Ambros Gleixner
Michael Bastubbe
Leon Eifler
Tristan Gally
Gerald Gamrath
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Marco Lübbecke
Stephen J. Maher
Matthias Miltenberger
Benjamin Müller
Marc Pfetsch
Christian Puchert
Daniel Rehfeldt
Franziska Schlösser
Christoph Schubert
Felipe Serrano
Yuji Shinano
Jan Merlin Viernickel
Matthias Walter
Fabian Wegscheider
Jonas T. Witt
Jakob Witzig
ZIB-Report
18-26
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear programming
eng
uncontrolled
mixed-integer linear programming
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
optimization solver
eng
uncontrolled
branch-and-cut
eng
uncontrolled
branch-and-price
eng
uncontrolled
column generation framework
eng
uncontrolled
parallelization
eng
uncontrolled
mixed-integer semidefinite programming
eng
uncontrolled
Steiner tree optimization
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Plan4res
https://opus4.kobv.de/opus4-zib/files/6936/scipopt-60.pdf
6753
2017
eng
138
168
2
33
article
0
--
--
--
Using white-box nonlinear optimization methods in system dynamics policy improvement
We present a new strategy for the direct optimization of the values of policy functions. This approach is particularly well suited to model actors with a global perspective on the system and relies heavily on modern mathematical white-box optimization methods. We demonstrate our strategy on two classical models: market growth and World2. Each model is first transformed into an optimization problem by defining how the actor can influence the models' dynamics and by choosing objective functions to measure improvements. To improve comparability between different runs, we also introduce a comparison measure for possible interventions. We solve the optimization problems, discuss the resulting policies and compare them to the existing results from the literature. In particular, we present a run of the World2 model which significantly improves the published “towards a global equilibrium” run with equal cost of intervention.
System Dynamics Review
10.1002/sdr.1583
yes
Ingmar Vierhaus
Ambros Gleixner
Armin Fügenschuh
Robert Lion Gottwald
Stefan Grösser
Mathematical Optimization
Mathematical Optimization Methods
Gottwald, Robert
MODAL-SynLab
MODAL-Gesamt