In many real-world problems, a big scale gap can be observed between micro- and macroscopic scales of the problem because of the difference in mathematical (engineering, social, biological, physical, etc.) models and/or laws at different scales. The main objective of the 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 discrete optimization problems: linear ordering, network compression, graph partitioning, clustering, network generation, 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, partitioning and clustering problems. Our multiscale methods have proved themselves to be robust both as a first approximation and as more aggressive optimization solvers. The computational results will be presented.

Coffee and tea will be served in conjunction with WID Discovery at 3:30pm