Journées de l'optimisation 2007 Optimizations days

In my lecture I will review briefly the handful of LP-algorithms that are either from a theoretical or from a practical point of view important for the solution of linear programs. I will sketch their advantages and disadvantages, in particular, for the solution of large-scale LPs. Semi-algebraic geometry investigates the real solution sets of finitely many polynomial equations and inequalities. I.e., polyhedra, the solution sets of LPs, are special cases of semi-algebraic sets. I will outline the somewhat surprising theorem (joint work with H. Bosse and M. Henk) that every n-dimensional polyhedron can be described by at most 2n polynomial inequalities and I will speculate whether or not this result can help solve linear and/or integer programs.