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

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

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.