Polymatroids and mean-risk minimization in discrete optimization

We study discrete optimization problems with a submodular mean-risk minimization objective. For-0-1 problems a linear characterization of the convex lower envelope is given. For mixed 0-1 problems we derive an exponential class of conic quadratic valid inequalities. We report computational experiments on risk-averse capital budgeting problems with uncertain returns. (c) 2008 Elsevier B.V. All rights reserved.