Submodular maximization and its generalization through an intersection cut lens

We study a mixed-integer set S:={(x,t)∈{0,1}ⁿ×R:f(x)≥t} arising in the submodular maximization problem, where f is a submodular function defined over {0,1}ⁿ. We use intersection cuts to tighten a polyhedral outer approximation of S. We construct a continuous extension F¯_f of f, which is convex and defined over the entire space Rⁿ. We show that the epigraph epi(F¯_f) of F¯_f is an S-free set, and characterize maximal S-free sets containing epi(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.