Submodular maximization and its generalization through an intersection cut lens
研究次模最大化问题中混合整数集的交集割，构造凸延拓并设计混合离散牛顿算法高效计算，推广到布尔超立方体上的次模-超模函数，在最大割、伪布尔最大化等问题的MIP求解中验证效果。
We study a mixed-integer set $$\mathcal {S}:=\{(x,t) \in \{0,1\}^n \times \mathbb {R}: f(x) \ge t\}$$ arising in the submodular maximization problem, where f is a submodular function defined over $$\{0,1\}^n$$ . We use intersection cuts to tighten a polyhedral outer approximation of $$\mathcal {S}$$ . We construct a continuous extension $$\bar{\textsf{F}}_f$$ of f, which is convex and defined over the entire space $$\mathbb {R}^n$$ . We show that the epigraph $${{\,\textrm{epi}\,}}(\bar{\textsf{F}}_f)$$ of $$\bar{\textsf{F}}_f$$ is an $$\mathcal {S}$$ -free set, and characterize maximal $$\mathcal {S}$$ -free sets containing $${{\,\textrm{epi}\,}}(\bar{\textsf{F}}_f)$$ . We propose a hybrid discrete Newton algorithm to compute an intersection cut efficiently and exactly. Our results are generalized to the hypograph or the superlevel set of a submodular-supermodular function over the Boolean hypercube, which is a model for discrete nonconvexity. A consequence of these results is intersection cuts for Boolean multilinear constraints. We evaluate our techniques on max cut, pseudo Boolean maximization, and Bayesian D-optimal design problems within a MIP solver.