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

• 成果类型: Article
• 署名作者: Hemmecke, Raymond; Koeppe, Matthias; Weismantel, Robert
• 署名单位: Technical University of Munich; University of California System; University of California Davis; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0638-z
• 发表日期: 2014
• 页码: 1-18
• 关键词: test sets; optimization; DECOMPOSITION; PROGRAMS

摘要

We consider -fold -block decomposable integer programs, which simultaneously generalize -fold integer programs and two-stage stochastic integer programs with 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 , 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.