Computer Algebra and Combinatorics: Results and Algorithms for Combinatorial Optimization

This talk will be a survey of recent results and algorithms originating in the theory of Gröbner bases and initial ideals of toric ideals. Toric ideals form the link between commutative algebra and integer programming. Monomial initial ideals of toric ideals provide rich combinatorial information which translates into structural results about the associated integer programs. For instance, Cohen-Macaulay initial ideals correspond to a certain class of easy-to-solve programs. Normal toric ideals and their initial ideals are the places to look for such easy programs which do not appear in the classical combinatorial optimization literature. Conversely, the algorithmic tools needed to sift through the vast number of initial ideals of a given toric ideal come from discrete geometry and combinatorics. I will exhibit the state of the art of these algorithms and the amazingly large computations it can handle.

Serkan Hosten