Maximizing a Class of Utility Functions Over the Vertices of a Polytope

• 成果类型: Article
• 署名作者: Atamturk, Alper; Gomez, Andres
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1570
• 发表日期: 2017
• 页码: 433-445
• 关键词: interior-point methods; function subject; optimization; approximations; PROTECTION; series

摘要

Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c'x + g(d'x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic times, in reliability models, in multinomial logit models and in robust optimization. We show that the problem is NP-hard for any strictly concave function g even for simple polytopes, such as the uniform matroid, assignment and path polytopes; and propose a 1/2-approximation algorithm for it. We discuss improvements for special cases where g is the square root, log utility, negative exponential utility and multinomial logit probability function. In particular, for the square root function, the approximation ratio is 4/5. We also propose a 1.25-approximation algorithm for a class of minimization problems in which the maximization of the utility function appears as a subproblem. Although the worst-case bounds are tight, computational experiments indicate that the suggested approach finds solutions within 1%-2% optimality gap for most of the instances, and can be considerably faster than the existing alternatives.