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.
