Maximizing a class of submodular utility functions |
| |
Authors: | Shabbir Ahmed Alper Atamt��rk |
| |
Institution: | 1. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332, USA 2. Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA, 94720-1777, USA
|
| |
Abstract: | Given a finite ground set N and a value vector ${a \in \mathbb{R}^N}$ , we consider optimization problems involving maximization of a submodular set utility function of the form ${h(S)= f \left(\sum_{i \in S} a_i \right ), S \subseteq 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|