Polyhedral results for a class of cardinality constrained submodular minimization problems

Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w, x) is an element of R x {0,1}(n) : w >= f(a'x), e'x <= k} where f : R -> R is a concave function, n and k are positive integers, alpha is an element of R-n is a nonnegative vector, e is an element of R-n is a vector of ones, and x'y denotes the scalar product of vectors x and y of same dimension. A standard linearization approach for P is to exploit the fact that f(a'x) is submodular with respect to the binary vector x. We extend this approach to take the cardinality constraint e'x <= k into account and provide a full description of the convex hull of P when the vector a has identical components. We also develop a family of facet-defining inequalities when the vector a has nonidentical components. Computational results using the proposed inequalities in a branch-and-cut framework to solve mean-risk knapsack problems show significant decrease in both time and the number of nodes over standard methods. (C) 2015 Elsevier B.V. All rights reserved.