TWiki> ECE Web>NewsDuttAward (2012-09-30, Main.ronaldf)EditAttach

Contratulations to ECE Professor Shantanu Dutt for receiving an NSF grant of $100,000 as PI for a project entitled "An Effective and Time-efficient Approach to Solving Linear Discrete Optimization Problems using Discretized Network Flow," Award No.CCF-1248945 that is effective September 15, 2012 and expires August 31, 2013.


Discrete optimization finds widespread use in almost all areas of human endeavor ranging from science to technology to business, and encompassing diverse applications such as chip design, power system design, robotics, bioinformatics, transportation, financial computing and industrial engineering. However, currently there is no general discrete optimization solver that can solve hard problems near-optimally in tractable runtimes (fast to moderate runtimes). To rectify this, this project will explore developing novel and efficient techniques for solving the class of 0/1 integer linear programming (ILP) problems that can be used to model a wide range of discrete optimization problems (DOPs). The approach used for this purpose is a solution technique termed discretized network flow (DNF), in which classical network flow (that solves a class of continuous linear programming problems), is constrained by special discrete requirements on the flow to yield valid solutions to 0/1 ILPs.

A successful completion of this project will yield algorithms and a software tool for solving large 0/1 ILP problems near-optimally and much faster than current techniques. This will represent a significant advance in the state-of-the-art of such solvers, and can be used to solve large DOPs more accurately and faster in many application areas ranging from genomics to chip design to robotics. This can help in answering fundamental issues in these application areas that have not been attempted so far, and also lead to better products and services in these areas. For example, in the area of chip design, the use of our solver can lead to much lower power and higher quality chips (e.g., with good performance and reliability) than are possible with current CAD tools, and thereby result in better and greener electronic products in several consumer and commercial application areas.

Details are available:

Topic revision: r1 - 2012-09-30 - 18:02:46 - Main.ronaldf
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF