Parallel Approximation, and Integer Programming Reformulation

Gabor Pataki (gaborunc.edu)
Mustafa Tural (turalemail.unc.edu)

Abstract: 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.

Keywords: integer programming, near parallel vector, sublattice determinant, basis reduction,

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (Other )

Citation: Research Report, Department of Statistics and Operations Research, University of North Carolina at Chapel Hill

Download: [Postscript]

Entry Submitted: 12/25/2007
Entry Accepted: 12/26/2007
Entry Last Modified: 01/01/2008

Modify/Update this entry