Optimization Online


Column basis reduction and decomposable knapsack problems

Bala Krishnamoorthy (bkrishna***at***math.wsu.edu)
Gabor Pataki (gabor***at***unc.edu)

Abstract: We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem

b'   ≤   Ax   ≤   b,   x ∈ Zn


b'   ≤   (AU)y   ≤   b,   y ∈ Zn,

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 branch-and-bound 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, branch-and-bound, 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 242-270.

Download: [PDF]

Entry Submitted: 06/27/2007
Entry Accepted: 06/28/2007
Entry Last Modified: 02/27/2010

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