Algebraic Algorithms in Discrete Optimization and Tools for Computational Convexity

这是一个计算数学的研究项目。我们的目标是使用新的代数思想来开发算法来解决离散优化问题。离散优化是研究有有限（但通常是非常多）潜在解的优化问题。这些不是列举的，而是由方程或不等式约束隐式定义的，例如，线性或非线性关系。我们专注于具有多项式约束的非线性整数规划，这是出了名的困难，我们探索了几种非传统的工具来解决它们，包括多元理性函数和复分析，多项式希尔伯特的Nullstellensatz证明，以及整数线性规划的新规范重新表述。我们也对计算凸性中密切相关的问题感兴趣。包括与最优化相关的多面体的计算、多面体并的实用逼近以及用凸规划方法求解几何问题。用于解决离散优化问题的软件和算法在许多具有巨大实际重要性的领域具有潜在的应用，例如数据挖掘，金融和经济学，运输调度（例如机组调度问题）和电路设计。离散优化问题的例子包括最小生成树问题（选择连接给定站点的最便宜网络）或旅行推销员问题（TSP）（选择给定地点集的最便宜旅行）。由于大多数离散优化问题是有用的，但很难解决，研究人员已经探索了特殊的结构，以便能够在实践中解决它们（例如，在TSP的情况下），或者满足于计算接近最优解的算法。在我们的项目中，我们尝试非传统的工具，基于最近的数学进展，作为解决这些非常困难的问题的方法。我们在这个项目中也有很强的教育成分。一些研究生和本科生都将在项目的发展中发挥重要作用。

This is a research project in Computational Mathematics. Our goal is to use new algebraic ideas for the development of algorithms to solve discrete optimization problems. Discrete optimization is the study of optimization problems in which there are a finite (but usually very large) number of potential solutions. These are not enumerated but rather defined implicitly by equation or inequality constraints, e.g., linear or nonlinear relations. We focus in non-linear integer programs with polynomial constraints which are notoriously difficult and we explore several non-traditional tools for solving them, including multivariate rational functions and complex analysis, polynomial Hilbert's Nullstellensatz certificates, and new canonical reformulations for integer linear programs. We are also interested on closely related problems in computational convexity. Including the computation of polyhedra related to optimization, the practical approximation of regions by unions of polyhedra and the solution of geometric problems using convex programming methods.Software and algorithms for solving discrete optimization problems has potential applications to many fields of huge practical importance, such as data mining, finances and economics, transport scheduling (e.g. crew scheduling problems), and circuit design. Examples of discrete optimization problems include the minimum spanning tree problem of selecting the least expensive network connecting given sites or the traveling salesman problem (TSP) consists of selecting the least expensive tour of a given set of locations. Since most discrete optimization problems are useful but very difficult to solve, researchers have explored special structures to be able to solve them in practice (e.g., in the case of the TSP) or settle for algorithms that compute near-optimal solutions. In our project we try non-traditional tools based on recent mathematical progress as a way to approach these very difficult problems. We also have a strong educational component for this project. Several graduate and undergraduate students will all play important roles in the project's development.