Graver basis and proximity techniques for block-structured separable convex integer minimization problems
Preprint
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.Keywords
All Related Versions
- Version 1, 2012-07-05, ArXiv
- Published version: Mathematical Programming, 145 (1-2), 1.
This publication has 11 references indexed in Scilit:
- n-Fold integer programming in cubic timeMathematical Programming, 2011
- Convex integer maximization via Graver basesJournal of Pure and Applied Algebra, 2009
- A polynomial oracle-time algorithm for convex integer minimizationMathematical Programming, 2009
- A note on second-order stochastic dominance constraints induced by mixed-integer linear recourseMathematical Programming, 2009
- On the positive sum property and the computation of Graver test setsMathematical Programming, 2003
- Decomposition of test sets in stochastic integer programmingMathematical Programming, 2003
- Convex separable optimization is not much harder than linear optimizationJournal of the ACM, 1990
- The stochastic multicommodity flow problemNetworks, 1990
- Solving integer minimum cost flows with separable convex cost objective polynomially1986
- Decomposition of regular matroidsJournal of Combinatorial Theory, Series B, 1980