Truncated Gröbner bases for integer programming
type: Item
instance of: scholarly article
title: Truncated Gröbner bases for integer programming
zbMATH Open document ID: 0914.90203
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1999-06-01T00:00:00Z
review text: Considered is an integer program of the form: minimize \(\{cx\mid Ax=b\), \(x\in {\mathbb{N}}^n\}\), denoted by \(IP_{A,b,c,=}\), where \(A:=(a_1,\dots,a_n)\in {\mathbb{Z}}^{ d\times n}\) is an integer matrix of full rank, \(b\) is an element of \({\mathbb{Z}}^d\) and \(c\) is a vector in \({\mathbb{R}}^n\) (called cost vector). \textit{P. Conti} and \textit{C. Traverso} [in: Applied algebra, algebraic algorithms and error-correcting codes, Proc. 9th Int. Symp., AAECC-9, Lect. Notes Comput. Sci. 539, 130-139 (1991; Zbl 0771.13014)] developed an algorithm for integer programming based on Gröbner bases techniques: Indeed, if \(I_A\) is the toric ideal given by the kernel of the map \(\pi_A:k[x_1,\dots,x_n]\longrightarrow k[t_1^{\pm 1},\dots, t_d^{\pm 1}]\) given by \(\pi_A(x_i):=t^{a_i}\), then the equation \(Ax=b\) can be converted into the membership and representation problems \(t^b \in I_A\), which are solved with Gröbner bases techniques. The authors give an algorithm for solving the integer program \(IP_{A,b,c,=}\) for a fixed \(b\). They observe that in this case the computation of the whole Gröbner basis of \(I_A\) is unnecessary since it contains many polynomials which are not involved in the representation of \(t^b\). Therefore they introduce a suitable multivariate grading on the ring of polynomials \(k[x_1,\dots,x_n]\) induced by the matrix \(A\) in such a way that the ideal \(I_A\) becomes homogeneous and they develop a suitable theory of truncated Gröbner bases which allows to stop the computations as soon as the multidegree of \(t^b\) is reached. 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\). Some examples complete the exposition.
reviewed by: Alessandro Logar
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 13P10
zbMATH DE Number: 1038371
zbMATH Keywords: integer programming
zbMATH Keywords: toric ideal
zbMATH Keywords: truncated Gröbner bases
zbMATH Keywords: truncated Buchberger algorithm
zbMATH Keywords: multivariate grading
author: Rekha Thomas
author: Robert Weismantel
describes a project that uses: GRIN
MaRDI profile type: Publication
full work available at URL: s002000050062
OpenAlex ID: W2135307914
Wikidata QID: Q114852529
DOI: 10.1007/S002000050062
description: scientific article; zbMATH DE number 1038371