An exact cutting plane method for k-submodular function maximization

Qimeng Yu, Simge Küçükyavuz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number100670
JournalDiscrete Optimization
Volume42
DOIs
StatePublished - Nov 2021
Externally publishedYes

Keywords

  • Cutting plane
  • k-submodular maximization
  • Multi-type sensor placement

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An exact cutting plane method for k-submodular function maximization'. Together they form a unique fingerprint.

Cite this