AF: Small: Complexity of convex optimization with integer variables

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

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.