  


Maximizing a Class of Submodular Utility Functions
Shabbir Ahmed (sahmedisye.gatech.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 riskaverse capital budgeting under uncertainty, competitive facility location, and combinatorial auctions. These problems can be formulated as linear mixed 01 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 mixedinteger 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 easilycomputable 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  