article · Mathematical Programming · 2009
Maximizing a class of submodular utility functions
Cited by 84Open access
Abstract
Given a finite ground set N and a value vector $${a \in \mathbb{R}^N}$$ , we consider optimization problems involving maximization of a submodular set utility function of the form $${h(S)= f \left(\sum_{i \in S} a_i \right ), S \subseteq N}$$ , where f is a strictly concave, increasing, differentiable function. This utility function appears frequently in combinatorial optimization problems when modeling risk aversion and decreasing marginal preferences, for instance, in risk-averse capital budgeting under uncertainty, competitive facility location, and combinatorial auctions. These problems can be formulated as linear mixed 0-1 programs. However, the standard formulation of these problems using submodular inequalities is ineffective for their solution, except for very small instances. In this paper, we perform a polyhedral analysis of a relevant mixed-integer set and, by exploiting the structure of the utility function h, strengthen the standard submodular formulation significantly. We show the lifting problem of the submodular inequalities to be a submodular maximization problem with a special structure solvable by a greedy algorithm, which leads to an easily-computable strengthening by subadditive lifting of the inequalities. Computational experiments on expected utility maximization in capital budgeting show the effectiveness of the new formulation.
Cite this paper
Ahmed, S., & Atamtürk, A. (2009). Maximizing a class of submodular utility functions. Mathematical Programming, 128(1-2), 149–169. https://doi.org/10.1007/s10107-009-0298-1
Ahmed, Shabbir, and Alper Atamtürk. “Maximizing a class of submodular utility functions.” Mathematical Programming, vol. 128, no. 1-2, 2009, pp. 149–69, https://doi.org/10.1007/s10107-009-0298-1.
Ahmed, Shabbir, and Alper Atamtürk. 2009. “Maximizing a class of submodular utility functions.” Mathematical Programming 128 (1-2): 149–69. https://doi.org/10.1007/s10107-009-0298-1.
Ahmed, S. and Atamtürk, A. (2009) ‘Maximizing a class of submodular utility functions’, Mathematical Programming, 128(1-2), pp. 149–169. Available at: https://doi.org/10.1007/s10107-009-0298-1.
@article{ahmed2009maximizing,
title = {{Maximizing a class of submodular utility functions}},
author = {Ahmed, Shabbir and Atamtürk, Alper},
journal = {Mathematical Programming},
volume = {128},
number = {1-2},
pages = {149--169},
year = {2009},
doi = {10.1007/s10107-009-0298-1}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.