Paper Info
Title
A polynomial-time algorithm for optimizing over N-flod 4-block decomposable integer programs
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.
Year
DOI
Venue
2010
10.1007/978-3-642-13036-6_17
IPCO
Keywords
Field
DocType
n-flod 4-block decomposable integer,4-block decomposable integer program,n scenario,variable n,fixed block,convex separable objective function,integer program,stochastic integer program,n-fold integer program,polynomial-time algorithm,stochastic integer multi-commodity flow,two-stage integer program,objective function,polynomial time,second order
Integer programming,Trial division,Integer sequence,Discrete mathematics,Mathematical optimization,Combinatorics,Graver basis,Branch and cut,Algorithm,Integer points in convex polyhedra,Prime factor,Radical of an integer,Mathematics
Conference
Volume
ISSN
ISBN
6080
0302-9743
3-642-13035-6
Citations 
PageRank 
References 
4
0.48
15
Authors
3
Name
Order
Citations
PageRank
Raymond Hemmecke127522.34
Matthias KöPpe219120.95
Robert Weismantel396490.05