×

zbMATH — the first resource for mathematics

Submodularity in conic quadratic mixed 0-1 optimization. (English) Zbl 1456.90106
Summary: We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and are based on the polymatroid inequalities over binaries for the diagonal case. We prove that the convex inequalities completely describe the convex hull of a single conic quadratic constraint as well as the rotated cone constraint over binary variables and unbounded continuous variables. We then generalize and strengthen the inequalities by incorporating additional constraints of the optimization problem. Computational experiments on mean-risk optimization with correlations, assortment optimization, and robust conic quadratic optimization indicate that the new inequalities strengthen the convex relaxations substantially and lead to significant performance improvements.
MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
90C17 Robustness in mathematical programming
Software:
QPsimplex
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1-2):149-169.Crossref, Google Scholar · Zbl 1218.90221
[2] Aktürk MS, Atamtürk A, Gürel S (2009) A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37(3):187-191.Crossref, Google Scholar · Zbl 1167.90518
[3] Aktürk MS, Atamtürk A, Gürel S (2010) Parallel machine match-up scheduling with manufacturing cost considerations. J. Scheduling 13(1):95-110.Crossref, Google Scholar · Zbl 1185.90064
[4] Amaldi E, Bosio S, Malucelli F, Yuan D (2011) Solving nonlinear covering problems arising in wlan design. Oper. Res. 59(1):173-187.Link, Google Scholar · Zbl 1218.90117
[5] Amiri A (1997) Solution procedures for the service system design problem. Comput. Oper. Res. 24(1):49-60.Crossref, Google Scholar · Zbl 0881.90087
[6] Anstreicher KM (2012) On convex relaxations for quadratically constrained quadratic programming. Math. Programming 136(2):233-251.Crossref, Google Scholar · Zbl 1267.90103
[7] Atamtürk A, Bhardwaj A (2015) Supermodular covering knapsack polytope. Discrete Optim. 18:74-86.Crossref, Google Scholar · Zbl 1387.90127
[8] Atamtürk A, Gómez A (2017) Maximizing a class of utility functions over the vertices of a polytope. Oper. Res. 65(2):433-445.Link, Google Scholar · Zbl 1366.90173
[9] Atamtürk A, Gómez A (2018) Strong formulations for quadratic optimization with M-matrices and indicator variables. Math. Programming 170(1):141-176.Crossref, Google Scholar · Zbl 1391.90423
[10] Atamtürk A, Gómez A (2019a) Rank-one convexification for sparse regression. Preprint, submitted January 29, https://arxiv.org/abs/1901.10334.Google Scholar
[11] Atamtürk A, Gómez A (2019b) Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra. Math. Programming Comput. 11(2):311-340.Crossref, Google Scholar · Zbl 1435.90097
[12] Atamtürk A, Jeon H (2017) Lifted polymatroid inequalities for mean-risk optimization with indicator variables. J. Global Optim. 73(4):677-699.Crossref, Google Scholar · Zbl 1422.90024
[13] Atamtürk A, Narayanan V (2007) Cuts for conic mixed-integer programming. Fischetti M, Williamson DP, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin, Heidelberg), 16-29.Crossref, Google Scholar · Zbl 1136.90518
[14] Atamtürk A, Narayanan V (2008) Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5):618-622.Crossref, Google Scholar · Zbl 1210.90127
[15] Atamtürk A, Narayanan V (2009) The submodular knapsack polytope. Discrete Optim. 6(4):333-344.Crossref, Google Scholar · Zbl 1179.90270
[16] Atamtürk A, Narayanan V (2010) Conic mixed-integer rounding cuts. Math. Programming 122(1):1-20.Crossref, Google Scholar · Zbl 1184.90112
[17] Atamtürk A, Narayanan V (2011) Lifting for conic mixed-integer programming. Math. Programming 126(2):351-363.Crossref, Google Scholar · Zbl 1206.90102
[18] Atamtürk A, Berenguer G, Shen Z-J (2012) A conic integer programming approach to stochastic joint location-inventory problems. Oper. Res. 60(2):366-381.Link, Google Scholar · Zbl 1248.90057
[19] Atamtürk A, Deck C, Jeon H (2019) Successive quadratic upper-bounding for discrete mean-risk minimization and network interdiction. INFORMS J. Comput., ePub ahead of print, October 19, https://doi.org/10.1287/ijoc.2018.0870.Google Scholar
[20] Atamtürk A, Gómez A, Han S (2018) Sparse and smooth signal estimation: Convexification of l0 formulations. BCOL Research Report 18.05, IEOR, University of California, Berkeley, Berkeley.Google Scholar
[21] Belotti P, Góez JC, Pólik I, Ralphs TK, Terlaky T (2015) A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. Al-Baali M, Grandinetti L, Purnama A, eds. Numerical Analysis and Optimization, Springer Proceedings in Mathematics and Statistics, vol. 134 (Springer, Cham, Switzerland), 1-35.Crossref, Google Scholar · Zbl 1330.65083
[22] Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769-805.Link, Google Scholar · Zbl 0977.90052
[23] Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1):1-13.Crossref, Google Scholar · Zbl 0941.90053
[24] Ben-Tal A, Nemirovski A (2001) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193-205.Link, Google Scholar · Zbl 1082.90133
[25] Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization, Princeton Series in Applied Mathematics. (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
[26] Berman O, Krass D (2001) Facility location problems with stochastic demands and congestion. Drezner Z, Hamacher HW, eds. Facility Location Applications and Theory (Springer, Berlin), 329-372.Google Scholar · Zbl 1061.90068
[27] Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1-3):49-71.Crossref, Google Scholar · Zbl 1082.90067
[28] Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35-53.Link, Google Scholar · Zbl 1165.90565
[29] Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar · Zbl 1223.90001
[30] Bollapragada R, Rao U (1999) Single-stage resource allocation and economic lot scheduling on multiple, nonidentical production lines. Management Sci. 45(6):889-904.Link, Google Scholar · Zbl 1231.90156
[31] Bonami P (2011) Lift-and-project cuts for mixed integer convex programs. Günlük O, Woeginger GJ, eds. Integer Programming and Combinatoral Optimization—IPCO 2011, Lecture Notes in Computer Science, vol. 6655 (Springer, Berlin, Heidelberg), 52-64.Google Scholar · Zbl 1339.90243
[32] Borrero JS, Gillen C, Prokopyev OA (2016a) Fractional 0-1 programming: Applications and algorithms. J. Global Optim. 69(1):1-28.Google Scholar
[33] Borrero JS, Gillen C, Prokopyev OA (2016b) A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems. Oper. Res. Lett. 44(4):479-486.Crossref, Google Scholar · Zbl 1380.90261
[34] Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769-784.Link, Google Scholar · Zbl 1233.90061
[35] Buchheim C, De Santis M (2019) An active set algorithm for robust combinatorial optimization based on separation oracles. Math. Programming Comput. Forthcoming.Crossref, Google Scholar · Zbl 07168040
[36] Bulut O, Tasgetiren MF (2014) An artificial bee colony algorithm for the economic lot scheduling problem. Internat. J. Production Res. 52(4):1150-1170.Crossref, Google Scholar
[37] Burer S, Kılınç-Karzan F (2017) How to convexify the intersection of a second order cone and a nonconvex quadratic. Math. Programming 162(1-2):393-429.Crossref, Google Scholar · Zbl 1358.90095
[38] Castro PM, Barbosa-Póvoa AP, Novais AQ (2005) Simultaneous design and scheduling of multipurpose plants using resource task network based continuous-time formulations. Indust. Engrg. Chemical Res. 44(2):343-357.Crossref, Google Scholar
[39] Castro PM, Westerlund J, Forssell S (2009) Scheduling of a continuous plant with recycling of byproducts: A case study from a tissue paper mill. Comput. Chemical Engrg. 33(1):347-358.Crossref, Google Scholar
[40] Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math. Programming 86(3):595-614.Crossref, Google Scholar · Zbl 0954.90049
[41] Çezik MT, Iyengar G (2005) Cuts for mixed 0-1 conic programming. Math. Programming 104(1):179-202.Crossref, Google Scholar · Zbl 1159.90457
[42] Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184-197.Link, Google Scholar · Zbl 0987.90516
[43] Dadush D, Dey SS, Vielma JP (2011a) The Chvátal-Gomory closure of a strictly convex body. Math. Oper. Res. 36(2):227-239.Link, Google Scholar
[44] Dadush D, Dey SS, Vielma JP (2011b) The split closure of a strictly convex body. Oper. Res. Lett. 39(2):121-126.Crossref, Google Scholar · Zbl 1225.90085
[45] Dadush D, Dey S, Vielma JP (2014) On the Chvátal-Gomory closure of a compact convex set. Math. Programming 145(1-2):327-348.Google Scholar · Zbl 1298.90056
[46] Davidoff G, Sarnak P, Valette A (2003) Elementary Number Theory, Group Theory and Ramanujan Graphs, London Mathematical Society Student Texts, vol. 55 (Cambridge University Press, Cambridge, UK).Google Scholar
[47] Désir A, Goyal V, Zhang J (2014) Near-optimal algorithms for capacity constrained assortment optimization. Working paper, Columbia University, New York.Google Scholar
[48] Dong H, Chen K, Linderoth J (2015) Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. Preprint, submitted October 20, https://arxiv.org/abs/1510.06083.Google Scholar
[49] Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy R, Hanani H, Sauer N, Schönenheim J, eds. Combinatorial Structures and Their Applications (Gordon and Breach, New York), 69-87.Google Scholar · Zbl 0268.05019
[50] El Ghaoui L, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4):543-556.Link, Google Scholar · Zbl 1165.91397
[51] Elhedhli S (2005) Exact solution of a class of nonlinear knapsack problems. Oper. Res. Lett. 33(6):615-624.Crossref, Google Scholar · Zbl 1141.90510
[52] Elhedhli S (2006) Service system design with immobile servers, stochastic demand, and congestion. Manufacturing Service Oper. Management 8(1):92-97.Link, Google Scholar
[53] Frangioni A, Claudio G, James H (2020) Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Math. Oper. Res. 45(1):15-33.Google Scholar · Zbl 1437.90110
[54] Fujishige S (2005) Submodular Functions and Optimization, vol. 58 (Elsevier, Amsterdam).Google Scholar
[55] Gilmore PC, Gomory RE (1963) A linear programming approach to the cutting stock problem—part II. Oper. Res. 11(6):863-888.Link, Google Scholar · Zbl 0124.36307
[56] Gómez A (2018) Strong formulations for conic quadratic optimization with indicator variables. Optim. Online (May 9), http://www.optimization-online.org/DB_HTML/2018/05/6616.html.Google Scholar
[57] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169-197.Crossref, Google Scholar · Zbl 0492.90056
[58] Günlük O, Linderoth J (2010) Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Programming 124(1-2):183-205.Crossref, Google Scholar · Zbl 1229.90106
[59] Hijazi H, Bonami P, Ouorou A (2013) An outer-inner approximation for separable mixed-integer nonlinear programs. INFORMS J. Comput. 26(1):31-44.Link, Google Scholar · Zbl 1356.90091
[60] Hochbaum DS (2010) Polynomial time algorithms for ratio regions and a variant of normalized cut. IEEE Trans. Pattern Anal. Machine Intelligence 32(5):889-898.Crossref, Google Scholar
[61] Hochbaum DS, Lyu C, Bertelli E (2013) Evaluating performance of image segmentation criteria and techniques. EURO J. Comput. Optim. 1(1-2):155-180.Crossref, Google Scholar · Zbl 1307.90006
[62] Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97-111.Crossref, Google Scholar · Zbl 1027.90106
[63] Jeon H, Linderoth J, Miller A (2017) Quadratic cone cutting surfaces for quadratic programs with on-off constraints. Discrete Optim. 24:32-50.Crossref, Google Scholar · Zbl 1387.90174
[64] Kılınç M, Linderoth J, Luedtke J (2010) Effective separation of disjunctive cuts for convex mixed integer nonlinear programs. Optim. Online (August 21), http://www.optimization-online.org/DB_FILE/2010/11/2808.pdf.Google Scholar
[65] Kılınç-Karzan F (2015) On minimal valid inequalities for mixed integer conic programs. Math. Oper. Res. 41(2):477-510.Link, Google Scholar · Zbl 1338.90275
[66] Kılınç-Karzan F, Yıldız S (2015) Two-term disjunctions on the second-order cone. Math. Programming 154(1-2):463-491.Crossref, Google Scholar · Zbl 1327.90137
[67] Lim C, Smith JC (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15-26.Crossref, Google Scholar
[68] Lovász L (1983) Submodular functions and convexity. Bachem A, Korte B, Grötschel M, eds. Mathematical Programming The State of the Art: Bonn 1982 (Springer, Berlin, Heidelberg), 235-257.Crossref, Google Scholar
[69] Lubin M, Yamangil E, Bent R, Vielma JP (2018) Polyhedral approximation in mixed-integer convex optimization. Math. Programming 172(1-2):139-168.Google Scholar · Zbl 1401.90158
[70] Méndez-Díaz I, Miranda-Bront JJ, Vulcano G, Zabala P (2014) A branch-and-cut algorithm for the latent-class logit assortment problem. Discrete Appl. Math. 164(1):246-263.Crossref, Google Scholar · Zbl 1326.90041
[71] Modaresi S, Vielma JP (2014) Convex hull of two quadratic or a conic quadratic and a quadratic inequality. Math. Programming 164(1-2):383-409.Crossref, Google Scholar · Zbl 1393.90074
[72] Modaresi S, Kılınç MR, Vielma JP (2016) Intersection cuts for nonlinear integer programming: Convexification techniques for structured sets. Math. Programming 155(1-2):575-611.Crossref, Google Scholar · Zbl 1358.90078
[73] Nahmias S, Cheng Y (2005) Production and Operations Analysis, vol. 6 (McGraw-Hill, New York).Google Scholar
[74] Nikolova E, Kelner J, Brand M, Mitzenmacher M (2006) Stochastic shortest paths via quasi-convex maximization. Azar Y, Erlebach T, eds. Algorithms—ESA 2006, Lecture Notes in Computer Science, vol. 4168 (Springer, Berlin, Heidelberg), 552-563.Google Scholar · Zbl 1131.05317
[75] Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118(2):237-251.Crossref, Google Scholar · Zbl 1179.90290
[76] Özsen L, Coullard CR, Daskin MS (2008) Capacitated warehouse location model with risk pooling. Naval Res. Logist. 55(4):295-312.Crossref, Google Scholar · Zbl 1153.90484
[77] Pesenti R, Ukovich W (2003) Economic lot scheduling on multiple production lines with resource constraints. Internat. J. Production Econom. 81:469-481.Crossref, Google Scholar
[78] Poljak S, Wolkowicz H (1995) Convex relaxations of (0, 1)-quadratic programming. Math. Oper. Res. 20(3):550-561.Link, Google Scholar · Zbl 0845.90089
[79] Prokopyev OA, Kong N, Martinez-Torres DL (2009) The equitable dispersion problem. Eur. J. Oper. Res. 197(1):59-67.Crossref, Google Scholar · Zbl 1157.90539
[80] Prokopyev OA, Meneses C, Oliveira CA, Pardalos PM (2005) On multiple-ratio hyperbolic 0-1 programming problems. Pacific J. Optim. 1(2):327-345.Google Scholar · Zbl 1105.90094
[81] Sahinidis N, Grossmann IE (1991) MINLP model for cyclic multiproduct scheduling on continuous parallel lines. Comput. Chemical Engrg. 15(2):85-103.Crossref, Google Scholar
[82] Santana A, Dey SS (2017) Some cut-generating functions for second-order conic sets. Discrete Optim. 24:51-65.Crossref, Google Scholar · Zbl 1387.90183
[83] Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346-355.Crossref, Google Scholar · Zbl 1052.90067
[84] Şen A, Atamtürk A, Kaminsky P (2018) A conic integer programming approach to constrained assortment optimization under the mixed multinomial logit model. Oper. Res. 66(4):994-1003.Link, Google Scholar
[85] Sharpe WF (1994) The Sharpe ratio. J. Portfolio Management 21:49-58.Crossref, Google Scholar
[86] Shen Z-JM, Coullard C, Daskin MS (2003) A joint location-inventory model. Transportation Sci. 37(1):40-55.Link, Google Scholar
[87] Stubbs AR, Mehrotra S (1999) A branch-and-cut method for 0-1 mixed convex programming. Math. Programming 86(3):515-532.Crossref, Google Scholar · Zbl 0946.90054
[88] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225-249.Crossref, Google Scholar · Zbl 1099.90047
[89] Tawarmalani M, Ahmed S, Sahinidis NV (2002) Global optimization of 0-1 hyperbolic programs. J. Global Optim. 24(4):385-416.Crossref, Google Scholar · Zbl 1046.90054
[90] Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1-18.Crossref, Google Scholar · Zbl 0800.90772
[91] Yu J, Ahmed S (2017) Polyhedral results for a class of cardinality constrained submodular minimization problems. Discrete Optim. 24:87-102.Crossref, Google Scholar · Zbl 1387.90167
[92] Zhang Y, · Zbl 1401.90140
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.