2021/03/07 by Qimeng Yu, Si̇mge Küçükyavuz, Yu, Qimeng +1 · 2 citations
Computer Science · Business, Management and Accounting · #Complexity and Algorithms in Graphs #Facility Location and Emergency Management #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2103.04398
We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of f(a^\top x), where f is a univariate concave function, a is a non-negative vector, and x is a binary vector of appropriate dimension. Such minimization problems frequently appear in applications that involve risk-aversion or economies of scale. We propose three classes of strong valid linear inequalities for this convex hull and specify their facet conditions when a has two distinct values. We show how to use these inequalities to obtain valid inequalities for general a that contains multiple values. We further provide a complete linear convex hull description for this mixed-integer set when a contains two distinct values and the cardinality constraint upper bound is two. Our computational experiments on the mean-risk optimization problem demonstrate the effectiveness of the proposed inequalities in a branch-and-cut framework.