Graver basis and proximity techniques for block-structured separable convex integer minimization problems
Skip to main content
eScholarship
Open Access Publications from the University of California

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

  • Author(s): Hemmecke, Raymond
  • Köppe, Matthias
  • Weismantel, Robert
  • et al.

Published Web Location

https://arxiv.org/pdf/1207.1149.pdf
No data is associated with this publication.
Abstract

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.

Item not freely available? Link broken?
Report a problem accessing this item