Submodularity in Conic Quadratic Mixed 0–1 Optimization

References

• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1–2):149–169.Crossref, Google Scholar
• 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
• 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
• 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
• Amiri A (1997) Solution procedures for the service system design problem. Comput. Oper. Res. 24(1):49–60.Crossref, Google Scholar
• Anstreicher KM (2012) On convex relaxations for quadratically constrained quadratic programming. Math. Programming 136(2):233–251.Crossref, Google Scholar
• Atamtürk A, Bhardwaj A (2015) Supermodular covering knapsack polytope. Discrete Optim. 18:74–86.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• Atamtürk A, Narayanan V (2008) Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5):618–622.Crossref, Google Scholar
• Atamtürk A, Narayanan V (2009) The submodular knapsack polytope. Discrete Optim. 6(4):333–344.Crossref, Google Scholar
• Atamtürk A, Narayanan V (2010) Conic mixed-integer rounding cuts. Math. Programming 122(1):1–20.Crossref, Google Scholar
• Atamtürk A, Narayanan V (2011) Lifting for conic mixed-integer programming. Math. Programming 126(2):351–363.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769–805.Link, Google Scholar
• Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1):1–13.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193–205.Link, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization, Princeton Series in Applied Mathematics. (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• 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
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1–3):49–71.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• 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
• 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
• Borrero JS, Gillen C, Prokopyev OA (2016a) Fractional 0–1 programming: Applications and algorithms. J. Global Optim. 69(1):1–28.Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math. Programming 86(3):595–614.Crossref, Google Scholar
• Çezik MT, Iyengar G (2005) Cuts for mixed 0-1 conic programming. Math. Programming 104(1):179–202.Crossref, Google Scholar
• Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• 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
• 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
• 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
• 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
• Désir A, Goyal V, Zhang J (2014) Near-optimal algorithms for capacity constrained assortment optimization. Working paper, Columbia University, New York.Google Scholar
• 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
• 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
• 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
• Elhedhli S (2005) Exact solution of a class of nonlinear knapsack problems. Oper. Res. Lett. 33(6):615–624.Crossref, Google Scholar
• Elhedhli S (2006) Service system design with immobile servers, stochastic demand, and congestion. Manufacturing Service Oper. Management 8(1):92–97.Link, Google Scholar
• 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
• Fujishige S (2005) Submodular Functions and Optimization, vol. 58 (Elsevier, Amsterdam).Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• Lim C, Smith JC (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15–26.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• 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
• Nahmias S, Cheng Y (2005) Production and Operations Analysis, vol. 6 (McGraw-Hill, New York).Google Scholar
• 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
• Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118(2):237–251.Crossref, Google Scholar
• Özsen L, Coullard CR, Daskin MS (2008) Capacitated warehouse location model with risk pooling. Naval Res. Logist. 55(4):295–312.Crossref, Google Scholar
• 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
• Poljak S, Wolkowicz H (1995) Convex relaxations of (0, 1)-quadratic programming. Math. Oper. Res. 20(3):550–561.Link, Google Scholar
• Prokopyev OA, Kong N, Martinez-Torres DL (2009) The equitable dispersion problem. Eur. J. Oper. Res. 197(1):59–67.Crossref, Google Scholar
• 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
• 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
• Santana A, Dey SS (2017) Some cut-generating functions for second-order conic sets. Discrete Optim. 24:51–65.Crossref, Google Scholar
• 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
• Ş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
• Sharpe WF (1994) The Sharpe ratio. J. Portfolio Management 21:49–58.Crossref, Google Scholar
• Shen Z-JM, Coullard C, Daskin MS (2003) A joint location-inventory model. Transportation Sci. 37(1):40–55.Link, Google Scholar
• 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
• Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225–249.Crossref, Google Scholar
• Tawarmalani M, Ahmed S, Sahinidis NV (2002) Global optimization of 0-1 hyperbolic programs. J. Global Optim. 24(4):385–416.Crossref, Google Scholar
• Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1–18.Crossref, Google Scholar
• Yu J, Ahmed S (2017) Polyhedral results for a class of cardinality constrained submodular minimization problems. Discrete Optim. 24:87–102.Crossref, Google Scholar
• Zhang Y, Jiang R, Shen S (2018) Ambiguous chance-constrained binary programs under mean-covariance information. SIAM J. Optim. 28(4):2922–2944.Crossref, Google Scholar