We analyze two integer programming reformulations of the n-dimensional knapsack feasibility problem without assuming any structure on the weight vector $a.$ Both reformulations have a constraint matrix in which the columns form a reduced basis in the sense of Lenstra, Lenstra, and Lov\'asz. The nullspace reformulation of Aardal, Hurkens and Lenstra has n-1 variables, and applies to equality constrained problems. The rangespace reformulation of Krishnamoorthy and Pataki leaves the number of variables n, and is applicable in general. Assuming that the norm of $a$ is at least $2^{(n/2 +1)n}$ we prove an upper bound on the number of branch-and-bound nodes that are created, when branching on the last variable in the reformulations. The upper bound becomes 1, when the norm of $a$ is large enough. The heart of the proof is an upper bound on the determinants of sublattices in LLL-reduced bases, and extracting a vector from the transformation matrices, which is ``near parallel'' to $a$. The near parallel vector is a good branching direction in the knapsack problem, and this transfers to the last variable in the reformulations.
Citation
Research Report, Department of Statistics and Operations Research, University of North Carolina at Chapel Hill
Article
View Parallel Approximation, and Integer Programming Reformulation