Sequence independent lifting for a set of submodular maximization problems

• 成果类型: Article
• 署名作者: Shi, Xueyu; Prokopyev, Oleg A.; Zeng, Bo
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01801-y
• 发表日期: 2022
• 页码: 69-114
• 关键词: valid inequalities; knapsack-problems; utility-functions; expected utility; minimization; MODEL; RISK

摘要

We study the polyhedral structure of a mixed 0-1 set arising from the submodular maximization problem, given by P = ((w, x) is an element of R x (0, 1)(n) : w <= f (x), x is an element of X), where submodular function f (x) is represented by a concave function composed with an affine function, and X is the feasible region of binary variables x. For X = (0, 1)(n), two families of facet-defining inequalities are proposed for the convex hull of P through restriction and lifting using submodular inequalities. When X involves multiple disjoint cardinality constraints, we propose a new class of facet-defining inequalities for the convex hull of P through multidimensional sequence independent lifting. The derived polyhedral results not only strengthen and generalize some existing developments in the literature, but are also linked to the classical results for the mixed 0-1 knapsack and single-node flow sets. Our computational study on a set of randomly generated submodular maximization instances demonstrates the superiority of the proposed facet-defining inequalities within a branch-and-cut scheme.