Name
Title | ||
|---|---|---|
Graver basis and proximity techniques for block-structured separable convex integer minimization problems |
Abstract | ||
|---|---|---|
We consider $$N$$ -fold $$4$$ -block decomposable integer programs, which simultaneously generalize $$N$$ -fold integer programs and two-stage stochastic integer programs with $$N$$ 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 $$N$$ , 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10107-013-0638-z | Mathematical Programming: Series A and B |
Keywords | Field | DocType |
proximity,graver basis,90c10,augmentation algorithm,$$n$$-fold integer programs,polynomial-time algorithm,90c15,stochastic integer programming,stochastic multi-commodity flow | Continuous optimization,Integer,Discrete mathematics,Mathematical optimization,Combinatorics,Graver basis,Separable space,Regular polygon,Combinatorial optimization,Integer points in convex polyhedra,Integer programming,Mathematics | Journal |
Volume | Issue | ISSN |
145 | 1-2 | 1436-4646 |
Citations | PageRank | References |
5 | 0.53 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raymond Hemmecke | 1 | 275 | 22.34 |
| Matthias KöPpe | 2 | 191 | 20.95 |
| Robert Weismantel | 3 | 964 | 90.05 |