3/8/18 | 4:15pm | E51-345
Reception to follow.

Alper Atamtürk

Professor
University of California, Berkeley 

Abstract:

This talk has two related parts. Part one is on the maximization of a particular submodular utility function, whereas part two is on its minimization. These problems arise naturally in combinatorial optimization with risk aversion, including estimation of project duration with stochastic task times, in reliability models, multinomial logit models, competitive facility location, combinatorial auctions, robust optimization, portfolio optimization.

In the first part, given a monotone concave univariate function g, two vectors c and d, and a polytope, we consider the discrete optimization problem of finding a vertex of the polytope that maximizes the utility function c'x + g(d'x). The problem is NP-hard for any strictly concave function g even for simple polytopes, such as the uniform matroid, assignment and path polytopes. We will describe a simple 1/2-approximation algorithm for it and 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 improves to 4/5. Although the worst case bounds are tight, computational experiments indicate that the approximation algorithm finds solutions within 1-2% of optimality gap for most instances very quickly and can be considerably faster than the existing alternatives.

In the second part of the talk, we consider a mixed 0-1 conic quadratic optimization problem with indicator variables arising in mean-risk optimization. The indicator variables are often used to model non-convexities such as fixed charges or cardinality constraints. Observing that the problem reduces to submodular function minimization for its binary restriction, we derive three classes of strong convex valid inequalities by lifting the polymatroid inequalities on the binary variables. Computational experiments demonstrate the effectiveness of the inequalities in strengthening the convex relaxations and, thereby, improving the solution times for mean-risk problems with fixed charges and cardinality constraints significantly.

Joint work with Andres Gomez and Hyemin Jeon. The talk is based on the following papers:

http://ieor.berkeley.edu/~atamturk/pubs/_published/or60-2012.pdf
http://ieor.berkeley.edu/~atamturk/pubs/_published/mathprog128-2011.pdf
http://ieor.berkeley.edu/~atamturk/pubs/poly-mip.pdf
http://ieor.berkeley.edu/~atamturk/pubs/conicvub.pdf
http://ieor.berkeley.edu/~atamturk/pubs/vertexoptv2.pdf

Bio:  Alper Atamturk is a Professor of Industrial Engineering and Operations Research at the University of California, Berkeley. He received his Ph.D. from the Georgia Institute of Technology in 1998. His current research interests are in integer programming (conic, mixed, combinatorial), optimization under uncertainty with applications to power systems, portfolio/network design, logistics of production, distribution, transportation systems and treatments for cancer. He serves on the editorial boards of Operations Research, Mathematical Programming Computation, Discrete Optimization, Journal of Risk, and Networks; and has in the past served on the editorial board of Management Science. Dr. Atamturk is a National Security Science & Engineering Faculty Fellow of the US Department of Defense.