# An Exact Cutting Plane Method for k-submodular Function Maximization

arXiv: https://arxiv.org/abs/2008.00988 · HTML: https://mlsanity.com/paper/2008.00988/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2020.

## Built on by (most cited first, 1 of 1)

- [k-Submodular Interdiction Problems under Distributional Risk-Receptiveness and Robustness: Application to Machine Learning](https://mlsanity.com/paper/2406.13023/) (2024)

## Abstract (arXiv)

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.