Title: Column Basis Reduction and Hard Knapsack Problems

We present a very simple preconditioning method applicable to any integer program with integral data. It works by replacing the feasibility problem
     Ax ≤ b
     x ∈ Zⁿ
by the equivalent problem
     (AU) y ≤ b
              y ∈ Zⁿ
where U is a unimodular matrix chosen to make the columns of AU "relatively" short and orthogonal. In practice, U is found by lattice basis reduction, utilizing the algorithm of Lovasz, or some of its followers. Our reformulation method - termed column basis reduction - is a generalization and simplification of a reformulation technique proposed by Aardal, Lenstra and others for equality constrained problems.
The performance of column basis reduction is quite striking on some classes of problems: in one prominent example, a 0-1 knapsack problem with only 100 variables that could not be solved by a state-of-the-art commercial solver after enumerating 2 BILLION nodes, was solved at the rootnode after the reformulation was applied.
We present an analysis of this method for several classes of hard knapsack problems. We prove that on these problems branch-and-bound must take an exponential number of nodes to solve it, while after reformulation it solves after a constant number of nodes are enumerated.
Joint work with Bala Krishnamoorthy at UNC Chapel Hill.