Convex integer maximization via Graver bases

We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where c is a convex function on R^d and w₁ x, ..., w_d x are linear forms on Rⁿ, max {c (w₁ x, ..., w_d x) : A x = b, x ∈ Nⁿ} . This method works for arbitrary input data A, b, d, w₁, ..., w_d, c. Moreover, for fixed d and several important classes of programs in variable dimension, we prove that our algorithm runs in polynomial time. As a consequence, we obtain polynomial time algorithms for various types of multi-way transportation problems, packing problems, and partitioning problems in variable dimension.