Optimization Online


Maximizing a Class of Submodular Utility Functions

Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Alper Atamturk (atamturk***at***berkeley.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society