Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints.
- Resource Type
- Article
- Authors
- Yu, Qimeng; Küçükyavuz, Simge
- Source
- Mathematical Programming. Sep2023, Vol. 201 Issue 1/2, p803-861. 59p.
- Subject
- *ECONOMIES of scale
*CONCAVE functions
- Language
- ISSN
- 0025-5610
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 ⊤ 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. [ABSTRACT FROM AUTHOR]