@misc{Hendel2018, author = {Hendel, Gregor}, title = {Adaptive Large Neighborhood Search for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71167}, year = {2018}, abstract = {Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.}, language = {en} } @misc{WitzigBertholdHeinz2018, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71170}, year = {2018}, abstract = {Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part.}, language = {en} } @article{WitzigGleixner2020, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, volume = {33}, journal = {INFORMS Journal on Computing}, number = {2}, doi = {10.1287/ijoc.2020.0973}, pages = {706 -- 720}, year = {2020}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @article{GleixnerHendelGamrathetal.2021, author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, year = {2021}, abstract = {We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.}, language = {en} } @misc{GeorgesGleixnerGojicetal.2018, author = {Georges, Alexander and Gleixner, Ambros and Gojic, Gorana and Gottwald, Robert Lion and Haley, David and Hendel, Gregor and Matejczyk, Bartlomiej}, title = {Feature-Based Algorithm Selection for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68362}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, booktitle = {OR 2018: International Conference on Operations Research}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances.}, language = {en} } @phdthesis{Miltenberger2023, author = {Miltenberger, Matthias}, title = {Linear Programming in MILP Solving - A Computational Perspective}, publisher = {Verlag Dr. Hut GmbH}, isbn = {9783843953238}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91873}, pages = {237}, year = {2023}, abstract = {Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly. This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub.}, language = {en} } @misc{WitzigGleixner2019, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2020.0973}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72204}, year = {2019}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @misc{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69563}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the \scip Optimization Suite on publicly available MIP instances.}, language = {en} } @misc{GamrathKochMartinetal.2013, author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in Presolving for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-015-0083-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42530}, year = {2013}, abstract = {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.}, language = {en} } @incollection{GamrathBertholdHeinzetal.2015, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-Based Primal Heuristics for Mixed Integer Programming}, volume = {13}, booktitle = {Optimization in the Real World}, publisher = {Springer Japan}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_3}, pages = {37 -- 53}, year = {2015}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.}, language = {en} } @misc{WitzigBertholdHeinz2016, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Experiments with Conflict Analysis in Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/978-3-319-59776-8_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61087}, year = {2016}, abstract = {The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.}, language = {en} } @misc{CheungGleixnerSteffy2016, author = {Cheung, Kevin K. H. and Gleixner, Ambros and Steffy, Daniel}, title = {Verifying Integer Programming Results}, issn = {1438-0064}, doi = {10.1007/978-3-319-59250-3_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61044}, year = {2016}, abstract = {Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.}, language = {en} } @misc{FujisawaShinanoWaki2015, author = {Fujisawa, Katsuki and Shinano, Yuji and Waki, Hayato}, title = {Optimization in the Real World}, volume = {13}, journal = {Mathematics for Industry (MFI)}, publisher = {Springer Tokyo Heidelberg New York Dordrecht London}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2}, year = {2015}, language = {en} } @misc{GleixnerBastubbeEifleretal.2018, author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, year = {2018}, abstract = {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.}, language = {en} } @article{GemanderChenWeningeretal.2020, author = {Gemander, Patrick and Chen, Wei-Kun and Weninger, Dieter and Gottwald, Leona and Gleixner, Ambros}, title = {Two-row and two-column mixed-integer presolve using hashing-based pairing methods}, volume = {8}, journal = {EURO Journal on Computational Optimization}, number = {3-4}, doi = {10.1007/s13675-020-00129-6}, pages = {205 -- 240}, year = {2020}, abstract = {In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.}, language = {en} } @article{GamrathBertholdSalvagnin2020, author = {Gamrath, Gerald and Berthold, Timo and Salvagnin, Domenico}, title = {An exploratory computational analysis of dual degeneracy in mixed-integer programming}, journal = {EURO Journal on Computational Optimization}, number = {8}, doi = {10.1007/s13675-020-00130-z}, pages = {241 -- 246}, year = {2020}, abstract = {Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable-constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates.}, language = {en} } @article{Gamrath2013, author = {Gamrath, Gerald}, title = {Improving strong branching by propagation}, volume = {7874}, journal = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems}, editor = {Gomes, Carla and Sellmann, Meinolf}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-642-38171-3_25}, pages = {347 -- 354}, year = {2013}, abstract = {Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.}, language = {en} } @article{GamrathLuebbecke2010, author = {Gamrath, Gerald and L{\"u}bbecke, Marco}, title = {Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs}, volume = {6049}, journal = {Experimental Algorithms}, editor = {Festa, P.}, publisher = {Springer-Verlag}, address = {Berlin}, doi = {10.1007/978-3-642-13193-6_21}, pages = {239 -- 252}, year = {2010}, language = {en} } @article{Gamrath2014, author = {Gamrath, Gerald}, title = {Improving strong branching by domain propagation}, volume = {2}, journal = {EURO Journal on Computational Optimization}, number = {3}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s13675-014-0021-8}, pages = {99 -- 122}, year = {2014}, abstract = {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 MIP solvers usually apply 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, the state-of-the-art hybrid branching rule can be improved this way as well. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.}, language = {en} } @inproceedings{HendelBertholdAchterberg2011, author = {Hendel, Gregor and Berthold, Timo and Achterberg, Tobias}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, booktitle = {Operations Research Proceedings 2011}, pages = {71 -- 76}, year = {2011}, abstract = {Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances.}, language = {en} }