Gröbner Bases and Integer Programming

Summary

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.