  


Basis Reduction, and the Complexity of BranchandBound
Gabor Pataki (gaborunc.edu) Abstract: The classical branchandbound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulations, 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 (i.e. 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. For all A matrices we 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 nonzero 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. Keywords: Basis reduction, branchandbound, integer programming, shortest vector Category 1: Integer Programming Category 2: Integer Programming (Other ) Category 3: Combinatorial Optimization Citation: Download: [Postscript][PDF] Entry Submitted: 07/21/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  