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