Polyhedral Omega: Generalizations and Applications - POGA

Project details

We are looking for researchers in this project.

This project is about solving problems that are described by linear Diophantine systems (LDS). The kind of solutions we seek for LDS is in the form of rational generating functions. There are two types of such problems we deal with in POGA. Either computing all solutions to a linear Diophantine system (LDS), or computing the optimal solution with respect to some linear function (objective function). The first type of problems is very important in number theory and combinatorics, where computing the generating function of some objects with properties described by linear constraints is common. The second type of problems is ubiquitous in applications, since a lot of real world problems are modeled as Integer Linear Programs (ILP). In POGA we generalize Polyhedral Omega, a method for solving linear Diophantine systems, in order to find the generating function for a family of problems parametrized by their dimension on one hand, and we show how to use it for solving ILP on the other. In order to solve families of problems parametrized by dimension, we need to extend linear algebra to work in symbolic dimension. This means that the dimension is considered as a variable symbol throughout the computation. To achieve that, we define symbolic matrices, which are matrices described by a finite number of case distinctions. Manipulating symbolic matrices requires rewriting techniques, since the objects become complicated. The combination of rewriting techniques with polyhedral geometry is a novel approach. In this project we focus on using these techniques for extending Polyhedral Omega to Symbolic Polyhedral Omega. On the other hand, we develop a general method for solving ILP. The main advantage of the method is that it allows to analyze the geometry of the solution space through Brion decompositions. Moreover, for certain families of problems it may be competitive with existing heuristics.