
The classical branchandbound algorithm for the integer feasibility problem
has exponential worst case complexity.
We prove that it is surprisingly efficient on reformulated problems, in which
the columns of the constraint matrix are short, and near orthogonal, i.e. a
reduced basis of the generated lattice; when the entries of A (the dense part
of the constraint matrix) are from {1, ..., M} for a large enough M,
branchandbound solves almost all reformulated instances at the rootnode. We
also prove an upper bound on the width of the reformulations along the last
unit vector.
The analysis builds on the ideas of Furst and Kannan to bound the number of
integral matrices for which the shortest vectors of certain lattices are long,
and also uses a bound on the size of the branchandbound tree based on the
norms of the GramSchmidt vectors of the constraint matrix.
We explore practical aspects of these results. First, we compute numerical
values of M which guarantee that 90, and 99 percent of the reformulated
problems solve at the root: these turn out to be surprisingly small when the
problem size is moderate. Second, we confirm with a computational study that
random integer programs become easier, as the coefficients grow.

We prove that the subset sum problem has a polynomial time computable
certificate of infeasibility for all $a$ weight vectors with density at most
$1/(2n)$ and for almost all integer right hand sides. The certificate is
branching on a hyperplane, i.e. by a methodology dual to the one explored by
Lagarias and Odlyzko; Frieze; Furst and Kannan; and Coster et. al.
The proof has two ingredients. We first prove that a vector that is near
parallel to $a$ is a suitable branching direction, regardless of the density.
Then we show that for a low density $a$ such a near parallel vector can be
computed using diophantine approximation, via a methodology introduced by Frank
and Tardos.
We also show that there is a small number of long intervals whose disjoint
union covers the integer right hand sides, for which the infeasibility is
proven by branching on the above hyperplane.

We show that in a knapsack feasibility problem an integral vector $p$, which
is short, and near parallel to the constraint vector gives a branching
direction with small integer width.
We use this result to analyze two computationally efficient reformulation
techniques on low density knapsack problems. Both reformulations have a
constraint matrix with columns reduced in the sense of Lenstra, Lenstra, and
Lov\'asz. We prove an upper bound on the integer width along the last variable,
which becomes 1, when the density is sufficiently small.
In the proof we extract from the transformation matrices a vector which is
near parallel to the constraint vector $a.$ The near parallel vector is a good
branching direction in the original knapsack problem, and this transfers to the
last variable in the reformulations.

We prove several inequalities on the determinants of sublattices in
LLLreduced bases. They generalize the inequalities on the length of the
shortest vector proven by Lenstra, Lenstra, and Lovasz, and show that
LLLreduction finds not only a short vector, but more generally, sublattices
with small determinants. We also prove new upper bounds on the product of the
norms of the first few vectors.