Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleA geometric Buchberger algorithm for integer programming
Author(s) Rekha R. Thomas
TypeArticle in Journal
AbstractLet IP denote the family of integer programs of the form Min cx : Ax
= b, x in N^n obtained by varying the right hand side vector b but keeping A and c fixed. A test set for IP is a set of vectors in Z^n such that for each non-optimal solution ff to a program in this family, there is at least one element g in this set such that alpha - g has an improved cost value as compared to alpha. We describe a unique minimal test set for this family called the reduced Grobner basis of IP. An algorithm for its construction is presented which we call a Geometric Buchberger Algorithm for integer programming. We show how an integer program may be solved using this test set and examine some geometric properties of elements in the set. The reduced Grobner basis is then compared with some other known test sets from the literature. We also indicate an easy procedure to construct test sets with respect to all cost functions for a matrix A in Z^{(n - 2) times n} of full row rank.
Keywordsinteger programming, test sets, reduced Gröbner basis, Buchberger algorithm, fiber, Hilbert bases
JournalMathematics of Operations Research
Translation No
Refereed No