Gröbner Bases and Integer Programming
Serkan Hoşten, Rekha R. Thomas · Cambridge University Press eBooks · 1998
Introduction This 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 basis 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 polytope are precisely the elements in the universal Gröbner 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 .