Truncated Gröbner bases for integer programming (Q1361003): Difference between revisions

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.