CAREER: Foundational Aspects of Discrete Optimization: Theory and Algorithms

职业：离散优化的基础方面：理论和算法

• 批准号: 1452820
• 负责人: Amitabh Basu
• 金额: $ 50万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-05-01 至 2020-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1452820&HistoricalAwards=false
• 关键词: CAREER; Foundational; Aspects; Discrete; Optimization

This Faculty Early Career Development (CAREER) grant aims to break new ground in the fundamentals of discrete optimization. Discrete optimization provides solution methods for solving large-scale decision making problems where a combination of discrete choices (e.g., should this power generator be on or off?) and non-discrete choices (e.g., what concentration of a chemical is to be maintained in a chemical process) have to be made to optimize a given objective (such as minimize costs, or environmental impact of a process, or maximize profits). These solution methods are widely applied in a diverse suite of scientific, technological and logistical problems, and are grounded in mathematical theory that has been built in the last 50-60 years. However, these techniques are showing signs of stagnation in the face of some of the complex, large scale problems of today?s modern applications. Significantly new ideas at the foundational level are required to keep pace. This grant aims to meet this challenge by making breakthroughs in the mathematical theory, and leverage that theory to forge more efficient tools for discrete optimization. Part of the relevant mathematics is suitable for introducing motivated high-school students and undergraduates to this research. It hopes to showcase the beauty and enormous applicability of mathematics to solve important problems, and attract students to pursue careers in scientific, technological, engineering and mathematical fields.The technical breakthrough will be achieved in three aspects of mixed-integer optimization: (i) cutting planes, (ii) duality theory and, (iii) linear programming components of the branch-and-cut paradigm in mixed-integer optimization solvers. A part of the effort will be focussed on translating techniques developed for linear problems to the nonlinear setting. Techniques from convex geometry, geometry of numbers, functional analysis, algebraic topology and real algebraic geometry will be employed in tackling (i), (ii) and (iii). Many of these connections are recent insights made in the last 5-6 years and have proved extremely useful in resolving decades-long open questions in the field of mixed-integer optimization. There is a lot of hope that such rapid progress can be continued by deeper investigation of the connection between these areas of mathematics and mixed-integer optimization. In the process, fresh dialogue can be facilitated between mathematicians and engineers through this research. The overall technical contribution will be towards developing the theoretical foundations of linear and nonlinear mixed-integer optimization, and provide radically new ideas for cut generation and branching in solvers.

这项学院早期职业发展(Career)补助金的目的是在离散优化的基础上开辟新的天地。离散优化为解决大规模决策问题提供了解决方法，在这些问题中，离散选择的组合(例如，这个发电机应该打开还是关闭？)而且，必须做出非离散的选择(例如，在化学过程中保持何种浓度的化学品)，以优化给定的目标(例如，最小化成本，或过程的环境影响，或最大化利润)。这些解决方法被广泛应用于各种科学、技术和后勤问题中，并以过去50-60年来建立的数学理论为基础。然而，面对今天一些复杂、大规模的问题--S的现代应用，这些技术却显示出停滞不前的迹象。值得注意的是，需要基础层面的新想法来跟上步伐。这笔赠款旨在通过在数学理论上取得突破来应对这一挑战，并利用该理论为离散优化打造更有效的工具。部分相关数学知识适合介绍动机高中生和本科生进行本研究。它希望展示数学在解决重要问题方面的美丽和巨大的适用性，并吸引学生在科学、技术、工程和数学领域追求职业生涯。这一技术突破将在混合整数优化的三个方面实现：(I)割平面，(Ii)对偶理论，(Iii)混合整数优化求解器中分支-切割范式的线性规划组件。部分工作将集中在将为线性问题开发的技术转换到非线性环境中。将运用凸几何、数几何、泛函分析、代数拓扑和实代数几何的技巧来解决(I)、(II)和(III)。这些联系中的许多都是最近在过去5-6年中提出的见解，在解决混合整数优化领域长达数十年的悬而未决的问题方面已被证明非常有用。通过更深入地研究这些数学领域和混合整数优化之间的联系，可以继续取得如此快速的进步，这是很有希望的。在这个过程中，通过这项研究，数学家和工程师之间可以进行新的对话。总体的技术贡献将是发展线性和非线性混合整数优化的理论基础，并为求解器中的割集生成和分支提供全新的想法。