{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T07:45:38Z","timestamp":1772610338047,"version":"3.50.1"},"reference-count":47,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T00:00:00Z","timestamp":1772150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2023YFE0108600"],"award-info":[{"award-number":["2023YFE0108600"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>Maximizing the expected value of a concave and strictly increasing utility function defines a fundamental class of discrete optimization problems. Among them, coverage decision problems with diminishing marginal returns under uncertainty, typically modeled via a set-union operator, have been extensively studied. In the classical framework, an item becomes active once it is covered by at least one chosen meta-item. Motivated by increasing robustness requirements in applications such as automated systems, social networks, and emergency response planning, we extend this setting by introducing threshold-based activation. The resulting generalized problem can be formulated as a mixed-integer nonlinear programming problem, for which we further propose three exact algorithms. The first two methods linearize the utility function using submodular cuts (SC) and outer-approximation (OA) techniques, respectively, resulting in formulations that can be solved exactly by off-the-shelf mixed-integer linear programming solvers. The third method builds upon the OA framework and further employs Benders decomposition (BD) to project out the item-related variables, which enables superior performance on ultra-large-scale instances. Extensive computational experiments show that, compared with the SC and BD methods, the OA method exhibits a substantial speed advantage on instances with a size of around 40,000, which can be solved within 100 s. In contrast, for ultra-large-scale instances with more than 100,000 items, the BD method demonstrates superior computational efficiency. These results provide practical guidance for algorithmic strategy selection and further demonstrate the computational tractability of this broader class of utility maximization problems under threshold-based activation.<\/jats:p>","DOI":"10.3390\/axioms15030169","type":"journal-article","created":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:52:38Z","timestamp":1772207558000},"page":"169","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Expected Maximization of a Concave Utility Function Under Threshold-Based Activation"],"prefix":"10.3390","volume":"15","author":[{"given":"Guangming","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China"},{"name":"Zhejiang Lab, Hangzhou 311100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3251-7270","authenticated-orcid":false,"given":"Yufei","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengjie","family":"Chen","sequence":"additional","affiliation":[{"name":"Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China"},{"name":"School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mou","family":"Sun","sequence":"additional","affiliation":[{"name":"Zhejiang Lab, Hangzhou 311100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wushuaijun","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2026,2,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s10107-009-0298-1","article-title":"Maximizing a class of submodular utility functions","volume":"128","author":"Ahmed","year":"2011","journal-title":"Math. Program."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10107-016-1033-3","article-title":"Maximizing a class of submodular utility functions with constraints","volume":"162","author":"Yu","year":"2017","journal-title":"Math. Program."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.orl.2015.12.016","article-title":"Maximizing expected utility over a knapsack constraint","volume":"44","author":"Yu","year":"2016","journal-title":"Oper. Res. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1057\/jors.1995.45","article-title":"Characteristics of decisions in decision analysis practice","volume":"46","author":"Corner","year":"1995","journal-title":"J. Oper. Res. Soc."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1016\/j.ejor.2005.10.075","article-title":"Competitive facility location model with concave demand","volume":"181","author":"Aboolian","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Feige, U. (2006, January 21\u201323). On maximizing welfare when utility functions are subadditive. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA.","DOI":"10.1145\/1132516.1132523"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/s10107-022-01884-7","article-title":"Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems","volume":"196","author":"Coniglio","year":"2022","journal-title":"Math. Program."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., and Tardos, \u00c9. (2003, January 24\u201327). Maximizing the spread of influence through a social network. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956769"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D., and Nisan, N. (2001, January 14\u201317). Combinatorial auctions with decreasing marginal utilities. Proceedings of the 3rd ACM Conference on Electronic Commerce, Tampa, FL, USA.","DOI":"10.1145\/501158.501161"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.ejor.2017.09.023","article-title":"Outer approximation and submodular cuts for maximum capture facility location problems with random utilities","volume":"266","author":"Moreno","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/trsc.23.3.192","article-title":"The maximum availability location problem","volume":"23","author":"ReVelle","year":"1989","journal-title":"Transp. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Li, G., Li, Y., Zhang, W., and Chen, S. (2025). Benders decomposition approach for generalized maximal covering and partial set covering location problems. Symmetry, 17.","DOI":"10.3390\/sym17091417"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1007\/s10898-019-00804-y","article-title":"Approximation algorithm for the partial set multi-cover problem","volume":"75","author":"Shi","year":"2019","journal-title":"J. Glob. Optim."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1007\/s10878-019-00513-y","article-title":"A primal-dual algorithm for the minimum partial set multi-cover problem","volume":"39","author":"Ran","year":"2020","journal-title":"J. Comb. Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02097801","article-title":"The maximum reliability location problem and \u03b1-reliable p-center problem: Derivatives of the probabilistic location set covering problem","volume":"18","author":"Revelle","year":"1989","journal-title":"Ann. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1068\/b150143","article-title":"A reliability-constrained siting model with local estimates of busy fractions","volume":"15","author":"ReVelle","year":"1988","journal-title":"Environ. Plan. B Plan. Des."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0377-2217(95)00182-4","article-title":"The queueing maximal availability location problem: A model for the siting of emergency vehicles","volume":"93","author":"Marianov","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"102465","DOI":"10.1016\/j.tre.2021.102465","article-title":"Emergency facility location problems in logistics: Status and perspectives","volume":"154","author":"Wang","year":"2021","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2002","DOI":"10.1057\/jors.2010.176","article-title":"Discrete cooperative covering problems","volume":"62","author":"Berman","year":"2011","journal-title":"J. Oper. Res. Soc."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s11067-007-9035-6","article-title":"Determining optimal police patrol areas with maximal covering and backup covering location models","volume":"10","author":"Curtin","year":"2010","journal-title":"Netw. Spat. Econ."},{"key":"ref_21","unstructured":"Reichlin, C.R.A. (2012). Non-Concave Utility Maximization:: Optimal Investment, Stability and Applications. [Ph.D. Thesis, ETH Zurich]."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Rahmattalabi, A., Jabbari, S., Lakkaraju, H., Vayanos, P., Izenberg, M., Brown, R., Rice, E., and Tambe, M. (2021, January 2\u20139). Fair influence maximization: A welfare optimization approach. Proceedings of the AAAI Conference on Artificial Intelligence, Virtual.","DOI":"10.1609\/aaai.v35i13.17383"},{"key":"ref_23","first-page":"1","article-title":"A general concave fairness framework for influence maximization based on poverty reward","volume":"19","author":"Wang","year":"2024","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"52103","DOI":"10.1007\/s11432-018-9609-7","article-title":"Cumulative activation in social networks","volume":"62","author":"Shan","year":"2019","journal-title":"Sci. China Inf. Sci."},{"key":"ref_25","unstructured":"Romero, D.M., Meeder, B., and Kleinberg, J. (April, January 28). Differences in the mechanics of information diffusion across topics: Idioms, political hashtags, and complex contagion on twitter. Proceedings of the 20th International Conference on World Wide Web, Hyderabad, India."},{"key":"ref_26","first-page":"277","article-title":"The multi-level location set covering model","volume":"35","author":"Church","year":"2003","journal-title":"Geogr. Anal."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1287\/trsc.1040.0107","article-title":"Reliability models for facility location: The expected failure cost case","volume":"39","author":"Snyder","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1086\/209225","article-title":"An evaluation cost model of consideration sets","volume":"16","author":"Hauser","year":"1990","journal-title":"J. Consum. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mksc.16.1.1","article-title":"A model of retail formats based on consumers\u2019 economizing on shopping time","volume":"16","author":"Messinger","year":"1997","journal-title":"Mark. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1080\/00218499.1997.12466679","article-title":"Effective frequency: Then and now","volume":"37","author":"Naples","year":"1997","journal-title":"J. Advert. Res."},{"key":"ref_31","unstructured":"Ostrow, J.W. (1982). Setting effective frequency levels. Proceedings of the Effective Frequency: The State of the Art, Advertising Research Foundation, Key Issues Workshop."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1057\/jt.2012.1","article-title":"Effective frequency estimates in local media planning practice","volume":"20","author":"Makienko","year":"2012","journal-title":"J. Target. Meas. Anal. Mark."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An analysis of approximations for maximizing submodular set functions\u2014I","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Program."},{"key":"ref_34","unstructured":"Wolsey, L.A., and Nemhauser, G.L. (1999). Integer and Combinatorial Optimization, John Wiley & Sons."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s10107-022-01801-y","article-title":"Sequence independent lifting for a set of submodular maximization problems","volume":"196","author":"Shi","year":"2022","journal-title":"Math. Program."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"106673","DOI":"10.1016\/j.cor.2024.106673","article-title":"Accelerated Benders decomposition and local branching for dynamic maximum covering location problems","volume":"167","author":"Lamontagne","year":"2024","journal-title":"Comput. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Nemhauser, G., and Wolsey, L. (1988). Matroid and Submodular Function Optimization. Integer and Combinatorial Optimization, John Wiley & Sons, Ltd.. Chapter 3.","DOI":"10.1002\/9781118627372"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","article-title":"A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems","volume":"33","author":"Padberg","year":"1991","journal-title":"SIAM Rev."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Wolsey, L.A. (2020). Integer Programming, John Wiley & Sons.","DOI":"10.1002\/9781119606475"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.ejor.2016.03.002","article-title":"Benders decomposition without separability: A computational study for capacitated facility location problems","volume":"253","author":"Fischetti","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1016\/j.ejor.2018.12.021","article-title":"Benders decomposition for very large scale partial set covering and maximal covering location problems","volume":"275","author":"Cordeau","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.ejor.2020.06.028","article-title":"Large-scale influence maximization via maximal covering location","volume":"289","author":"Leitner","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1007\/s10589-012-9458-y","article-title":"Branch and cut algorithms for detecting critical nodes in undirected graphs","volume":"53","author":"Grosso","year":"2012","journal-title":"Comput. Optim. Appl."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.cor.2018.04.012","article-title":"Improved formulations for minimum connectivity network interdiction problems","volume":"97","author":"Pavlikov","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"ref_45","unstructured":"CPLEX (2022). User\u2019s Manual for CPLEX, IBM. Available online: https:\/\/www.ibm.com\/docs\/en\/icos\/20.1.0?topic=cplex-users-manual."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.cor.2006.03.007","article-title":"Solving the maximal covering location problem with heuristic concentration","volume":"35","author":"ReVelle","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1002\/net.22161","article-title":"Efficient presolving methods for the influence maximization problem","volume":"82","author":"Chen","year":"2023","journal-title":"Networks"}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/15\/3\/169\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T05:11:28Z","timestamp":1772601088000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/15\/3\/169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,27]]},"references-count":47,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2026,3]]}},"alternative-id":["axioms15030169"],"URL":"https:\/\/doi.org\/10.3390\/axioms15030169","relation":{},"ISSN":["2075-1680"],"issn-type":[{"value":"2075-1680","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,27]]}}}