Seminar: November 23
Ilya Safro, Argonne National Laboratory
Multilevel Algorithms for Large-Scale Combinatorial Optimization Problems
The main objective of multilevel algorithms (MA) is to create a hierarchy of problems, each representing the original problem, but with fewer degrees of freedom. We will talk about different strategies of creating these hierarchies for graph related NP-hard optimization problems: linear ordering problems (logarithmic and linear arrangements, 2-sum, bandwidth, workbound), (hyper)graph partitioning and constrained 2D-layout problem. These strategies are based on the classical multigrid frameworks: Geometric Multigrid, Algebraic Multigrid and Full Approximation Scheme. We will present in details a framework for designing linear time Algebraic Multigrid based MA for the minimum linear and logarithmic arrangement problems. Unfortunately, theoretical bounds for MA for combinatorial optimization problems are not known. Our algorithms were developed for practical purposes and we compared them to many different heuristics such as: spectral sequencing, optimally oriented decomposition tree, multilevel based, simulated annealing, genetic algorithms, path relinking, GRASP-based and others (including their combinations). For almost all large-scale instances, we observed significant improvement of the results and/or the computational time. Our MA have proved themselves to be very robust both as a first approximation and as more aggressive energy minimizers.
If time allows, we will discuss the notion of algebraic distance between graph vertices. Algebraic distance is inspired by Bootstrap Algebraic Multigrid. It can be successfully used as ingredient of MA on graphs, and as a preprocessing for greedy choice steps in algorithms for various well know connectivity based problems (such as approximated maximum matching, approximated minimum independent set, TSP, etc.).