Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider -fold -block decomposable integer programs, which simultaneously generalize -fold integer programs and two-stage stochastic integer programs with scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843-862,1990), which allows us to use convex continuous optimization as a subroutine.