The quadratic Graver cone, quadratic integer minimization, and extensions (Q1925790): Difference between revisions

The paper addresses quadratic integer programming problems. The authors first observe that it is NP-hard to determine the optimal value of a quadratic integer programme \[ \min \{x^TVx + w^Tx + a: x \in \mathbb{Z}^n, ~Ax =b,~ l \leq x \leq u\} \] even if the Graver basis of \(A\) is given and even if the objective function is convex and \(V= vv^T\). They use this as a motivtaion to study special cases of quadratic functions for which this problem can be solved in polynomial time. Their main results show that this is the case for matrices \(V\) lying in the dual quadratic Graver cone (defined in the paper). As a special case, the result also holds for separable quadratic programming with the objective \(\sum_{i=1}^n (v_ix_i^2 + w_ix_i +a_i)\), where \(v\) belongs to the dual diagonal Graver cone. The results are extended later to show that for more general polynomials. It is shown that for every fixed \(d\) there is an algorithm that, given the Graver basis, solves \[ \min\{f(x): x \in \mathbb{Z}^n, ~Ax=b,~ x \geq 0\} \] in polynomial time for every degree \(d\) integer homogeneous polynomial \(f\) in a cone of certain tensors defined by \(A\).