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

Alper Atamtürk () and Andrés Gómez ()
Additional contact information
Alper Atamtürk: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720
Andrés Gómez: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720

Operations Research, 2017, vol. 65, issue 2, 433-445

Abstract: 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 𝒩𝒫 -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.

Keywords: PERT; value-at-risk; multinomial logit; reliability; assortment; submodularity; combinatorial optimization; conic quadratic optimization; robust optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2016.1570 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:65:y:2017:i:2:p:433-445

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().