  


Maximizing a class of utility functions over the vertices of a polytope
Alper Atamturk(atamturkberkeley.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 NPhard for any strictly concave function g even for simple polytopes, such as the uniform matroid, assignment and path polytopes; and propose a 1/2approximation 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.25approximation 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 12% optimality gap for most of the instances, and can be considerably faster than the existing alternatives. Keywords: PERT, valueatrisk, 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  