• Calendar

February 1, Monday
12:00 – 13:30

The Multiscale method is a class of algorithmic techniques for solving efficiently and effectively large-scale computational and optimization problems. This method was originally invented for solving elliptic partial differential equations and up to now it represents the most effective class of numerical algorithms for them. During the last two decades, there were many successful attempts to adapt the multiscale method for combinatorial optimization problems. Whereas the variety of continuous systems' multiscale algorithms turned into a separate field of applied mathematics, for combinatorial optimization problems they still have not reached an advanced stage of development, consisting in practice of a very limited number of multiscale techniques. In the first part of this talk we formulate the principles of designing multiscale algorithms for combinatorial optimization problems defined on a simple graph model. We present the results for the k-partitioning and a variety of linear ordering functionals (minimum linear arrangement/2-sum/bandwidth/workbound/wavefront sum). Since our algorithms were developed for practical purposes we compared them to many different heuristics: Spectral Sequencing, Optimally Oriented Decomposition Tree, Multilevel based, Simulated Annealing, Genetic Hillclimbing and other (including their combinations). In almost all cases we observed significant improvement of previous state-of-the-art results. We will cover a recently introduced measure of graph connectivity which can be important component of multilevel algorithms and other optimization problems on graphs.

If time permits we will present a multiscale coarsening scheme for minimizing a quadratic objective functional under planar inequality constraints. The scheme is demonstrated on a graph drawing problem in which the economical space utilization demand is evolved over the desired area rather than the widely used force-directed method, which preserves the non-overlapping property of the graph vertices. The non-overlapping property is automatically almost preserved as a result of equidensity constraints defined over the entire area. This demonstrates an ability of the algorithm to be used for solving a famous VLSI placement problem.