generalized branching

On complexity of Selecting Branching Disjunctions in Integer Programming

  • Ashutosh Mahajan
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Branching is an important component of branch-and-bound algorithms for solving mixed integer linear programs. We consider the problem of selecting, at each iteration of the branch-and-bound algorithm, a general branching disjunction of the form $“\pi x \leq \pi_0 \vee \pi x \geq \pi_0 + 1”$, where $\pi, \pi_0$ are integral. We show that the problem … Read more

    Experiments with Branching using General Disjunctions

  • Ashutosh Mahajan
  • Ted K. Ralphs
    • Categories Integer Programming Tags , , ,

    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 … Read more