Convex integer maximization via Graver bases

We present a new algebraic algorithmic scheme to solve convex integer maximization   problems of the following form, where cc is a convex function on RdRd and w1x,…,wdxw1x,…,wdx are linear forms on RnRn, max{c(w1x,…,wdx):Ax=b,x∈Nn}.max{c(w1x,…,wdx):Ax=b,x∈Nn}. This method works for arbitrary input data A,b,d,w1,…,wd,cA,b,d,w1,…,wd,c. Moreover, for fixed dd 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.