CAREER: Foundational Aspects of Discrete Optimization: Theory and Algorithms

这个教师早期职业发展（CAREER）补助金的目的是在离散优化的基础上开辟新的天地。离散优化提供了用于解决大规模决策问题的解决方法，其中离散选择的组合（例如，这台发电机应该开还是关？）以及非离散的选择（例如，在化学过程中要保持什么浓度的化学品），以优化给定的目标（例如最小化成本，或过程的环境影响，或最大化利润）。这些解决方法广泛应用于各种科学，技术和物流问题，并以过去50-60年建立的数学理论为基础。然而，这些技术在面对当今一些复杂的大规模问题时显示出停滞的迹象。的现代应用。需要在基础层面上有重大的新想法才能跟上步伐。这项资助旨在通过在数学理论上取得突破来应对这一挑战，并利用该理论为离散优化打造更有效的工具。相关数学的部分内容适合向有积极性的高中生和本科生介绍本研究。该计划旨在展示数学在解决重要问题时的美丽和巨大应用性，吸引学生投身科学、技术、工程和数学领域。该计划将在混合整数优化的三个方面取得技术突破：（i）切割平面;（ii）对偶理论;（iii）混合整数优化求解器中分支切割范式的线性规划组件。一部分的努力将集中在翻译技术开发的线性问题的非线性设置。从凸几何，几何的数字，功能分析，代数拓扑和真实的代数几何的技术将在解决（一），（二）和（三）。其中许多联系都是在过去5-6年中提出的新见解，并且在解决混合整数优化领域长达数十年的开放问题方面非常有用。有很多希望，这种快速的进展可以继续深入调查这些领域的数学和混合整数优化之间的联系。在这个过程中，通过这项研究，可以促进数学家和工程师之间的新对话。总体技术贡献将是发展线性和非线性混合整数优化的理论基础，并为求解器中的切割生成和分支提供全新的思路。

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.