  


Graver basis and proximity techniques for blockstructured separable convex integer minimization problems
Raymond Hemmecke(hemmeckema.tum.de) Abstract: We consider Nfold 4block decomposable integer programs, which simultaneously generalize Nfold integer programs and twostage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomialtime algorithm for optimizing over Nfold 4block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219229], it was proved that for fixed blocks but variable N, these integer programs are polynomialtime 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), 843862], which allows us to use convex continuous optimization as a subroutine. Keywords: Nfold integer programs, Graver basis, augmentation algorithm, proximity, polynomialtime algorithm, stochastic multicommodity flow, stochastic integer programming Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Download: [PDF] Entry Submitted: 07/04/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  