Journal Article

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

Atamtürk, Alper, Gómez, Andrés

2017

Overview

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.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Algorithms / Analysis / Apexes / Approximation / assortment / Combinatorial analysis / combinatorial optimization / conic quadratic optimization / Logit models / Mathematical functions / Maximization / METHODS / multinomial logit / Operations research / Optimization / PERT / Polytopes / reliability / Reliability analysis / robust optimization / Statistical analysis / Stochastic models / submodularity / Utility functions / value-at-risk