Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. Link to the article

CONIGLIO, S., FURINI, F. and LJUBIC, I. (2022). Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems. Mathematical Programming, 196(1-2), pp. 9-56.

Keywords : #Submodular-maximization, #Branch, #and, #Cut, #Benders-decomposition, #Stochastic-maximal-covering-location-problems, #Influence-maximization