# Submodular maximization and its generalization through an intersection cut lens

 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 $$\mathsf{F}$$ of $$f$$, which is convex and defined over the entire space $$\mathbb{R}^n$$. We show that the epigraph of $$\mathsf{F}$$ is an $$\mathcal{S}$$-free set, and characterize maximal $$\mathcal{S}$$-free sets including the epigraph. 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, 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.