An exact cutting plane method for k-submodular function maximization

DOI10.1016/J.DISOPT.2021.100670MaRDI QIDQ2067498zbMATH OpenOpenAlexFDO

Authors Qimeng Yu, Simge Küçükyavuz

Publication date 18 January 2022

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.00988

zbMATH Keywords

cutting plane\(k\)-submodular maximizationmulti-type sensor placement

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

Recommendations

• An efficient branch-and-cut algorithm for submodular function maximization
• \(k\)-submodular maximization with two kinds of constraints
• Improved approximation algorithms for \(k\)-submodular function maximization
• On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1953186 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A characterization of bisubmodular functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A faster strongly polynomial time algorithm for submodular function minimization
• A polyhedral approach to bisubmodular function minimization
• A two-stage stochastic programming approach for influence maximization in social networks
• Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information
• An analysis of approximations for maximizing submodular set functions—I
• An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions
• Bisubmodular Function Minimization
• Data Mining with Decision Trees
• Directed submodularity, ditroids and directed submodular flows
• Hub location as the minimization of a supermodular set function
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Maximizing \(k\)-submodular functions and beyond
• Maximizing a class of submodular utility functions
• Maximizing a class of submodular utility functions with constraints
• Maximizing bisubmodular and \(k\)-submodular functions
• On distributionally robust chance constrained programs with Wasserstein distance
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Polymatroids and mean-risk minimization in discrete optimization
• Probabilistic partial set covering with an oracle for chance constraints
• Pseudomatroids
• Sequence Independent Lifting for the Set of Submodular Maximization Problem
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• Towards minimizing \(k\)-submodular functions
• Understanding machine learning. From theory to algorithms

Cited in

(4)

• \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• An efficient branch-and-cut algorithm for submodular function maximization
• Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization

This page was built for publication: An exact cutting plane method for \(k\)-submodular function maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2067498)