Integer Hulls, Z-Polyhedra and Presburger Arithmetic in Action

When solving systems of polynomial equations and inequalities, the task of computing their solutions with integer coordinates is a much harder problem than that of computing their real solutions or that of computing all their solutions. In fact, in the presence of non-linear constraints, this task may simply become an undecidable problem [12, 15]. However, studying the integer solutions of linear systems of equations and inequalities is of practical importance in various areas of scientific computing. Two such areas are combinatorial optimization (in particular, integer linear programming) and compiler optimization (in particular, the analysis, transformation, and scheduling of nested loops in computer programs), where a variety of algorithms solve questions related to the points with integer coordinates in a given polyhedron. Another area is at the crossroads of computer algebra and polyhedral geometry, with topics such as toric ideals and Hilbert bases, see [16], as well as the manipulation of Laurent series, see [1].