Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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. It generalizes, and simplifies a reformulation method 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 nodes 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 applied. 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.