Parallel Approximation, and Integer Programming Reformulation

Patakı, Gabor
Tural, Mustafa Kemal
We show that in a knapsack feasibility problem an integral vectorp, which is short, and nearparallel to the constraint vector gives a branching direction with small integer width.We use this result to analyze two computationally efficient reformulation techniques on lowdensity knapsack problems. Both reformulations have a constraint matrix with columns reducedin the sense of Lenstra, Lenstra, and Lov ́asz. We prove an upper bound on the integer widthalong the last variable, which becomes 1,when the density is sufficiently small.In the proof we extract from the transformation matrices a vector which is near parallel tothe constraint vectora.The near parallel vector is a good branching direction in the originalknapsack problem, and this transfers to the last variable in the reformulations
Citation Formats
G. Patakı and M. K. Tural, “Parallel Approximation, and Integer Programming Reformulation,” presented at the INFORMS Optimization Society Conference 2008, (14 - 16 Mart 2008), Amerika Birleşik Devletleri, 2008, Accessed: 00, 2021. [Online]. Available: