An Effective and Time-efficient Approach to Solving Linear Discrete Optimization Problems using Discretized Network Flow

使用离散网络流解决线性离散优化问题的有效且省时的方法

• 批准号: 1248945
• 负责人: Shantanu Dutt
• 金额: $ 10万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-15 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1248945&HistoricalAwards=false
• 关键词: Effective; Time; efficient; Approach; Solving

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.

离散优化在人类工作的几乎所有领域都得到了广泛的应用，从科学到技术再到商业，并涵盖了芯片设计、电力系统设计、机器人、生物信息学、交通运输、金融计算和工业工程等各种应用。然而，目前还没有通用的离散优化求解器可以在易处理的运行时(快速到中等运行时)近乎最佳地解决困难问题。为了纠正这一点，该项目将探索开发新的和有效的技术来解决0/1整数线性规划(ILP)问题，这些问题可以用于对广泛的离散优化问题(DOP)进行建模。这是一种称为离散化网络流的求解技术，在这种技术中，经典的网络流(解决一类连续线性规划问题)受到流的特殊离散要求的约束，从而得到0/1 ILP的有效解。该项目的成功完成将产生一个算法和软件工具，用于以接近最优的方式解决大型0/1 ILP问题，并且比现有技术快得多。这将代表着此类解算器的最新技术水平的重大进步，并可用于在从基因组学到芯片设计再到机器人的许多应用领域更准确、更快地求解大DOPS。这可以帮助回答这些应用领域中迄今尚未尝试的基本问题，并在这些领域带来更好的产品和服务。例如，在芯片设计领域，使用我们的求解器可以产生比使用当前CAD工具更低的功耗和更高质量的芯片(例如，具有良好的性能和可靠性)，从而在几个消费和商业应用领域产生更好和更环保的电子产品。