Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems

References

• Adibi A, Mokhtari A, Hassani H (2022) Minimax optimization: The case of convex-submodular. Proc. 25th Internat. Conf. Artificial Intelligence Statist., vol. 151 (PMLR, New York), 3556–3580.Google Scholar
• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1–2):149–169.Google Scholar
• Atamtürk A (2006) Strong formulations of robust mixed 0-1 programming. Math. Programming 108(2–3):235–250.Google Scholar
• Atamtürk A, Gómez A (2020) Submodularity in conic quadratic mixed 0-1 optimization. Oper. Res. 68(2):609–630.Abstract, Google Scholar
• Atamtürk A, Gómez A (2023) Supermodularity and valid inequalities for quadratic optimization with indicators. Math. Programming 201(1–2):295–338.Google Scholar
• Austin R, Choi C, Preis A, Ostfeld A, Lansey K (2009) Multi-objective sensor placements with improved water quality models in a network with multiple junctions. World Environmental and Water Resources Congress 2009: Great Rivers, 451–459.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. Let. 25(1):1–13.Google Scholar
• Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming 88(3):411–424.Google Scholar
• Ben-Tal A, Golany B, Nemirovski A, Vial J-P (2005) Retailer-supplier flexible commitments contracts: A robust optimization approach. Manufacturing Service Oper. Management 7(3):248–271.Link, Google Scholar
• Berry J, Fleischer L, Hart WE, Phillips CA, Watson J (2005) Sensor placement in municipal water networks. J. Water Resources Planning Management 131(3):237–243.Google Scholar
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1–3):49–71.Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Thiele A (2006) A robust optimization approach to inventory theory. Oper. Res. 54(1):150–168.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Google Scholar
• Bertsimas D, Litvinov E, Sun XA, Zhao J, Zheng T (2013) Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans. Power Systems 28(1):52–63.Google Scholar
• Bogunovic I, Mitrović S, Scarlett J, Cevher V (2017) Robust submodular maximization: A non-uniform partitioning approach. Proc. 34th Internat. Conf. Machine Learn., ICML-2017, 508–516.Google Scholar
• Boykov Y, Jolly M-P (2001) Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images. Proc. Eighth IEEE Internat. Conf. Comput. Vision (IEEE), 105–112.Google Scholar
• Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, KDD ‘09 (ACM, New York), 199–208.Google Scholar
• Church R, ReVelle C (1974) The maximal covering location problem. Papers Regional Sci. Assoc. 32(1):101–118.Google Scholar
• Coniglio S, Furini F, Ljubić I (2022) Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems. Math. Programming 196(1–2):9–56.Google Scholar
• Cordeau J-F, Furini F, Ljubić I (2019) Benders decomposition for very large scale partial set covering and maximal covering location problems. Eur. J. Oper. Res. 275(3):882–896.Google Scholar
• Dorini G, Jonkergouw P, Kapelan Z, di Pierro F, Khu ST, Savic D (2006) An efficient algorithm for sensor placement in water distribution systems. Eighth Annual Water Distribution Systems Analysis Sympos. (WDSA).Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Google Scholar
• Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Google Scholar
• Fischetti M, Kahr M, Leitner M, Monaci M, Ruthmair M (2018) Least cost influence propagation in (social) networks. Math. Programming 170(1):293–325.Google Scholar
• Ghaoui LE, 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
• Goldfarb D, Iyengar G (2003) Robust portfolio selection problems. Math. Oper. Res. 28(1):1–38.Link, Google Scholar
• Golovin D, Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42(1):427–486.Google Scholar
• Gómez A (2018) Submodularity and valid inequalities in nonlinear optimization with indicator variables. Optimization-Online.Google Scholar
• Günneç D, Raghavan S, Zhang R (2020) Least-cost influence maximization on social networks. INFORMS J. Comput. 32(2):289–302.Abstract, Google Scholar
• He X, Kempe D (2016) Robust influence maximization. Proc. 22nd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, KDD ‘16 (ACM, New York), 885–894.Google Scholar
• Huang JJ, McBean, EA, James W (2006) Multiobjective optimization for monitoring sensor placement in water distribution systems. Eighth Annual Water Distribution Systems Analysis Sympos. (WDSA).Google Scholar
• Jegelka S, Bilmes J (2011) Submodularity beyond submodular energies: Coupling edges in graph cuts. Cvpr (IEEE, Piscataway, NJ).Google Scholar
• Jiang R, Zhang M, Li G, Guan Y (2012) Benders decomposition for the two-stage security constrained robust unit commitment problem. Proc. IISE Annual Conf., 1–10.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proc. Ninth ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, KDD ‘03 (ACM, New York), 137–146.Google Scholar
• Kessler A, Ostfeld A, Sinai G (1998) Detecting accidental contaminations in municipal water networks. J. Water Resources Plannning Management 124(4):192–198.Google Scholar
• Kılınç-Karzan F, Küçükyavuz S, Lee D (2022) Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens. Math. Programming 195(1–2):283–326.Google Scholar
• Kılınç-Karzan F, Küçükyavuz S, Lee D, Shafieezadeh-Abadeh S (2025) Conic mixed-binary sets: Convex hull characterizations and applications. Oper. Res. 73(1):251–269.Abstract, Google Scholar
• Kouvelis P, Yu G (1997) Robust Discrete Optimization and Its Applications (Springer, Dordrecht, Netherlands).Google Scholar
• Krause A, Golovin D (2014) Submodular function maximization. Bordeaux L, Hamadi Y, Kohli P, eds. Tractability: Practical Approaches to Hard Problems (Cambridge University Press, Cambridge, UK), 71–104.Google Scholar
• Krause A, Singh A, Guestrin C (2008c) Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Machine Learn. Res. 9(8):235–284.Google Scholar
• Krause A, McMahan HB, Guestrin C, Gupta A (2008b) Robust submodular observation selection. J. Machine Learn. Res. 9(93):2761–2801.Google Scholar
• Krause A, Leskovec J, Guestrin C, VanBriesen J, Faloutsos C (2008a) Efficient sensor placement optimization for securing large water distribution networks. J. Water Resources Planning Management 134(6):516–526.Google Scholar
• Küçükyavuz S, Yu Q (2023) Mixed-integer programming approaches to generalized submodular optimization and its applications. Bish EK, Balasubramanian H, eds. Tutorials in Operations Research: Advancing the Frontiers of or/MS: From Methodologies to Applications, chapter 1 (INFORMS, Catonsville, MD), 1–30.Link, Google Scholar
• Kumar A, Kansal ML, Arora G (1997) Identification of monitoring stations in water distribution system. J. Environ. Engrg. 123(8):746–752.Google Scholar
• Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. Proc. 13th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, KDD ‘07 (ACM, New York), 420–429.Google Scholar
• Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Proc. 49th Annual Meeting Assoc. Comput. Linguistics: Human Language Technologies (Association for Computational Linguistics), 510–520.Google Scholar
• Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems. Oper. Res. 43(2):264–281.Link, Google Scholar
• Nannicini G, Sartor G, Traversi E, Wolfler-Calvo R (2019) An exact algorithm for robust influence maximization. Integer Programming Combin. Optim.: 20th Internat. Conf. (Lecture Notes in Computer Science), 313–326.Google Scholar
• Nemhauser G, Wolsey L (1981) Maximizing submodular set functions: Formulations and analysis of algorithms. Hansen P, ed. Annals of Discrete Mathematics (11) Studies on Graphs and Discrete Programming, North-Holland Mathematics Studies, vol. 59 (North-Holland, Amsterdam), 279–301.Google Scholar
• Nemhauser G, Wolsey L, Fisher M (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Google Scholar
• Orlin JB, Schulz AS, Udwani R (2018) Robust monotone submodular function maximization. Math. Programming 172(1–2):505–537.Google Scholar
• Ostfeld A, Salomons E (2004) Optimal layout of early warning detection stations for water distribution systems security. J. Water Resources Planning Management 130(5):377–385.Google Scholar
• Ostfeld A, Uber JG, Salomons E, Berry JW, Hart WE, Phillips CA, Watson JP, et al. (2008) The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms. J. Water Resources Planning Management 134(6):556–568.Google Scholar
• Powers T, Bilmes J, Wisdom S, Krout DW, Atlas L (2016) Constrained robust submodular optimization. NeurIPS 2016 Workshop Optim. Machine Learn. (OPT).Google Scholar
• Preis A, Ostfeld A (2006) Multiobjective sensor design for water distribution systems security. Eighth Annual Water Distribution Systems Analysis Sympos. (WDSA).Google Scholar
• Shen H, Jiang R (2023) Chance-constrained set covering with Wasserstein ambiguity. Math. Programming 198(1):621–674.Google Scholar
• Shi X, Prokopyev OA, Zeng B (2022) Sequence independent lifting for a set of submodular maximization problems. Math. Programming 196(1–2):69–114.Google Scholar
• Staib M, Wilder B, Jegelka S (2019) Distributionally robust submodular maximization. Proc. 22nd Internat. Conf. Artificial Intelligence Statist., vol. 89 (PMLR), 506–516.Google Scholar
• Torrico A, Singh M, Pokutta S, Haghtalab N, Naor J, Anari N (2021) Structured robust submodular maximization: Offline and online algorithms. INFORMS J. Comput. 33(4):1590–1607.Abstract, Google Scholar
• Tütüncü R, Koenig M (2004) Robust asset allocation. Ann. Oper. Res. 132(1):157–187.Google Scholar
• Watson J-P, Greenberg HJ, Hart WE (2004) A multiple-objective analysis of sensor placement optimization in water networks. Proc. ASCE World Water Environmental Resources.Google Scholar
• Wu H, Küçükyavuz S (2018) A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3):563–595.Google Scholar
• Wu H, Küçükyavuz S (2019) Probabilistic partial set covering with an oracle for chance constraints. SIAM J. Optim. 29(1):690–718.Google Scholar
• Wu ZY, Walski T (2006) Multiobjective optimization of sensor placement in water distribution systems. Eighth Annual Water Distribution Systems Analysis Sympos. (WDSA).Google Scholar
• Yu J, Ahmed S (2017) Maximizing a class of submodular utility functions with constraints. Math. Programming 162(1–2):145–164.Google Scholar
• Yu Q, Küçükyavuz S (2021a) An exact cutting plane method for k-submodular function maximization. Discrete Optim. 42:100670.Google Scholar
• Yu Q, Küçükyavuz S (2021b) A polyhedral approach to bisubmodular function minimization. Oper. Res. Lett. 49(1):5–10.Google Scholar
• Yu Q, Küçükyavuz S (2023) Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints. Math. Programming 201(1):803–861.Google Scholar
• Yu Q, Küçükyavuz S (2025) On constrained mixed-integer DR-submodular minimization. Math. Oper. Res. 50(2):871–909.Link, Google Scholar
• Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5):457–461.Google Scholar
• Zhao L, Zeng B (2012) Robust unit commitment problem with demand response and wind energy. Proc. IEEE Power Energy Society General Meeting (IEEE, Piscataway, NJ), 1–8.Google Scholar
• Zheng K, Albert LA, Luedtke JR, Towle E (2019) A budgeted maximum multiple coverage model for cybersecurity planning and management. IISE Trans. 51(12):1303–1317.Google Scholar