Branching is an important component of the branch-and-cut algorithm for solving mixed integer linear programs. Most solvers branch by imposing a disjunction of the form``$x_i \leq k \vee x_i \geq k+1$'' for some integer $k$ and some integer-constrained variable $x_i$. A generalization of this branching scheme is to branch by imposing a more general disjunction of the form ``$\pi x \leq \pi_0 \vee \pi x \geq \pi_0+1$'', where $\pi,\pi_0$ are integral. In this paper, we discuss the formulation of two optimization models for selecting such a branching disjunction and then describe methods of solution using a standard MILP solver. We report on computational experiments carried out to study the effects of branching on such disjunctions.
Citation
Technical Report, COR@L Lab, Lehigh University