×

Graver basis and proximity techniques for block-structured separable convex integer minimization problems. (English) Zbl 1298.90057

Summary: 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 [R. Hemmecke et al., Lecture Notes in Computer Science 6080, 219–229 (2010; Zbl 1285.90022)], 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 [D. S. Hochbaum and J. G. Shanthikumar, J. Assoc. Comput. Mach. 37, No. 4, 843–862 (1990; Zbl 0721.90060)], which allows us to use convex continuous optimization as a subroutine.

MSC:

90C10 Integer programming
90C15 Stochastic programming

Software:

DDSIP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] De Loera, J.A., Hemmecke, R., Onn, S., Rothblum, U.G., Weismantel, R.: Convex integer maximization via Graver bases. J. Pure Appl. Algebra 213, 1569-1577 (2009) · Zbl 1284.05026 · doi:10.1016/j.jpaa.2008.11.033
[2] De Loera, J.A., Hemmecke, R., Onn, S., Weismantel, R.: \(N\)-fold integer programming. Discret. Optim. 5(2), 231-241 (2008) doi:10.1016/j.disopt.2006.06.006 (In Memory of George B. Dantzig) · Zbl 1151.90025
[3] Diaconis, P., Graham, R. L., Sturmfels, B.: Primitive partition identities. In: Miklós, D., Sós, V.T., Szőnyi, D. (eds.), Combinatorics, Paul Erdős is Eighty, Volume 2. Bolyai Society Mathematical Studies, vol. 2, pp. 173-192 (1996) · Zbl 0852.05014
[4] Gollmer, R., Gotzes, U., Schultz, R.: A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse. Math. Program. 126, 179-190 (2011) · Zbl 1229.90109 · doi:10.1007/s10107-009-0270-0
[5] Graver, J.E.: On the foundations of linear and integer linear programming I. Math. Program. 8, 207-226 (1975) · Zbl 0323.90035 · doi:10.1007/BF01681344
[6] Hemmecke, R.: Test sets for integer programs with \(\mathbb{Z} \)-convex objective. eprint arXiv:math/0309154 (2003) · Zbl 0689.90031
[7] Hemmecke, R.: On the positive sum property and the computation of Graver test sets. Math. Program. Ser. B 96, 247-269 (2003) · Zbl 1059.90108 · doi:10.1007/s10107-003-0385-7
[8] Hemmecke, R., Köppe, M., Weismantel, R.: A polynomial-time algorithm for optimizing over \[N\]-fold 4-block decomposable integer programs, In: Eisenbrand, F., Shepherd, F.B. (eds.), Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 6080, Springer, Berlin, pp. 219-229 (2010). doi:10.1007/978-3-642-13036-6_17 · Zbl 1285.90022
[9] Hemmecke, R., Onn, S., Romanchuk, L.: \(N\)-fold integer programming in cubic time. Math. Program. 1-17 (2011). doi:10.1007/s10107-011-0490-y · Zbl 1262.90104
[10] Hemmecke, R., Onn, S., Weismantel, R.: A polynomial oracle-time algorithm for convex integer minimization. Math. Program. 126, 97-117 (2011). doi:10.1007/s10107-009-0276-7 · Zbl 1228.90055
[11] Hemmecke, R., Schultz, R.: Decomposition of test sets in stochastic integer programming. Math. Program. 94(2-3), 323-341 (2003) · Zbl 1030.90073 · doi:10.1007/s10107-002-0322-1
[12] Hochbaum, D.S.: Lower and upper bounds for allocation problems. Math. Oper. Res. 19, 390-409 (1994) · Zbl 0820.90082 · doi:10.1287/moor.19.2.390
[13] Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder than linear optimization, J. ACM 37, 843-862 (1990). doi:10.1145/96559.96597 · Zbl 0721.90060
[14] Minoux, M.: Solving integer minimum cost flows with separable convex cost objective polynomially. Math. Prog. Study 26, 237-239 (1986) · Zbl 0588.90027 · doi:10.1007/BFb0121104
[15] Mirchandani, P., Soroush, H.: The stochastic multicommodity flow problem. Networks 20, 121-155 (1990) · Zbl 0689.90031
[16] Murota, K., Saito, H., Weismantel, R.: Optimality criterion for a class of nonlinear integer programs. Oper. Res. Lett. 32, 468-472 (2004) · Zbl 1054.90049 · doi:10.1016/j.orl.2003.11.007
[17] Onn, S.: Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society (2010) · Zbl 1219.90003
[18] Onn, S.: Theory and applications of \(N\)-fold integer programming. In: The IMA Volumes in Mathematics and its Applications, Mixed Integer Nonlinear Programming, pp. 559-593. Springer, Berlin (2012) · Zbl 1242.90113
[19] Onn, S., Rothblum, U.G.: Convex combinatorial optimization. Disc. Comp. Geom. 32, 549-566 (2004) · Zbl 1179.90289 · doi:10.1007/s00454-004-1138-y
[20] Powell, W., Topaloglu, H.: Dynamic-programming approximations for stochastic time-staged integer multicommodity-flow problems. INFORMS J. Comput. 18, 31-42 (2006) · Zbl 1241.90172 · doi:10.1287/ijoc.1040.0079
[21] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986) · Zbl 0665.90063
[22] Schulz, A.S., Weismantel, R.: An oracle-polynomial time augmentation algorithm for integer programming. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 967-968 (1999) · Zbl 1052.90589
[23] Schulz, A.S., Weismantel, R., Ziegler, G.M.: 0/1 integer programming: optimization and augmentation are equivalent. In: Spirakis, P. (ed.), Algorithms-ESA 95, Lecture Notes in Computer Science, vol. 979, Springer, Berlin, pp. 473-483 (1995) · Zbl 1512.90140
[24] Seymour, P.D.: Decomposition of regular matroids. J. Comb. Theory 28, 305-359 (1980) · Zbl 0443.05027 · doi:10.1016/0095-8956(80)90075-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.