AF: Small: Complexity of convex optimization with integer variables

AF：小：整数变量凸优化的复杂性

• 批准号: 2006587
• 负责人: Amitabh Basu
• 金额: $ 40.29万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006587&HistoricalAwards=false
• 关键词: AF; Small; Complexity; convex; optimization

Mathematical optimization is a key ingredient in quantitative decision making. A wide range of decision-making problems ranging from designing vehicle routes by delivery companies to minimize CO2 impact, to finding most efficient deployment of resources for national security and defense, use mathematical optimization tools. The field of optimization, studied from the times of Newton and Lagrange, has constantly encountered new challenges coming from problems in the natural and social sciences, as well as engineering and technological applications. Broadly speaking, one wishes to find the optimal values of certain parameters that minimize or maximize some objective function of those parameters, while respecting certain constraints on those parameters. In the 20th century, it has become increasingly important to handle constraints that impose the restriction that the parameters can only take discrete values. For example, when designing an optimal inventory plan for a retail store, one must decide on the number of units to stock for a certain product (say a particular type of bottled beverage) which must be a whole number (e.g., one cannot stock 10.5 bottles). While the theory and computational aspects of optimization with continuous valued parameters is very well-developed, handling constraints that model discreteness are notoriously hard. The project will aim to address some of the outstanding questions in this context.A large class of such discrete optimization problems can be modeled by using convex objective functions and constraints, apart from the restriction of integrality on the variables. The algorithmic complexity of this problem is not as well-understood as the complexity of convex optimization with continuous variables, in spite of several breakthroughs since the 1950s. In particular, an outstanding open question is nailing down the precise dependence of the running time for the best possible algorithms, on the number of integer constrained variables. This would involve not only designing an algorithm with provable complexity guarantees, but also establishing lower bounds on any algorithmic approach for the problem. The project will explore both information-theoretical lower bounds, as well as bounds that can be established under standard computational complexity hypotheses. Moreover, the analysis of algorithms that are currently deployed in practice will be undertaken from a rigorous perspective. There is ample scope for strengthening the algorithmic foundations of these methods even though they have received a lot of attention in the literature from a structural and empirical perspective. All of these questions are also known to have intimate connections with computational logic and proof complexity. The resolution of these questions will thus require bringing together techniques from areas like proof complexity, logic, computational complexity and ideas in convex geometry, geometry of numbers and polyhedral theory. Successful resolution will completely or partially resolve questions open for decades in the area, build new connections between pure mathematics and computer science, and contribute to the theoretical foundations of optimization over integers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

数学优化是定量决策的关键因素。从设计运输公司的车辆路线以尽量减少二氧化碳的影响，到为国家安全和国防找到最有效的资源部署，各种各样的决策问题都使用数学优化工具。从牛顿和拉格朗日时代开始研究的优化领域不断遇到来自自然科学和社会科学问题以及工程和技术应用的新挑战。广义地说，人们希望找到某些参数的最优值，使这些参数的某些目标函数最小化或最大化，同时尊重这些参数的某些约束。在20世纪，处理参数只能取离散值的约束变得越来越重要。例如，在为零售商店设计最优库存计划时，必须决定为某种产品（例如某种特定类型的瓶装饮料）库存的单位数量，该数量必须是整数（例如，不能库存10.5瓶）。虽然连续参数优化的理论和计算方面已经非常发达，但处理模型离散性的约束是出了名的困难。该项目旨在解决这方面的一些突出问题。一大类这样的离散优化问题可以通过使用凸目标函数和约束来建模，除了对变量的完整性的限制。尽管自20世纪50年代以来取得了几次突破，但这个问题的算法复杂性并不像连续变量凸优化的复杂性那样被很好地理解。特别是，一个突出的开放问题是确定最佳算法的运行时间与整数约束变量的数量的精确依赖关系。这不仅涉及设计一个具有可证明复杂性保证的算法，而且还涉及为该问题的任何算法方法建立下界。该项目将探索信息理论的下界，以及可以在标准计算复杂性假设下建立的边界。此外，将从严格的角度对目前在实践中部署的算法进行分析。尽管从结构和经验的角度来看，这些方法在文献中受到了很多关注，但仍有足够的空间来加强这些方法的算法基础。众所周知，所有这些问题都与计算逻辑和证明复杂性有着密切的联系。因此，这些问题的解决需要将证明复杂性、逻辑学、计算复杂性以及凸几何、数几何和多面体理论中的思想等领域的技术结合起来。成功的解决将完全或部分解决该领域几十年来的问题，在纯数学和计算机科学之间建立新的联系，并为整数优化的理论基础做出贡献。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Two-halfspace closure

两半空间闭合

• DOI: 10.1007/s10107-022-01802-x
• 发表时间: 2022
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Basu, Amitabh;Jiang, Hongyi
• 通讯作者: Jiang, Hongyi

Complexity of optimizing over the integers

整数优化的复杂性

• DOI: 10.1007/s10107-022-01862-z
• 发表时间: 2022
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Basu, Amitabh

Enumerating Integer Points in Polytopes with Bounded Subdeterminants

枚举具有有界子行列式的多面体中的整数点

• DOI: 10.1137/21m139935x
• 发表时间: 2022
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Jiang, Hongyi;Basu, Amitabh
• 通讯作者: Basu, Amitabh

Admissibility of Solution Estimators for Stochastic Optimization

随机优化解估计器的可接受性

• DOI: 10.1137/19m1291546
• 发表时间: 2021
• 期刊: SIAM Journal on Mathematics of Data Science
• 影响因子: 3.6
• 作者: Basu, Amitabh;Nguyen, Tu;Sun, Ao
• 通讯作者: Sun, Ao

Complexity of branch-and-bound and cutting planes in mixed-integer optimization

混合整数优化中分支定界和割平面的复杂性

• DOI: 10.1007/s10107-022-01789-5
• 发表时间: 2022
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Basu, Amitabh;Conforti, Michele;Di Summa, Marco;Jiang, Hongyi
• 通讯作者: Jiang, Hongyi