TY - JOUR

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

AU - Hemmecke, Raymond

AU - Köppe, Matthias

AU - Weismantel, Robert

PY - 2014/6

Y1 - 2014/6

N2 - 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 (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), 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 (Hochbaum and Shanthikumar in J. ACM 37:843-862,1990), which allows us to use convex continuous optimization as a subroutine.

AB - 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 (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), 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 (Hochbaum and Shanthikumar in J. ACM 37:843-862,1990), which allows us to use convex continuous optimization as a subroutine.

KW - Augmentation algorithm

KW - Graver basis

KW - N-fold integer programs

KW - Polynomial-time algorithm

KW - Proximity

KW - Stochastic integer programming

KW - Stochastic multi-commodity flow

UR - http://www.scopus.com/inward/record.url?scp=84901837975&partnerID=8YFLogxK

U2 - 10.1007/s10107-013-0638-z

DO - 10.1007/s10107-013-0638-z

M3 - Article

AN - SCOPUS:84901837975

SN - 0025-5610

VL - 145

SP - 1

EP - 18

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -