TY - GEN A1 - Gamrath, Gerald A1 - Schubert, Christoph T1 - Measuring the impact of branching rules for mixed-integer programming N2 - 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. T3 - ZIB-Report - 17-34 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - strong branching Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64722 SN - 1438-0064 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Schubert, Christoph T1 - Measuring the impact of branching rules for mixed-integer programming T2 - Operations Research Proceedings 2017 N2 - 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. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_23 SP - 165 EP - 170 PB - Springer International Publishing ER - TY - THES A1 - Schubert, Christoph T1 - Multi-Level Lookahead Branching Y1 - 2017 ER - TY - GEN A1 - Gleixner, Ambros A1 - Bastubbe, Michael A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Schubert, Christoph A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Walter, Matthias A1 - Wegscheider, Fabian A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 6.0 N2 - 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. T3 - ZIB-Report - 18-26 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69361 SN - 1438-0064 ER -