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 -