Column basis reduction, and decomposable knapsack problems

Bala Krishnamoorthy, Gabor Pataki

We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b' <= Ax <= b, x \in Z^n with b' <= AUy <= b, y \in Z^n, where U…