April 25, 2013: Seminar Announcement - Shantanu Dutt: "Discretized Network Flow: A New Efficient Discrete Optimization Technique and its Application to Hard Problems"

Seminar Announcement

Discretized Network Flow: A New Efficient Discrete Optimization Technique and its Application to Hard Problems

Shantanu Dutt
Dept. of Electrical and Computer Engineering
University of Illinois at Chicago
Thursday, April 25, 2013
11:00 a.m., 1000 SEO Building


In this talk I will discuss a new discrete optimization technique called discretized network flow (DNF) that we have recently developed. DNF has been used to obtain solutions to several hard problems in various domains ranging from 0/1 MIP (mixed integer programming) to chip design to bioinformatics to TSP (traveling salesman problem) that match or significantly surpass the previous state-of-the-art. The development of DNF as a general discrete optimization problem (DOP) solver was motivated by the observations that: (a) classical min-cost network flow (NF) has a discrete flavor to it, in that the structure on which it operates is a directed graph, and (2) it is a continuous linear-programming (LP) solver (for a subset of LPs), and thus obtains solutions very time efficiently. However, clearly, NF cannot produce legal solutions to DOPs, and this brought up the issue of determining a set of discretization requirements that need to be imposed on NF in order to solve a large class of DOPs. Two important discretization requirements we have identified are: (1) Mutual exclusion of flows in the arcs of certain arc sets called mutually exclusive arc (MEA) sets. (2) Discrete arcs in which flows can only have discrete values (generally two: zero or full). The resulting NF computation with these discretizations is DNF. There are two stages to solving DOPs using DNF: (a) Modeling: in which the DOP (its basic elements, solution definition, objective function and constraints) are modeled by a DNF graph. (b) Algorithms: in which known algorithms with significant extensions were developed to find min-cost flow in DNF graphs. The end result of our work to date is a set of algorithms and DNF models that can solve 0/1 MIPs with linear or polynomial optimization functions, as well as various other DOPs directly (i.e., without requiring their MIP re-formulations).

We have applied DNF to solve several complex problems in various domains: (1) electronic design automation (or VLSI CAD), e.g., chip timing and power optimization under several constraints; (2) Genomics: genetic marker determination for complex diseases like lung cancer and rheumatoid arthritis (this is essentially a bi-clustering problem, and thus can also be applied to other domains like data mining); (3) linear and polynomial 0/1 MIP; (4) Classical DOPs like the traveling salesman's problem (TSP). In all instances, we have found that DNF obtains either significantly better solution qualities (the most prevalent case) or comparable qualities with, in some cases, 1-2 orders of runtime improvement, compared to state-of-the-art techniques and commercial MIP solvers like CPLEX and LINGO.


Shantanu Dutt is a professor at the Department of Electrical and Computer Engineering, University of Illinois at Chicago. He received his Ph.D. in computer science and engineering from the University of Michigan, Ann Arbor. Prof. Dutt was awarded a Research Initiation Award by the National Science Foundation. His current technical interests include CAD for sub-micron VLSI circuits, optimization algorithms, fault-tolerant computing, and testing and trusted design for emerging VLSI technologies. His research is or has been funded by NSF, DARPA, AFOSR and companies like Xilinx and Intel. He has published more than 75 papers in well-recognized archival journals and refereed conferences in all the above areas. His work has been cited about 1500 times, and he has an h-index of 21 and an i-index of 37. Prof. Dutt has received a Best-Paper award, a Most-Influential-Paper award, a Best-Paper nomination and a featured speaker recognition at premier conferences such as DAC and ICCAD (VLSI CAD conferences), and FTCS (fault tolerance conference, now renamed DSN). He has contributed invited articles in the Wiley Encyclopedia of Electrical and Electronics Engineering, and the Electrical Engineering Handbook from Academic Press. He has been on several NSF review panels, and on many technical program committees of conferences on fault-tolerant computing, parallel processing and VLSI CAD.

Host: Bob Sloan

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF