On Constrained Mixed-Integer DR-Submodular Minimization

References

• [1] Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1):149–169.Crossref, Google Scholar
• [2] Aspvall B, Shiloach Y (1980) A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM J. Comput. 9(4):827–845.Crossref, Google Scholar
• [3] Atamtürk A, Gómez A (2020) Submodularity in conic quadratic mixed 0–1 optimization. Oper. Res. 68(2):609–630.Abstract, Google Scholar
• [4] 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
• [5] Atamtürk A, Jeon H (2019) Lifted polymatroid inequalities for mean-risk optimization with indicator variables. J. Global Optim. 73(4):677–699.Crossref, Google Scholar
• [6] Atamtürk A, Narayanan V (2008) Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5):618–622.Crossref, Google Scholar
• [7] Atamtürk A, Narayanan V (2022) Submodular function minimization and polarity. Math. Programming 196:57–67.Crossref, Google Scholar
• [8] Bach F (2019) Submodular functions: From discrete to continuous domains. Math. Programming 175(1):419–459.Crossref, Google Scholar
• [9] Bian A, Levy K, Krause A, Buhmann JM (2017) Continuous DR-submodular maximization: Structure and algorithms. Bengio S, Wallach HM, Larochelle H, Grauman K, Fusi N, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Neural Information Processing Systems Foundation, La Jolla, CA).Google Scholar
• [10] Bian AA, Mirzasoleiman B, Buhmann J, Krause A (2017) Guaranteed non-convex optimization: Submodular maximization over continuous domains. Artificial Intelligence Statistics (PMLR), 111–120.Google Scholar
• [11] Calinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint. Rote G, Vygen J, eds. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin, Heidelberg), 182–196.Google Scholar
• [12] Cohen E, Megiddo N (1991) Improved algorithms for linear inequalities with two variables per inequality. Vazirani UM, Sipser M, eds. Proc. 23rd Annual ACM Sympos. Theory Comput. (ACM, New York), 145–155.Google Scholar
• [13] Cornuejols G, Fisher M, Nemhauser GL (1977) On the uncapacitated location problem. Ann. Discrete Math. 1:163–177.Crossref, Google Scholar
• [14] Cunningham WH (1985) On submodular function minimization. Combinatorica 5(3):185–192.Crossref, Google Scholar
• [15] Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. Scharnow JG, ed. Combinatorial Optimization—Eureka, You Shrink! (Springer, Berlin, Heidelberg), 11–26.Crossref, Google Scholar
• [16] Ene A, Nguyen HL (2016) A reduction for optimizing lattice submodular functions with diminishing returns. Preprint, submitted June 27, https://arxiv.org/abs/1606.08362.Google Scholar
• [17] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• [18] 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
• [19] Han S, Gómez A, Pang J-S (2022) On polynomial-time solvability of combinatorial markov random fields. Preprint, submitted September 27, https://arxiv.org/abs/2209.13161.Google Scholar
• [20] Hassani H, Soltanolkotabi M, Karbasi A (2017) Gradient methods for submodular maximization. Bengio S, Wallach HM, Larochelle H, Grauman K, Fusi N, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Neural Information Processing Systems Foundation, La Jolla, CA).Google Scholar
• [21] Hochbaum DS, Naor J (1994) Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23(6):1179–1192.Crossref, Google Scholar
• [22] Iwata S (2008) Submodular function minimization. Math. Programming 112(1):45–64.Crossref, Google Scholar
• [23] Iwata S, Orlin JB (2009) A simple combinatorial algorithm for submodular function minimization. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1230–1237.Google Scholar
• [24] Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• [25] Jegelka S, Bilmes J (2011) Submodularity beyond submodular energies: Coupling edges in graph cuts. CVPR 2011 (IEEE, Piscataway, NJ), 1897–1904.Google Scholar
• [26] Kempe D, Kleinberg J, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput. 11(4):105–147.Crossref, Google Scholar
• [27] Kılınç-Karzan F, Küçükyavuz S, Lee D (2023) Conic mixed-binary sets: Convex hull characterizations and applications. Oper. Res., ePub ahead of print July 19, https://doi.org/10.1287/opre.2020.0827.Google Scholar
• [28] 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:283–326.Crossref, Google Scholar
• [29] Krause A, Singh A, Guestrin C (2008) Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Machine Learn. Res. 9(2):235–284.Google Scholar
• [30] Lee YT, Sidford A, Wong SC-W (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1049–1065.Google Scholar
• [31] Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2010) Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23(4):2053–2078.Crossref, Google Scholar
• [32] Lovász L (1983) Submodular functions and convexity. Bachem A, Grötschel M, Korte B, eds. Mathematical Programming: The State of the Art (Springer, Berlin), 235–257.Crossref, Google Scholar
• [33] McCormick ST (2005) Submodular function minimization. Handbooks Oper. Res. Management Sci. 12:321–391.Crossref, Google Scholar
• [34] Medal H, Ahanor I (2022) A spatial branch-and-bound approach for maximization of non-factorable monotone continuous submodular functions. Preprint, submitted August 29, https://arxiv.org/abs/2208.13886.Google Scholar
• [35] Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of Turán. Canadian J. Math. 17:533–540.Crossref, Google Scholar
• [36] Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3):177–188.Link, Google Scholar
• [37] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• [38] Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118(2):237–251.Crossref, Google Scholar
• [39] Orlin JB, Schulz AS, Udwani R (2018) Robust monotone submodular function maximization. Math. Programming 172(1):505–537.Crossref, Google Scholar
• [40] Sadeghi O, Fazel M (2021) Faster first-order algorithms for monotone strongly DR-submodular maximization. SIAM Conf. Appl. Comput. Discrete Algorithms (SIAM, Philadelphia), 169–179.Google Scholar
• [41] 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
• [42] Shen H, Jiang R (2023) Chance-constrained set covering with Wasserstein ambiguity. Math. Programming 198:621–674.Crossref, Google Scholar
• [43] Shi X, Prokopyev OA, Zeng B (2022) Sequence independent lifting for a set of submodular maximization problems. Math. Programming 196:69–114.Crossref, Google Scholar
• [44] Shostak R (1981) Deciding linear inequalities by computing loop residues. J. ACM 28(4):769–779.Crossref, Google Scholar
• [45] Soma T, Yoshida Y (2015) A generalization of submodular cover via the diminishing return property on the integer lattice. Adv. Neural Inform. Processing Systems, vol. 28 (NIPS Foundation, La Jolla, CA), 847–855.Google Scholar
• [46] Soma T, Yoshida Y (2017) Non-monotone DR-submodular function maximization. Proc. Conf. AAAI Artificial Intelligence, vol. 31 (AAAI Press, Palo Alto, CA).Google Scholar
• [47] Soma T, Yoshida Y (2018) Maximizing monotone submodular functions over the integer lattice. Math. Programming 172(1):539–563.Crossref, Google Scholar
• [48] Staib M, Jegelka S (2017) Robust budget allocation via continuous submodular functions. Bach FR, Blei DM, eds. Internat. Conf. Machine Learn. (ICML), 3230–3240.Google Scholar
• [49] Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41–43.Crossref, Google Scholar
• [50] Svitkina Z, Fleischer L (2011) Submodular approximation: Sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6):1715–1737.Crossref, Google Scholar
• [51] Topkis DM (1978) Minimizing a submodular function on a lattice. Oper. Res. 26(2):305–321.Link, Google Scholar
• [52] Wolsey LA (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385–393.Crossref, Google Scholar
• [53] Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization, vol. 55 (John Wiley & Sons, Inc., New York).Google Scholar
• [54] Wu H-H, Küçükyavuz S (2018) A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3):563–595.Crossref, Google Scholar
• [55] Wu H-H, Küçükyavuz S (2019) Probabilistic partial set covering with an oracle for chance constraints. SIAM J. Optim. 29(1):690–718.Crossref, Google Scholar
• [56] Wu H-H, Küçükyavuz S (2020) An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions. Oper. Res. Lett. 48(3):356–361.Crossref, Google Scholar
• [57] Xie W (2021) On distributionally robust chance constrained programs with Wasserstein distance. Math. Programming 186:115–155.Crossref, Google Scholar
• [58] Yu J, Ahmed S (2017) Maximizing a class of submodular utility functions with constraints. Math. Programming 162(1–2):145–164.Crossref, Google Scholar
• [59] Yu J, Ahmed S (2017) Polyhedral results for a class of cardinality constrained submodular minimization problems. Discrete Optim. 24:87–102.Crossref, Google Scholar
• [60] Yu Q, Küçükyavuz S (2020) A polyhedral approach to bisubmodular function minimization. Oper. Res. Lett. 49(1):5–10.Crossref, Google Scholar
• [61] Yu Q, Küçükyavuz S (2021) An exact cutting plane method for k-submodular function maximization. Discrete Optim. 42:100670.Crossref, Google Scholar
• [62] 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
• [63] 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