Improved branching disjunctions for branch-and-bound: An analytic center approach

Abstract

In classical branch-and-bound algorithms, the branching disjunction is often based on a single variable, which is a special case of the more general approach that involves multiple variables. In this paper, we present a new approach to generate good general branching disjunctions based on the shape of the polyhedron and interior-point concepts. The approach is based on approximating the feasible polyhedron using Dikin's inscribed ellipsoid, calculated using the analytic center from interior-point methods. We use the fact that the width of the ellipsoid in a given direction has a closed form expression to formulate a quadratic problem whose optimal solution is a thin direction of the ellipsoid. While solving a quadratic problem at each node of the branch-and-bound tree is impractical, we use an efficient neighborhood search heuristic for its solution. We report computational results on hard mixed integer problems from the literature showing that the proposed approach leads to smaller branch-and-bound trees and a reduction in the computational time as compared with classical branching and strong branching. As the computation of the analytic center is a bottleneck, we finally test the approach within a general interior-point based Benders decomposition where the analytic center is readily available, and show clear dominance of the approach over classical branching.