Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Column basis reduction, and decomposable knapsack problemsOptimization
|Speaker: ||Gabor Pataki, University of North Carolina at Chapell Hill|
|Location: ||140 Physics/Geol|
|Start time: ||Thu, Nov 17 2005, 12:10PM|
We propose a very simple preconditioning method, called column basis
for integer programs:
applying a transformation to the constraint matrix, to make its columns
euclidean norm, and more orthogonal. It generalizes, and simplifies a
for equality constrained problems recently proposed by Aardal, Hurkens,
Lenstra and others.
CBR is attractive for two reasons: computationally, the transformation makes
many computationally hard problems easy to solve; and
mathematically, its effect
can be rigorously analyzed on a fairly wide class of hard IPs,
called decomposable knapsack problems.
This class generalizes the instances proposed by Jeroslow, Chvatal and Todd,
Avis, Aardal and Lenstra,
Cornuejols and others. We prove that 1) they need an exponential number of
to solve, for branch-and-bound;
2) after the transformation, a constant number of nodes suffice.
A subclass of decomposable knapsack problems is called cascade problems.
They illustrate the surprising fact, that in hard IPs
a "thin" direction is sometimes not the best to branch on.
A 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
The talk will assume no background in integer programming, and will
be accessible to a general audience.
Joint work with Bala Krishnamoorthy at Washington State University.