An abstract model for branching and its application to mixed integer programming
From MaRDI portal
Abstract: The selection of branching variables is a key component of branch-and-bound algorithms for solving Mixed-Integer Programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their "LP gains", which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 "tree" instances where we achieve a 5% geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.
Recommendations
- Further results on an abstract model for branching and its application to mixed integer programming
- Branching on nonchimerical fractionalities
- Enhancing MIP branching decisions by using the sample variance of pseudo costs
- Information-based branching schemes for binary linear mixed integer problems
- Cloud branching
Cites work
- An Automatic Method of Solving Discrete Programming Problems
- Conflict analysis in mixed integer programming
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- Integer Programming
- Introduction to algorithms.
- MIPLIB 2003
- Mixed integer programming: analyzing 12 years of progress
- Numerical recipes. The art of scientific computing.
- PP is as Hard as the Polynomial-Time Hierarchy
- SCIP: solving constraint integer programs
- The polynomial-time hierarchy
Cited in
(28)- How important are branching decisions: fooling MIP solvers
- Projection heuristics for binary branchings between sum and product
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- An abstract model for branch-and-cut
- A generic exact solver for vehicle routing and related problems
- Further results on an abstract model for branching and its application to mixed integer programming
- Information-based branching schemes for binary linear mixed integer problems
- Faster MIP solutions via new node selection rules
- On learning and branching: a survey
- Comments on: ``On learning and branching: a survey
- Improving strong branching by domain propagation
- Backdoor branching
- Information-theoretic approaches to branching in search
- Branching on nonchimerical fractionalities
- Measuring the impact of branching rules for mixed-integer programming
- Cloud branching
- Improving strong branching by propagation
- Multivariable Branching: A 0-1 Knapsack Problem Case Study
- Decomposition Branching for Mixed Integer Programming
- Branching on multi-aggregated variables
- Enhancing MIP branching decisions by using the sample variance of pseudo costs
- Evaluating mixed-integer programming models over multiple right-hand sides
- A theoretical and computational analysis of full strong-branching
- Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications
- Faster integer-feasibility in mixed-integer linear programs by branching to force change
- On computing small variable disjunction branch-and-bound trees
- An abstract model for branch and cut
- Last fifty years of integer linear programming: a focus on recent practical advances
This page was built for publication: An abstract model for branching and its application to mixed integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1683695)
