Journal
MATHEMATICAL PROGRAMMING
Volume 128, Issue 1-2, Pages 149-169Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-009-0298-1
Keywords
Expected utility maximization; Combinatorial auctions; Competitive facility location; Submodular function maximization; Polyhedra
Categories
Funding
- Air Force Office of Scientific Research [FA9550-08-1-0117]
- National Science Foundation [DMI0700203]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [0758234] Funding Source: National Science Foundation
Ask authors/readers for more resources
Given a finite ground set N and a value vector a is an element of R-N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S) = f(Sigma(i is an element of S)a(i)), S subset of N, where f is a strictly concave, increasing, differentiable function. This utility 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available