Improving Full Strong Branching Decisions by Incorporating Additional Information
Preprint
Abstract
The full strong branching (FSB) rule is well known to produce extremely small branch-and-bound trees. This rule guides branching decisions based exclusively on the information regarding local gains in the linear programming (LP) bounds. We identify and correct two key shortcomings in FSB. First, the LP gains may be overestimations of the improvement in global dual bounds whenever pruning is possible. We propose a modification to address this issue, that incorporates primal bounds and readjusts the relative importance of the larger and smaller LP gains. Second, FSB decisions may be myopic as they consider only local LP gains and cannot foresee the impact of branching decisions on feasibility or integrality beyond immediate children. To address this weakness, we present an approach that detects global asymmetry trends in infeasibility and integrality due to 0 and 1 assignments and incorporates them into the FSB score function. We further extend this approach to achieve more balanced trees even when the branch-and-bound tree prunes primarily by bounds. Using randomly generated problem instances with known structures, we derive insights and fine-tune our modified scores. Evaluation on MIPLIB 2017 Benchmark instances shows a 22-35\% reduction in mean tree sizes for solved cases and a 3.6-5.6\% decrease in the remaining gap for unsolved ones. Our approach extends to reliability branching (RB), where improved scores reduce mean tree sizes by 5-13\% on solved instances and lower the mean gap by 2.6-4.3\% on unsolved instances, depending on primal bound quality.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Primal Heuristics in Integer Programming2025
- Learning generalized strong branching for set covering, set packing, and 0–1 knapsack problemsEuropean Journal of Operational Research, 2022
- Measuring the impact of primal heuristicsOperations Research Letters, 2013
- Information-based branching schemes for binary linear mixed integer problemsMathematical Programming Computation, 2009
- Constraint Integer Programming: A New Approach to Integrate CP and MIP2008
- Capacitated lot-sizing with extensions: a review4OR, 2007
- Active-constraint variable ordering for faster feasibility of mixed integer linear programsMathematical Programming, 2006
- Branching rules revisitedOperations Research Letters, 2005
- A comparison of heuristics and relaxations for the capacitated plant location problemEuropean Journal of Operational Research, 1991
- Experiments in mixed-integer linear programmingMathematical Programming, 1971