High-performance computations with rational generating functions

这是离散计算数学的一个研究项目。研究者和他的学生将使用并显著推进Barvinok（1994）引入的短有理生成函数技术。简而言之，该技术允许有效地计算多面体族中的整数点，这有许多应用。这个项目的研究将涉及数学优化、离散几何、凸性和基于计算机的搜索等方法。PI编写并维护了开源软件“LattE macchiato”，这是两个最先进的短有理生成函数实现之一。过去和目前的PI研究已经通过引入算法和证明其计算复杂性的定理，证明了短有理生成函数具有巨大的计算潜力，超出了迄今为止在实践中所取得的成就。这种潜力涉及到许多领域的应用，包括组合学、数学优化（非线性混合整数规划）和算法博弈论。本课题的总体主题是寻找具有特殊性质的分解格式的新定理，推广原始空间或对偶空间中简单锥的有符号分解。在其他技术中，PI的研究将涉及基于计算机的最佳分解方案搜索。这是一个深刻的理论兴趣，独立于算法的结果。在新的分解和其他新技术（如利用对称性）的基础上，PI期望开发和实现新的高效算法，包括用于多核系统和集群的并行实现。总体目标是显著扩展短有理生成函数方法的适用范围。这些方法的成功将通过本建议中列出的具体计算挑战来衡量，这些挑战对于当前的计算机软件来说是难以解决的。数学优化是在资源有限的情况下尽可能做出最佳决策的科学。在过去的10年里，人们已经清楚地认识到，从生物技术到化学工程和医疗保健等一系列关键技术，都依赖于解决一种称为“非线性混合整数规划”的复杂数学优化问题的能力。PI和合作者最近表明，一种称为短有理生成函数的数学技术非常强大，可以解决这些优化问题，至少在数学理论方面超过所有其他已知技术。然而，理论与实践之间仍然存在着巨大的差距。本课题是关于短有理生成函数技术的基础研究，以帮助弥补这一空白。这将带来新的数学见解和更有效的算法，以及新的、更强大的开源数学软件。这个项目也有很强的教育影响。PI计划在这一研究领域培养几名本科生和研究生。培训的一个组成部分将是根据本提案的主题创建新的课程材料，并将其用于本科生和研究生的新课程。训练的第二个组成部分包括学生直接参与这个研究项目，包括理论工作、计算机实验和软件实现，所有这些都将导致本科生和研究生的论文。

This is a research project in Discrete Computational Mathematics. The investigator and his students will use and significantly advance the technology of short rational generating functions introduced by Barvinok (1994). In short, this technology allows to efficiently count the integer points in families of polytopes, which has numerous applications. Research in this project will involve methods from mathematical optimization, discrete geometry, convexity, and computer-based search. The PI has written and maintains the open-source software "LattE macchiato", which is one of the two state-of-the-art implementations of short rational generating functions. Past and current research of the PI has established, by introducing algorithms and proving theorems on their computational complexity, that short rational generating functions have a large computational potential that goes beyond what has been achieved so far in practice. This potential relates to applications in many fields, including combinatorics, mathematical optimization (nonlinear mixed integer programming), and algorithmic game theory. The general theme of the research project is to find new theorems on decomposition schemes with special properties, generalizing the signed decomposition of simplicial cones in the primal or dual space. The PI's research will involve, among other techniques, computer-based search for optimal decomposition schemes. There is a deep theoretical interest in this, independent of algorithmic consequences. On the basis of the new decompositions and other new techniques (such as exploiting symmetry), the PI expects to develop and implement new efficient algorithms, including a parallel implementation for use on multi-core systems and clusters. The overall goal is to expand the range of applicability of short rational generating function methods significantly. The success of these methods will be measured by specific computational challenges listed in this proposal, which are intractable by current computer software.Mathematical optimization is the science of making the best decisions possible, when resources are limited. In the past 10 years it has become clear that a wide array of key technologies, ranging from biotechnology to chemical engineering and healthcare, depend on the ability to solve a complicated type of mathematical optimization problems, called "nonlinear mixed-integer programs". The PI and collaborators have shown recently that a mathematical technique called short rational generating functions is very powerful to solve these optimization problems, surpassing all other known techniques, at least in mathematical theory. However, there still is a huge gap between theory and practice. This research project is about fundamental research on this technique of short rational generating functions, to help bridge the gap. This will lead to new mathematical insights and more efficient algorithms and new, more powerful open-source mathematical software. This project also has a strong educational impact. The PI plans to train several undergraduate and graduate students in this research area. One component of the training will be to create new course material on the topics of this proposal, and to use it for new classes for undergraduate and graduate students. The second component of the training consists of direct involvement of students in this research project, involving theoretical work, computer experimentation, and software implementation, all of which lead to undergraduate and graduate theses.