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 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. Such problems arise, for instance, in the context of risk-averse capital budgeting under uncertainty and combinatorial auctions. Due to their combinatorial nature, these problems can be formulated as linear mixed 0-1 programs. However, the standard formulation of these problems based on existing submodular inequalities is ineffective for solving them except for very small instances. In this paper, we perform a polyhedral analysis of the 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 show the effectiveness of the new formulation.

Keywords: Expected utility maximization, combinatorial auctions

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation:

Download: [PDF]

Entry Submitted: 04/14/2008
Entry Accepted: 04/14/2008
Entry Last Modified: 04/14/2008

Modify/Update this entry