Year of Graduation
Toric Ideals and Groebner Bases in Integer Programming
Applied Mathematics and Information Science
The paper studies the applicability of toric ideal methods in linear integer programming. The review of toric ideals method in integer programming and related Groebner theory is presented. Optimization is processed via reduction of monomial-coded feasible solution to its normal form by elements of the Groebner basis of a toric ideal. Experimental estimates of computational complexity were built for solving knapsack problem, transportation problem and minimum vertex cover problem. It is shown that the execution time is very high, so the Buchberger algorithm is able to solve only limited class of problems of relatively small size. Despite that fact, the empirical study of complexity shows acceptable asymptotic results.