Algebraic Algorithms in Discrete Optimization and Tools for Computational Convexity

离散优化中的代数算法和计算凸性工具

• 批准号: 0608785
• 负责人: Jesus De Loera
• 金额: --
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-15 至 2010-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0608785&HistoricalAwards=false
• 关键词: Algebraic; Algorithms; Discrete; Optimization; Tools

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.

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