Année
2022
Auteurs
LJUBIC Ivana, CONIGLIO Stefano, FURINI Fabio
Abstract
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.
CONIGLIO, S., FURINI, F. et 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.