Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A Markov basis of a lattice is a set of integer vectors such that it is possible to move between any two integer points in a polyhedron while staying within the polyhedron by adding or subtracting vectors in the Markov basis. A Markov basis has three main applications: sampling from a set of feasible solutions computing Groebner bases of integer programs. Sampling from a set of feasible solutions is used in algebraic statistics to determine whether a set of observed events follow a given frequency distribution. We present an algorithm for computing Markov basis. This algorithm can also solve the feasibility problem of finding an integer point in a polyhedron.

A Groebner basis of a lattice is a set of vectors such that we can improve any given non-optimal feasible solution of an integer programming by subtracting a vector in the Groebner basis. So, using a Groebner basis, we can solve an integer program by iteratively improving a given initial feasible solution. We present and discuss different Groebner basis approaches to solve integer programs.