Optimization Online


Parallel Approximation, and Integer Programming Reformulation

Gabor Pataki (gabor***at***unc.edu)
Mustafa Tural (tural***at***email.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society