TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components N2 - 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. T3 - ZIB-Report - 13-08 KW - mixed-integer quadratically constrained programming KW - mixed-integer programming KW - branch-and-cut KW - nonconvex KW - global optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17754 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in Presolving for Mixed Integer Programming N2 - Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice. T3 - ZIB-Report - 13-48 KW - mixed-integer programming KW - presolving KW - preprocessing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42530 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 -