Initial deals of unimodular integer programs

Initial deals of unimodular integer programs

0.00 Avg rating0 Votes
Article ID: iaor20061827
Country: United Kingdom
Volume: 82
Issue: 12
Start Page Number: 1429
End Page Number: 1445
Publication Date: Dec 2005
Journal: International Journal of Computer Mathematics
Authors: ,
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 Hosten. 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.

Reviews

Required fields are marked *. Your email address will not be published.