| - | ||||
|
|
Maximizing a Class of Submodular Utility Functions
Shabbir Ahmed(sahmed 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 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 | |
|
||||