Mathematics – Optimization and Control
Scientific paper
2009-07-15
Mathematics
Optimization and Control
15 pages, 1 figure
Scientific paper
The classical branch-and-bound 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, branch-and-bound 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 branch-and-bound tree based on the norms of the Gram-Schmidt 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.
Pataki Gabor
Tural Mustafa
No associations
LandOfFree
Basis Reduction, and the Complexity of Branch-and-Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Basis Reduction, and the Complexity of Branch-and-Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Basis Reduction, and the Complexity of Branch-and-Bound will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-364897