An Exact Cutting Plane Method for k-submodular Function Maximization

A natural and important generalization of submodularity -- k-submodularity -- applies to set functions with k arguments and appears in a broad range of applications, such as infrastructure design, machine learning, and healthcare. In this paper, we study maximization problems with k-submodular objective functions. We propose valid linear inequalities, namely the k-submodular inequalities, for the hypograph of any k-submodular function. This class of inequalities serves as a novel generalization of the well-known submodular inequalities. We show that maximizing a k-submodular function is equivalent to solving a mixed-integer linear program with exponentially many k-submodular inequalities. Using this representation in a delayed constraint generation framework, we design the first exact algorithm, that is not a complete enumeration method, to solve general k-submodular maximization problems. Our computational experiments on the multi-type sensor placement problems demonstrate the efficiency of our algorithm in constrained nonlinear k-submodular maximization problems for which no alternative compact mixed-integer linear formulations are available. The computational experiments show that our algorithm significantly outperforms the only available exact solution method -- exhaustive search. Problems that would require over 13 years to solve by exhaustive search can be solved within ten minutes using our method.