What is Polylib useful for?

Polyhedra, linear inequalities and linear programming can be seen as three views of the same concept. Polyhedra represent a geometrical point of view, linear inequalities - the algebraic point of view, and linear programming the optimization point of view. Basic results in polyhedral description are due to Farkas, Minkovski, Caratheodory, Weyl, Motzkin and Chernikova. Farkas' Lemma, the Duality Theorem, the Decomposition Theorem for polyhedra and the Finite Basis theorem for polytopes are theoretical results that stand behind any implementation. See A. Schrijver's book [SCH86] for more details. A polyhedral library can be used in various fields, some of them are listed here:

• In computational geometry, many algorithms involve polyhedra, for example: the convex hull of a finite point set, the vertex enumeration for a convex polytope, the computation of Voronoi diagram and Delaunay triangulation.
• The algebraic point of view is one of the most promising approaches to attack combinatorial optimization problems. Polyhedral investigations are the theoretical basis of so-called cutting plane algorithms. The polyhedral approach for an integer program works via the following basic scheme: with the given integer program, one associates the polyhedron defined as the convex hull of all its feasible solutions. On account of a classical theorem of Weyl one knows that this polyhedron can be represented as the intersection of half spaces, i.e., by means of a system of linear inequalities. One central question in polyhedral combinatorics is to find families of inequalities that are needed in a description of polyhedra associated with integer programs and to handle these inequalities algorithmically. The latter problem is known as the separation problem.
• The structural/lattice point of view is used in combinatorics and has applications in discrete dynamical systems.
• A very important area of applications is program optimization and parallelization. The iteration space of a loop nest can indeed be modeled by a system of rational linear constraints. As Polylib was developed in this context, we develop it in the next section.
• Finally, polyhedra are used in the field of program verification. For example, one can represent the range of a set of integer variables as a polyhedron, and use static analysis of programs to prove various properties which can be expressed as subsets of polyhedra.