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
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- An Automatic Method of Solving Discrete Programming Problems
- Conflict analysis in mixed integer programming
- 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
(26)- An abstract model for branch and cut
- On computing small variable disjunction branch-and-bound trees
- Branching on multi-aggregated variables
- Branching on nonchimerical fractionalities
- Cloud branching
- Projection heuristics for binary branchings between sum and product
- Further results on an abstract model for branching and its application to mixed integer programming
- Information-theoretic approaches to branching in search
- Faster MIP solutions via new node selection rules
- Backdoor branching
- Improving strong branching by domain propagation
- Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications
- Enhancing MIP branching decisions by using the sample variance of pseudo costs
- Improving strong branching by propagation
- Decomposition Branching for Mixed Integer Programming
- A theoretical and computational analysis of full strong-branching
- Measuring the impact of branching rules for mixed-integer programming
- How important are branching decisions: fooling MIP solvers
- A generic exact solver for vehicle routing and related problems
- On learning and branching: a survey
- Information-based branching schemes for binary linear mixed integer problems
- Comments on: ``On learning and branching: a survey
- Faster integer-feasibility in mixed-integer linear programs by branching to force change
- An abstract model for branch-and-cut
- Evaluating mixed-integer programming models over multiple right-hand sides
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
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)
