ISSN:
1432-0622
Keywords:
Keywords: Integer programming
;
Toric ideal
;
Truncated Gröbner bases
;
Truncated Buchberger algorithm
;
Multivariate grading.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract. The toric ideal I A of a matrix A=(a 1, . . . , a n )∈ℤd × n is the kernel of the monoid algebra map π^ A : k[x 1, . . . , x n ]→k[t ±1 1, . . . , t ±1 d ], defined as x j ?t aj . It was shown in [4] that the reduced Gröbner basis of I A , with respect to the weight vector c, can be used to solve all integer programs minimize {cx : Ax=b, x∈ℕ n }, denoted IP A,b,c,= , as b varies. In this paper we describe the construction of a truncated Gröbner basis of I A with respect to c, that solves IP A,b,c,= for a fixed b. This is achieved by establishing the homogeneity of I A with respect to a multivariate grading induced by A. Depending on b, the truncated Gröbner basis may be considerably smaller than the entire Gröbner basis of I A with respect to c. For programs of the form maximize{cx : Ax≦b, x≦u, x∈ℕ n } in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in [17].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002000050062
Permalink