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


TitleGröbner Bases and Integer Programming
Author(s) Serkan Hosten, Rekha R. Thomas
TypeTechnical Report, Misc
AbstractThis article is a brief survey of recent work on Gröbner bases
(Buchberger 1965) of toric ideals and their role in integer programming. Toric varieties and ideals are crucial players in the interaction between combinatorics, discrete geometry, commutative algebra and algebraic geometry. For a detailed treatment of this topic see (Sturmfels 1995). Our survey focuses on the application of toric ideals to integer programming, a specific branch of discrete optimization, and for the sake of brevity we leave details to the references that are included. We study a family of integer programs associated with a fixed matrix A and the corresponding toric ideal I_A . In Section 2, we show that reduced Gröbner bases of I_A are test sets for these integer programs. In Section 3, we define the universal Gröbner bases of I_A and we identify it as a subset of the Graver basis of A. Section 4 deals with the effect of varying the cost function while keeping the matrix A fixed; there we give a self contained construction of the state polytope and Gröbner fan of I_A. Moreover, we show that the edge directions of the state polytype are precisely the elements in the universal Gröner basis of I_A. We conclude in Section 5 with a discussion of practical issues that arise while computing Gröbner bases of toric ideals. In particular we discuss algorithms for finding generating sets for I_A.
Translation No
Refereed No