Given a finite ground set
N and a value vector
a Î \mathbbRN{a \in \mathbb{R}^N}, we consider optimization problems involving maximization of a submodular set utility function of the form
h(S) = f (åi Î S ai ), S Í N{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.
Mathematics Subject Classification (2000) 90C57 – 91B16 – 91B28
Keywords Expected utility maximization – Combinatorial auctions – Competitive facility location – Submodular function maximization – Polyhedra
The research of the first author has been supported, in part, by Grant # FA9550-08-1-0117 from the Air Force Office of Scientific
Research. The research of the second author has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.
The second author is grateful for the hospitality of the Georgia Institute of Technology, where part of this research was
conducted.