Gabor Pataki

Title:
Column basis reduction, and decomposable knapsack problems

Abstract:
We propose a very simple preconditioning method, called column basis reduction (CBR)
for integer programs: applying a transformation to the constraint matrix,
to make its columns shorter in euclidean norm, and more orthogonal.
CBR generalizes and simplifies a reformulation method
for equality constrained problems proposed by Aardal, Hurkens and Lenstra.

We give a rigorous analysis of CBR on several classes of fairly general,
and interesting IP instances, which are of interest on their own right.
A class, called decomposable knapsack
problems (DKPs) subsume the instances proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra,
Cornuejols and others, and include some interesting new families.
Some of these are: knapsacks with Fibonacci coefficients, and cascade problems.

Cascade problems illustrate the surprising fact, that in hard IPs a
"thin" direction is sometimes not the best to branch on. These are small 0-1 knapsack problems that seem as hard as the hardest "tricky" IPs proposed so far (e.g. marketshare), but have only one constraint and no unbounded variables. The key to solving them is branching on a hyperplane in whose direction the polyhedron's width is larger than 1, as opposed to the unit directions: i.e. thinner may not be better.

Joint work with Bala Krishnamoorthy at Washington State University, and Mustafa Tural at UNC Chapel Hill.