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 $$ \ba{rcl} b' \, \leq & Ax & \,\, \leq b \\ x & \in & \zad{n} \ea $$ with $$ \ba{rcl} b' \, \leq & (AU)y & \,\, \leq b \\ y & \in & \zad{n}, \ea $$ where $U$ is a unimodular matrix computed via {\em basis reduction}, to make the columns of $AU$ short (i.e. have small Euclidean norm), and nearly orthogonal (see e.g. \cite{LLL82}, \cite{K83}). Our approach is termed column basis reduction, and the reformulation is called rangespace reformulation. It is motivated by the reformulation technique proposed for {\em 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 {\em decomposable knapsack problems (DKPs)}. DKPs generalize the instances proposed by Jeroslow, Chv\'atal and Todd, Avis, Aardal and Lenstra, and Cornu\'ejols et al. DKPs are knapsack problems with a constraint vector of the form $pM + r, \,$ with $p >0$ and $r$ integral vectors, $M$ an integer, $\norm{a} > \norm{r}, \, M > \norm{r}.$ If the parameters are suitably chosen in DKPs, we prove \begin{itemize} \item hardness results for these problems, when branch-and-bound branching on individual variables is applied; \item that they are easy, if one branches on the constraint $px$ instead; and \item 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. \eit 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 theoretical results.

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: Report 2006-07, Department of Statistics and Operations Research, UNC Chapel Hill

Download: [Postscript][PDF]

Entry Submitted: 06/27/2007
Entry Accepted: 06/28/2007
Entry Last Modified: 04/24/2008

Modify/Update this entry