View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document