A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs

DOI10.1007/978-3-642-13036-6_17MaRDI QIDQ3569820zbMATH OpenOpenAlexFDO

Authors Raymond Hemmecke, Matthias Köppe, Robert Weismantel

Publication date 22 June 2010

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.4055

zbMATH Keywords

Graver basispolynomial-time algorithmstochastic integer programmingaugmentation algorithm\(N\)-fold integer programsstochastic multi-commodity flow

Mathematics Subject Classification ID

Stochastic programming (90C15) Integer programming (90C10)

Abstract: In this paper we generalize N-fold integer programs and two-stage integer programs with N scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

Recommendations

• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• \(n\)-fold integer programming in cubic time
• \(N\)-fold integer programming
• Theory and Applications of n-Fold Integer Programming
• Faster Algorithms for Integer Programs with Block Structure

Cited in

(13)

• Huge multiway table problems
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• \(N\)-fold integer programming
• The double exponential runtime is tight for 2-stage stochastic ILPs
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• FPT algorithms for a special block-structured integer program with applications in scheduling
• Subset selection in sparse matrices
• The double exponential runtime is tight for 2-stage stochastic ILPs
• Convex integer optimization by constantly many linear counterparts
• Huge unimodular \(n\)-fold programs
• Block-structured integer programming: can we parameterize without the largest coefficient?
• \(n\)-fold integer programming in cubic time
• A colorful Steinitz lemma with application to block-structured integer programs

This page was built for publication: A polynomial-time algorithm for optimizing over \(N\)-fold 4-block decomposable integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569820)