TY - GEN
T1 - A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs
AU - Hemmecke, Raymond
AU - Köppe, Matthias
AU - Weismantel, Robert
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - Graver basis
KW - N-fold integer programs
KW - augmentation algorithm
KW - polynomial-time algorithm
KW - stochastic integer programming
KW - stochastic multi-commodity flow
UR - http://www.scopus.com/inward/record.url?scp=77954392662&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-13036-6_17
DO - 10.1007/978-3-642-13036-6_17
M3 - Conference contribution
AN - SCOPUS:77954392662
SN - 3642130356
SN - 9783642130359
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 219
EP - 229
BT - Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings
T2 - 14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010
Y2 - 9 June 2010 through 11 June 2010
ER -