Optimization Online


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

Raymond Hemmecke(hemmecke***at***ma.tum.de)
Matthias Köppe(mkoeppe***at***math.ucdavis.edu)
Robert Weismantel(robert.weismantel***at***ifor.math.ethz.ch)

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: N-fold integer programs, Graver basis, augmentation algorithm, proximity, polynomial-time algorithm, stochastic multi-commodity flow, stochastic integer programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 07/04/2012
Entry Accepted: 07/05/2012
Entry Last Modified: 07/04/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society