ISE SEMINAR 2-25-11

INDUSTRIAL AND SYSTEMS ENGINEERING DEPARTMENT
SPRING 2011 SEMINAR SERIES

TITLE:                      Multiscale Methods For Large-Scale Combinatorial
                                   Optimization Problems
SPEAKER:               Dr. Ilya Safro
                                   Argonne National Laboratory, Chicago, IL
DATE / TIME:          Friday, February 25, 2011
                                    2:30 – 3:30 p.m.
LOCATION:             Room 453 Mohler Lab, 200 W. Packer Avenue
ABSTRACT:  In many cases, a big scale gap can be observed between micro- and macroscopic scales of problems because of the difference in mathematical (engineering, social, biological, physical, etc.) models and/or laws at different scales.  The main objective of multiscale algorithms is to create a hierarchy of problems, each representing the original problem at different coarse scales with fewer degrees of freedom.  We will talk about different strategies of creating these hierarchies for large-scale combinatorial optimization problems: linear ordering, network compression, partitioning, clustering and constrained 2D-layout problem.  These strategies are inspired by 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 multiscale algorithm for the linear ordering problems.
            Our algorithms were developed for practical purposes and we compared them to many different methods such as: spectral sequencing, decomposition trees, multilevel-based, stochastic searches, genetic algorithms, path relinking, GRASP-based and other (including their combinations).  For almost all large-scale instances (about 200 application-based instances), we observed a significant improvement of the results and/or the computational time.  Our multiscale methods have proved themselves to be robust both as a first approximation and as more aggressive optimization solvers.
BIOGRAPHY:  Ilya Safro studied Mathematics and Computer Science at the Weizmann Institute of Science where he obtained his Ph.D. under the supervision of Achi Brandt and Dorit Ron.   Since 2007 Ilya was a postdoctoral fellow at Argonne National Laboratory.  Today he is an Argonne Scholar at the Laboratory of Advanced Numerical Simulations at Argonne National Laboratory.  His research interests include multiscale methods, network analysis, combinatorial optimization problems and machine learning.