A spatial branch-and-bound approach for maximization of non-factorable monotone continuous submodular functions
In contrast to the many continuous global optimization methods that assume the objective function
and constraints are factorable, we study how to find globally maximal solutions to problems that are
not factorable, focusing on a particular class of problems. Specifically, we develop a method for
non-decreasing continuous submodular functions subject to constraints. We characterize the
hypograph of such functions and develop a cutting plane algorithm that finds approximate solutions
and bounds using an approximation of the convex hull of the hypograph. We also test a spatial
branch-and-bound approach that utilizes the approximate cutting plane algorithm to form an outer
approximation and obtain upper bounds for a sub-rectangle and compare our method with a
state-of-the-art commercial solver. The main result is that for some problems the property of
submodularity is more useful than factorability.