TY - GEN A1 - Hendel, Gregor A1 - Miltenberger, Matthias A1 - Witzig, Jakob T1 - Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms N2 - 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. T3 - ZIB-Report - 18-36 KW - mixed integer programming KW - primal heuristics KW - multi armed bandit Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69563 SN - 1438-0064 ER - TY - CHAP A1 - Hendel, Gregor A1 - Miltenberger, Matthias A1 - Witzig, Jakob T1 - Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms T2 - OR 2018: International Conference on Operations Research N2 - 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. Y1 - 2018 ER - TY - GEN A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 18-60 KW - mixed integer programming KW - primal heuristics KW - large neighborhood search KW - multi armed bandit problem Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71167 SN - 1438-0064 ER - TY - JOUR A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming JF - Mathematical Programming Computation N2 - 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. Y1 - 2018 ER - TY - GEN A1 - Anderson, Daniel A1 - Hendel, Gregor A1 - Le Bodic, Pierre A1 - Viernickel, Jan Merlin T1 - Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation N2 - 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. T3 - ZIB-Report - 19-11 KW - Mixed-Integer Programming solvers KW - Restart KW - Progress measures KW - tree-size estimates Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72653 SN - 1438-0064 ER - TY - THES A1 - Hendel, Gregor T1 - Empirical Analysis of Solving Phases in Mixed Integer Programming N2 - 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. KW - mixed-integer programming KW - branch-and-cut Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54270 ER - TY - CHAP A1 - Hendel, Gregor T1 - Enhancing MIP Branching Decisions by Using the Sample Variance of Pseudo Costs T2 - Integration of AI and OR Techniques in Constraint Programming N2 - 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. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_14 VL - 9075 SP - 199 EP - 214 ER - TY - GEN A1 - Hendel, Gregor T1 - Enhancing MIP branching decisions by using the sample variance of pseudo-costs N2 - 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. T3 - ZIB-Report - 15-28 KW - mixed-integer programming KW - reliability branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54591 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor A1 - Anderson, Daniel A1 - Le Bodic, Pierre A1 - Pfetsch, Marc T1 - Estimating the Size of Branch-And-Bound Trees N2 - 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. T3 - ZIB-Report - 20-02 KW - mixed integer programming KW - machine learning KW - branch and bound KW - forecasting Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78144 SN - 1438-0064 ER - TY - JOUR A1 - Hendel, Gregor A1 - Anderson, Daniel A1 - Le Bodic, Pierre A1 - Pfetsch, Marc T1 - Estimating the Size of Branch-And-Bound Trees JF - INFORMS Journal on Computing N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1287/ijoc.2021.1103 ER -