Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w,x) : w >= f(a'x), e'x <= k, x in {0,1}^n } where f is a concave function, n and k are positive integers, a is a nonnegative vector, e 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.
Citation
Technical report, ISyE, Georgia Tech
Article
View Polyhedral results for a class of cardinality constrained submodular minimization problems