M.Sc Student | Romanchuk Lyubov |
---|---|

Subject | Graver Bases Methods in Integer Programming |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Shmuel Onn |

Full Thesis text |

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.