Date

2010-05-06

Author

Pataki, Gábor
Tural, Mustafa Kemal
Wong, Erick B.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

192
views

0
downloads

Cite This

The classical branch-and-bound algorithm for the integer feasibility problem [GRAPHICS] has exponential worst case complexity. We prove that, it. is surprisingly efficient on reformulations of (01), 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 ale from {1, ,M} for a large enough M, branch-and-bound solves almost all reformulated instances at the root. node For all A matrices we prove an upper bound on the width of the reformulations along the last. unit vector Out results generalize the results of Furst, and kannan on the solvability of subset sum problems. also, we wove them via branch-and-bound, an algorithm traditionally considered inefficient from the theoretical point, of view We use two main tools. first, we find a bound on the size of the branch-and-bound tree based on the norms of the Gram-Schmidt vectors of the constiant. matrix. Second, building on the ideas of Furst and Kannan, we bound the number of integral matrices for which the shortest nonzero vectors of certain lattices ale long We explore practical aspects of these results 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 model ate We also confirm with a computational study that random integer programs become easier, as the coefficients grow.

Subject Keywords

Programs, Algorithm, variables, Integer, Subset sum problems

URI

https://hdl.handle.net/11511/53256

Collections

Department of Industrial Engineering, Conference / Seminar