English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the polyhedral convex hull structure of a mixed-integer set whicharises in a class of cardinality-constrained concave submodular minimizationproblems. 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 anon-negative vector, and $x$ is a binary vector of appropriate dimension. Suchminimization problems frequently appear in applications that involverisk-aversion or economies of scale. We propose three classes of strong validlinear inequalities for this convex hull and specify their facet conditionswhen $a$ has two distinct values. We show how to use these inequalities toobtain valid inequalities for general $a$ that contains multiple values. Wefurther provide a complete linear convex hull description for thismixed-integer set when $a$ contains two distinct values and the cardinalityconstraint upper bound is two. Our computational experiments on the mean-riskoptimization problem demonstrate the effectiveness of the proposed inequalitiesin a branch-and-cut framework.

Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints