Computing Markov bases, Gröbner bases, and extreme rays

In this thesis, we address problems from two topics of applied mathematics: linear integer programming and polyhedral computation. Linear integer programming concerns solving optimisation problems to maximise a linear cost function over the set of integer points in a polyhedron. Polyhedral computation is concerned with algorithms for computing different properties of convex polyhedra. First, we explore the theory and computation of Gröbner bases and Markov bases for linear integer programming. Second, we investigate and improve an algorithm from polyhedral computation that converts between different representations of cones and polyhedra. A Markov basis is a set of integer vectors such that we can move between any two feasible solutions of an integer program by adding or subtracting vectors in the Markov basis while never moving outside the set of feasible solutions. Markov bases are mainly used in algebraic statistics for sampling from a set of feasible solutions. The major contribution of this thesis is a fast algorithm for computing Markov bases, which we used to solve a previously intractable computational challenge. Gröbner basis methods are exact local search approaches for solving integer programs. We present a Gröbner basis approach that can use the structure of an integer program in order to solve it more efficiently. Gröbner basis methods are interesting mainly from a purely theoretical viewpoint, but they are also interesting because they may provide insight into why some classes of integer programs are difficult to solve using standard techniques and because someday they may be able to solve these difficult problems. Computing the properties of convex polyhedra is useful for solving problems within different areas of mathematics such as linear programming, integer programming, combinatorial optimisation, and computational geometry. We investigate and improve an algorithm for converting between a generator representation of a cone or polyhedron and a constraint representation of the cone or polyhedron and vice versa. This algorithm can be extended to compute circuits of matrices, which are used in computational biology for metabolic pathway analysis.