  


Parallel Approximation, and Integer Programming Reformulation
Gabor Pataki (gaborunc.edu) Abstract: We analyze two integer programming reformulations of the ndimensional 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 n1 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 branchandbound 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 LLLreduced 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  