Describing Polyhedra by Polynomial Inequalities

Project description:

The power of linear programming, one of today's most important optimization techniques, is - to a large extent - based on deep insights into the interplay between the geometry and algebraic description of polyhedra.

A new method of description is implied by recent results in real-algebraic geometry: Polyhedra fall into the class of basic closed semi-algebraic sets, the intersections of solutions of finitely-many non-strict polynomial inequalities. Due to a deep result of Bröcker and Scheiderer ([1],[2],[3]), every n-dimensional basic closed semi-algebraic set (and hence every n-dimensional polyhedron) can be described by at most n(n+1)/2 polynomial inequalities. Surprisingly, this is true independently on the combinatorial, algebraic, or geometric complexity of the set. As all known proofs of the Bröcker-Scheiderer result are non-constructive, an explicit construction of such systems of polynomials has been only recently discovered within this research group ([4],[5]).

The aim of this project is to further explore the new proof technique and implement the algorithm that is the basis of this result. New strategies for the solution of combinatorial optimization problems will be examined by adapting the results to special classes of combinatorially interesting polyhedra. Finally, general principles used in the theory of polyhedra, such as homogenization, are to be investigated with respect to their applicability in algebraic geometry.

Literature.

Publications.

M. Grötschel and M. Henk:
The representation of polyhedra by polynomial inequalities
Discrete Comput. Geom. 29 (2003), no.4, 485-504.

H. Bosse, M. Grötschel, M. Henk:
Polynomial inequalities representing polyhedra
Mathematical Programming 103:1 (2005) 35--44.