Optimization Online


Maximizing a class of utility functions over the vertices of a polytope

Alper Atamturk(atamturk***at***berkeley.edu)
Andres Gomez(a.gomez***at***berkeley.edu)

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 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.

Keywords: PERT, value-at-risk, multinomial logit, reliability, assortment, submodularity, combinatorial optimization, conic quadratic optimization, robust optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Robust Optimization

Category 3: Stochastic Programming

Citation: BCOL Research Report 15.05, IEOR, UC Berkeley

Download: [PDF]

Entry Submitted: 09/24/2016
Entry Accepted: 09/25/2016
Entry Last Modified: 09/24/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society