Lyubov Romanchuk

In a recent series of papers, De Loera, Hemmecke, Onn, Rothblum and Weismantel have shown that Graver bases can be used to solve broad classes of linear and nonlinear integer programming problems in variable dimension in polynomial time.

We describe two continuations of this line of investigation. First, we show that Graver bases also enable polynomial time integer minimization of quadratic functions lying in a certain cone of matrices. This cone is incomparable with the cone of positive semidefinite matrices and we can minimize some nonconvex and some (including all separable) convex quadratics.

Second, we use Graver bases methods to establish an iterative algorithm that solves the n-fold integer programming problem drastically faster, in cubic time. We extend our results to programs with nonlinear objective functions and provide an optimality certification procedure for separable convex objectives, and an algorithm for solving problems with separable convex piecewise affine objectives. We propose a simple Graver approximation hierarchy, parameterized by degree, for nonlinear integer programming over n-fold systems in general and multiway tables in particular, which makes use of quickly constructible approximations of the true Graver basis.

Furthermore, we provide an implementation of the algorithm and approximation hierarchy for the case of linear objective functions.