Column basis reduction, decomposable knapsack and cascade problems

Thursday, July 28, 2005 - 4:00pm - 4:45pm
EE/CS 3-180
Gabor Pataki (University of North Carolina, Chapel Hill)
We propose a very simple preconditioning method for integer programming feasibility
problems: applying basis reduction to the constraint matrix, to make its columns shorter in
euclidean norm, and more orthogonal. Our approach -- termed column basis reduction, and abbreviated as CBR --
simplifies and generalizes the reformulation technique proposed for
equality constrained IPs by Aardal, Hurkens, Lenstra and others.

We describe a family of IP instances, called decomposable knapsack problems,
that generalize the ones proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra,
and Wolsey. We prove that 1) they need an exponential number of nodes
to solve, when branch-and-bound branching on individual variables is applied;
2) after the application of column basis reduction, a constant number of nodes suffice.

A subclass of decomposable knapsack problems is called cascade problems.
They were created to illustrate the surprising fact, that in hard IPs
a thin direction is sometimes not the best to branch on.
Besides having this structure, the cascade problems
-- despite having only one dense constraint -- are as difficult for commercial MIP solvers,
as the well-known marketshare problems.

Our computational study shows
that most difficult IPs recently used to test nontraditional IP algorithms
-- subset sum, strongly correlated knapsack problems, the marketshare problems, and our cascade problems --
become easy for a commercial IP solver after our preconditioning is applied.

Joint work with Bala Krishnamoorthy at Washington State University.