Initial ideals of unimodular integer programs

Abstract

This article concerns the initial ideal computation for toric ideals, which arises in the computational algebraic approach for integer programs. It is known that the initial ideals of toric ideals contain many information about original toric ideals that are beneficial for solving the integer programs. Therefore, their analyses may bring further comprehensions for structure of integer programs and can help us to construct a new type of algorithm. There are two known algorithms for initial ideal computation. One is based on the theory of Gröbner bases and the other is proposed by Thomas and Hos¸ten. In this article, we propose another type of algorithm to perform the initial ideal computation for the toric ideals defined by unimodular matrices. The unimodular matrices is one of the important matrix classes, that are often looming as the coefficient matrices of some combinatorial optimization problems with the forms of integer programs. Ours are based on a combinatorial relation between the vector matroids of defining matrices and the minimal generators of initial ideals.

Keywords:

• Unimodular integer program
• Toric ideal
• Gröbner basis
• Standard-pair decomposition
• Primary decomposition
• Vector matroid