branching on hyperplanes

On generalized branching methods for mixed integer programming

  • Zhifeng Li
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    In this paper we present a restructuring of the computations in Lenstra’s methods for solving mixed integer linear programs. We show that the problem of finding a good branching hyperplane can be formulated on an adjoint lattice of the Kernel lattice of the equality constraints without requiring any dimension reduction. As a consequence the short … Read more

    Hard equality constrained integer knapsacks

  • Karen I. Aardal
  • Arjen K. Lenstra
    • Categories Integer Programming Tags , ,

    We consider the following integer feasibility problem: “Given positive integer numbers $a_0,a_1,\dots,a_n,$ with $\gcd(a_1,\dots,a_n)=1$ and $\va=(a_1,\dots,a_n)$, does there exist a vector $\vx\in\bbbz^n_{\ge \zero}$ satisfying $\va\vx = a_0$?” Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as … Read more