@misc{BertholdHendel, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-And-Propagate}, issn = {1438-0064}, doi = {10.1007/s10732-014-9271-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17596}, abstract = {For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics.}, language = {en} } @misc{AchterbergBertholdHendel, author = {Achterberg, Tobias and Berthold, Timo and Hendel, Gregor}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, doi = {10.1007/978-3-642-29210-1_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13255}, number = {11-29}, 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} } @masterthesis{Hendel, type = {Bachelor Thesis}, author = {Hendel, Gregor}, title = {New Rounding and Propagation Heuristics for Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13322}, school = {Zuse Institute Berlin (ZIB)}, pages = {95}, abstract = {Die vorliegende Arbeit befasst sich mit Primalheuristiken f{\"u}r gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP). Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierf{\"u}r sind u. a. Optimierungsprobleme im {\"o}ffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation. Das L{\"o}sen von MIP ist NP-schwer und wird heutzutage meistens mit Hilfe von Branch-and-Bound-basierenden Algorithmen versucht. Das Branch-and-Bound-Ver\-fah\-ren profitiert unter Umst{\"a}nden von bereits fr{\"u}hzeitig zur Verf{\"u}gung stehenden L{\"o}sungen, daher sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute L{\"o}sung f{\"u}r eine große Zahl an MIPs liefern und somit die L{\"o}sezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen k{\"o}nnen. Primalheuristiken sind Suchverfahren zum Auffinden zul{\"a}ssiger L{\"o}sungen eines MIP. Verschiedene Typen von Primalheuristiken sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten w{\"a}hrend der Branch-and-Bound-Suche decken. W{\"a}hrend Start- und Rundeheuristiken zu Beginn des L{\"o}seprozesses eine große Rolle bei der Suche nach der ersten zul{\"a}ssigen L{\"o}sung haben, arbeiten Verbesserungs-heuristiken auf schon bekannten L{\"o}sungen, um neue, bessere L{\"o}sungen zu produzieren. Diese Arbeit besch{\"a}ftigt sich mit Primalheuristiken, welche Teil des MIP-L{\"o}sers SCIP sind. Im ersten Kapitel werden nach der Erarbeitung grundlegender Definitionen viele der durch Tobias Achterberg und Timo Berthold in SCIP integrierten heuristischen Verfahren vorgestellt und kategorisiert. Auf dieser Grundlage bauen dann die Kapitel 2-4 der Arbeit auf. In diesen werden drei zus{\"a}tzliche Heuristiken vorgestellt, im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine 2-Opt-Heuristik f{\"u}r MIP und eine neue Startheuristik, Shift-And-Propagate. Großer Wert wird in jedem Kapitel auf die algorithmische Beschreibung der Heuristiken gelegt, die stets anhand von motivierenden Beispielen eingef{\"u}hrt und anhand von Pseudocode-Algorithmen begleitet werden. Zus{\"a}tzlich enth{\"a}lt jedes Kapitel Auswertungen der mit den neuen Heuristiken gemessenen Ergebnisse von SCIP. Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.}, language = {en} } @article{BertholdHendelKoch2017, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {From feasibility to improvement to proof: three phases of solving mixed-integer programs}, series = {Optimization Methods and Software}, volume = {33}, journal = {Optimization Methods and Software}, number = {3}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1392519}, pages = {499 -- 517}, year = {2017}, abstract = {Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points.}, language = {en} } @inproceedings{HendelBertholdAchterberg, author = {Hendel, Gregor and Berthold, Timo and Achterberg, Tobias}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, series = {Operations Research Proceedings 2011}, booktitle = {Operations Research Proceedings 2011}, pages = {71 -- 76}, 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} } @misc{Hendel, type = {Master Thesis}, author = {Hendel, Gregor}, title = {Empirical Analysis of Solving Phases in Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54270}, pages = {159}, abstract = {Modern solving software for mixed-integer programming (MIP) incorporates numerous algorithmic components whose behavior is controlled by user parameter choices, and whose usefulness dramatically varies depending on the progress of the solving process. In this thesis, our aim is to construct a phase-based solver that dynamically reacts on phase transitions with an appropriate change of its component behavior. Therefore, we decompose the branch-and-bound solving process into three distinct phases: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps: First, we identify promising components for every solving phase individually and show that their combination is beneficial on a test bed of practical MIP instances. We then present and evaluate three heuristic criteria to make use of the phase-based solver in practice, where it is infeasible to distinguish between the last two phases before the termination of the solving process.}, language = {en} } @inproceedings{Hendel, author = {Hendel, Gregor}, title = {Exploiting Solving Phases for Mixed-Integer Programs}, series = {Operations Research Proceedings 2015}, booktitle = {Operations Research Proceedings 2015}, doi = {10.1007/978-3-319-42902-1_1}, pages = {3 -- 9}, abstract = {Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.}, language = {en} } @article{BertholdHendel, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-and-Propagate}, series = {Journal of Heuristics}, volume = {21}, journal = {Journal of Heuristics}, number = {1}, doi = {10.1007/s10732-014-9271-0}, pages = {73 -- 106}, abstract = {In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.}, language = {en} } @misc{Hendel, author = {Hendel, Gregor}, title = {Exploiting Solving Phases for Mixed-Integer Programs}, issn = {1438-0064}, doi = {10.1007/978-3-319-42902-1_1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57098}, abstract = {Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.}, language = {en} } @misc{Hendel, author = {Hendel, Gregor}, title = {Enhancing MIP branching decisions by using the sample variance of pseudo-costs}, issn = {1438-0064}, doi = {10.1007/978-3-319-18008-3_14}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54591}, abstract = {The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.}, language = {en} } @inproceedings{Hendel, author = {Hendel, Gregor}, title = {Enhancing MIP Branching Decisions by Using the Sample Variance of Pseudo Costs}, series = {Integration of AI and OR Techniques in Constraint Programming}, volume = {9075}, booktitle = {Integration of AI and OR Techniques in Constraint Programming}, doi = {10.1007/978-3-319-18008-3_14}, pages = {199 -- 214}, abstract = {The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a specialized version of a two-sample Student's t -test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.}, language = {en} } @misc{Hendel, 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}, 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{GeorgesGleixnerGojicetal., 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}, 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{AndersonHendelLeBodicetal., author = {Anderson, Daniel and Hendel, Gregor and Le Bodic, Pierre and Viernickel, Jan Merlin}, title = {Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation}, series = {AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence}, booktitle = {AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence}, abstract = {We propose a simple and general online method to measure the search progress within the branch-and-bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.}, language = {de} } @misc{HendelAndersonLeBodicetal., author = {Hendel, Gregor and Anderson, Daniel and Le Bodic, Pierre and Pfetsch, Marc}, title = {Estimating the Size of Branch-And-Bound Trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78144}, abstract = {This paper investigates the estimation of the size of Branch-and-Bound (B\&B) trees for solving mixed-integer programs. We first prove that the size of the B\&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B\&B search, such as the gap, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B\&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B\&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP.}, language = {en} } @article{GleixnerHendelGamrathetal., 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}, series = {Mathematical Programming Computation}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, 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{AndersonHendelLeBodicetal., author = {Anderson, Daniel and Hendel, Gregor and Le Bodic, Pierre and Viernickel, Jan Merlin}, title = {Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72653}, abstract = {We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.}, language = {en} } @article{Hendel, author = {Hendel, Gregor}, title = {Adaptive Large Neighborhood Search for Mixed Integer Programming}, series = {Mathematical Programming Computation}, journal = {Mathematical Programming Computation}, 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{BertholdHendelKoch, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {The Three Phases of MIP Solving}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1392519}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61607}, abstract = {Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.}, language = {en} } @article{HendelAndersonLeBodicetal., author = {Hendel, Gregor and Anderson, Daniel and Le Bodic, Pierre and Pfetsch, Marc}, title = {Estimating the Size of Branch-And-Bound Trees}, series = {INFORMS Journal on Computing}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2021.1103}, abstract = {This paper investigates the estimation of the size of Branch-and-Bound (B\&B) trees for solving mixed-integer programs. We first prove that the size of the B\&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B\&B search, such as the gap, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B\&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B\&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP.}, language = {en} }