  We consider N-fold 4-block decomposable integer programs, which
simultaneously generalize N-fold integer programs and two-stage stochastic
integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R.
Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block
decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer
Science, vol. 6080, Springer, 2010, pp. 219--229], it was proved that for fixed
blocks but variable N, 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 [D.S. Hochbaum and J.G. Shanthikumar, Convex separable
optimization is not much harder than linear optimization, J. ACM 37 (1990),
843--862], which allows us to use convex continuous optimization as a
subroutine.
