Bases de Gröbner: eliminación y programación lineal entera

Abstract

Gröbner basis is a basic concept in Computational Algebra; it was introduced by the Austrian mathematician Bruno Buchberger in 1965. A Gröbner basis of an ideal in a polinomial ring with coefficients over a field is a special generator set of the ideal. These bases have a very useful properties and applications. In this project we deal with the theory of Gr¨obner bases, starting with the definition of the concept, studying their main properties and explaining Buchberger’s algorithm for their computation. Then we give some applications The main objective of Elimination theory is the resolution of systems of polynomials equations. We use the Elimination theorem and the Extension theorem repeatedly, so at each step we only have to solve equations that depend on a finite subset of the original variables. The simplest case is when, at each step, we only need to solve equations depending on one single variable, but unfortunately this is not always posible. We also include here a geometric interpretation of Elimination theory, the Closure theorem, and its proof, being the main result in this subject. Finally, we give an application of Gr¨obner bases theory to Integer Lineal Programming. Our ultimate aim is to provide an algorithm whose input is a problem of Integer Lineal Programming, say in its standard form, and by using Gröbner basis, the algorithm returns, as an output, an optimal solution if it exists, or otherwise, the algorithm informs us that the problem has no solution.