6758
2017
eng
masterthesis
0
--
--
--
Multi-Level Lookahead Branching
Thorsten Koch
Christoph Schubert
Ambros Gleixner
Mathematical Optimization
Mathematical Optimization Methods
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
6728
2018
eng
165
170
6
conferenceobject
Springer International Publishing
0
2018-05-26
--
--
Measuring the impact of branching rules for mixed-integer programming
Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.
Operations Research Proceedings 2017
10.1007/978-3-319-89920-6_23
yes
urn:nbn:de:0297-zib-64722
2017-11-10
Gerald Gamrath
Gerald Gamrath
Christoph Schubert
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
6472
eng
reportzib
0
--
2017-07-27
--
Measuring the impact of branching rules for mixed-integer programming
Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.
1438-0064
urn:nbn:de:0297-zib-64722
10.1007/978-3-319-89920-6_23
Appeared in: Operations Reseach Proceedings 2017 (2018) pp 165-170
Gerald Gamrath
Gerald Gamrath
Christoph Schubert
ZIB-Report
17-34
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
branch-and-bound
eng
uncontrolled
branching rule
eng
uncontrolled
strong branching
Computational methods
Search theory
Integer programming
Mixed integer programming
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6472/ZR-17-34-rev1.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
Ambros Gleixner
Matthias Miltenberger
Michael Bastubbe
Leon Eifler
Tristan Gally
Gerald Gamrath
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Marco E. Lübbecke
Stephen J. Maher
Matthias Miltenberger
Benjamin Müller
Marc E. 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
Witzig, Jakob
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Viernickel, Jan Merlin
Wegscheider, Fabian
Plan4res
https://opus4.kobv.de/opus4-zib/files/6936/scipopt-60.pdf