Mathematics – Optimization and Control
Scientific paper
2008-07-21
Mathematics
Optimization and Control
Scientific paper
We show that in a knapsack feasibility problem an integral vector $p$, which is short, and near parallel to the constraint vector gives a branching direction with small integer width. We use this result to analyze two computationally efficient reformulation techniques on low density knapsack problems. Both reformulations have a constraint matrix with columns reduced in the sense of Lenstra, Lenstra, and Lov\'asz. We prove an upper bound on the integer width along 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 to the constraint vector $a.$ The near parallel vector is a good branching direction in the original knapsack problem, and this transfers to the last variable in the reformulations.
Pataki Gabor
Tural Mustafa
No associations
LandOfFree
Parallel Approximation and Integer Programming Reformulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parallel Approximation and Integer Programming Reformulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel Approximation and Integer Programming Reformulation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-435343