Maximizing a Class of Submodular Utility Functions

Shabbir Ahmed (sahmedisye.gatech.edu)
Alper Atamturk (atamturkberkeley.edu)

Abstract: Given a finite ground set N and a value vector a in R^N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S)= f (sum_{i in S} a_i), S subseteq N, where f is a strictly concave, increasing, differentiable function. This 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.

Keywords: Expected utility maximization, competitive facility location, combinatorial auctions, polyhedra

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Forthcoming in Mathematical Programming

Download: [PDF]

Entry Submitted: 04/14/2008
Entry Accepted: 04/14/2008
Entry Last Modified: 07/03/2009

Modify/Update this entry