

Column basis reduction and decomposable knapsack problems
Bala Krishnamoorthy (bkrishnamath.wsu.edu)
Gabor Pataki (gaborunc.edu)
Abstract:
We propose a very simple preconditioning method for integer programming feasibility
problems: replacing the problem
b' ≤ Ax ≤ b,
x ∈ Z^{n}
with
b' ≤ (AU)y ≤ b,
y ∈ Z^{n},
where U is a unimodular matrix computed via basis reduction, to
make the columns of AU short (i.e., have small Euclidean norm),
and nearly orthogonal. Our approach is termed column basis reduction,
and the reformulation is called rangespace reformulation. It is
motivated by the technique proposed for equality constrained IPs by
Aardal, Hurkens, and Lenstra. We also propose a simplified method to
compute their reformulation.
We also study a family of IP instances, called decomposable
knapsack problems (DKPs). DKPs generalize the instances proposed
by Jeroslow, Chvátal and Todd, Avis, Aardal and Lenstra, and
Cornuéjols et al. They are knapsack problems with a constraint
vector of the form a = pM + r, with
p > 0 and r integral vectors, and
M a large integer. If the parameters are suitably chosen in
DKPs, we prove
 hardness results, when branchandbound branching on individual
variables is applied;
 that they are easy, if one branches on the constraint
px instead; and
 that branching on the last few variables in either the rangespace
or the AHL reformulations is equivalent to branching on
px in the original problem.
We also provide recipes to generate such instances.
Our computational study confirms that the behavior of the studied
instances in practice is as predicted by the theory.
Keywords:
integer programming, branchandbound, basis reduction, split disjunctions
Category 1:
Integer Programming
Category 2:
Integer Programming (Other )
Category 3:
Combinatorial Optimization (Other )
Citation:
Discrete Optimization, 2009, Volume 6, Issue 3, pages 242270.
Download:
[PDF] Entry Submitted: 06/27/2007 Entry Accepted: 06/28/2007 Entry Last Modified: 02/27/2010 Modify/Update this entry
