TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A massively parallel STP solver N2 - In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research. T3 - ZIB-Report - 14-35 KW - Steiner Tree Problem KW - Mixed-Integer Programming KW - Branch-and-Cut KW - DIMACS Challenge Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52293 SN - 1438-0064 ER - 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 - GEN A1 - Gamrath, Gerald T1 - Improving strong branching by domain propagation N2 - One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013. T3 - ZIB-Report - 13-47 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - variable selection KW - strong branching KW - domain propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42546 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gamrath, Gerald A1 - Salvagnin, Domenico T1 - Exploiting Dual Degeneracy in Branching N2 - Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average. T3 - ZIB-Report - 19-17 KW - mixed integer programming KW - branching rule KW - search strategy KW - dual degeneracy Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73028 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on multi-aggregated variables N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. T3 - ZIB-Report - 15-10 KW - mixed-integer programming, branch-and-bound, branching rule, strong branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53829 SN - 1438-0064 ER -