Basis Reduction Methods

2011-01-01
Patakı, Gabor
Tural, Mustafa Kemal
Show full item record
244
views
0
downloads
We review lattice based methods to solve integer programming feasibility problems, in particular, the algorithms of Lenstra, and Kannan, and the reformulation methods of Aardal, et al. and of Krishnamoorthy and Pataki. The unifying theme in all of them is transforming the problem urn:x-wiley:9780470400531:media:eorms0093:xm1 where P is a polyhedron, into urn:x-wiley:9780470400531:media:eorms0093:xm2 where the columns of B are short, and near orthogonal, that is, they form a reduced basis of the generated lattice, and the choice of B and the polyhedron Q is specific to each method. We give simple proofs of the polynomial running time of Lenstra's and Kannan's algorithms under the assumption that the dimension is fixed. We analyze the reformulation methods on knapsack problems with decomposable structure, and more surprisingly, we prove that they solve bounded integer programs with high probability by enumerating only one subproblem. We include several exercises as well, and we believe that the survey will be suitable to teach a 2–3 class long segment on lattice based methods in a course on Integer Programming.
http://onlinelibrary.wiley.com/book/10.1002/9780470400531
https://hdl.handle.net/11511/84150
Department of Industrial Engineering, Book / Book chapter

Suggestions

Implicit monolithic parallel solution algorithm for seismic analysis of dam-reservoir systems
Özmen, Semih; Kurç, Özgür; Department of Civil Engineering (2016)
This research mainly focuses on developing a computationally scalable and efficient solution algorithm that can handle linear dynamic analysis of dam-reservoir interaction problem. Lagrangian fluid finite elements are utilized and compressibility and viscosity of the fluid are taken into consideration during the reservoir modeling. In order to provide computational scalability and efficiency, domain decomposition methods implemented with parallel computing approaches such as Finite Element Tearing and Inter...
Basis reduction and the complexity of branch-and-bound
Pataki, Gábor; Tural, Mustafa Kemal; Wong, Erick B. (2010-05-06)
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 th...
Benchmark Solutions of Large Problems for Evaluating Accuracy and Efficiency of Electromagnetics Solvers
Gurel, Levent; Ergül, Özgür Salih (2011-07-08)
We present a set of benchmark problems involving conducting spheres and their solutions using a parallel implementation of the multilevel fast multipole algorithm (MLFMA). Accuracy of the implementation is tested by comparing the computational results with analytical Mie-series solutions. Reference solutions are made available on an interactive website to evaluate and compare the accuracy and efficiency of fast solvers. We also demonstrate the capabilities of our solver on real-life problems involving compl...
Hierarchical parallelisation strategy for multilevel fast multipole algorithm in computational electromagnetics
Ergül, Özgür Salih (Institution of Engineering and Technology (IET), 2008-01-03)
A hierarchical parallelisation of the multilevel fast multipole algorithm (MLFMA) for the efficient solution of large-scale problems in computational electromagnetics is presented. The tree structure of MLFMA is distributed among the processors by partitioning both the clusters and the samples of the fields appropriately for each level. The parallelisation efficiency is significantly improved compared to previous approaches, where only the clusters or only the fields are partitioned in a level.
Rigorous Solutions of Large-Scale Scattering Problems Discretized with Hundreds of Millions of Unknowns
Guerel, L.; Ergül, Özgür Salih (2009-09-18)
We present fast and accurate solutions of large-scale scattering problems using a parallel implementation of the multilevel fast multipole algorithm (MLFMA). By employing a hierarchical partitioning strategy, MLFMA can be parallelized efficiently on distributed-memory architectures. This way, it becomes possible to solve very large problems discretized with hundreds of millions of unknowns. Effectiveness of the developed simulation environment is demonstrated on various scattering problems involving canonic...
Citation Formats
G. Patakı and M. K. Tural, Basis Reduction Methods. 2011.
METU IIS - Integrated Information Service open@metu.edu.tr