An exact cutting plane method for k -submodular function maximization
An exact cutting plane method for k -submodular function maximization
复制标题
k子模函数最大化的精确割平面法
DOI：
10.1016/j.disopt.2021.100670
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Küçükyavuz, Simge
中科院分区：
文献类型：
--
作者：
Yu, Qimeng;Küçükyavuz, Simge
子模性的一个自然而重要的推广-k-子模性-适用于具有k个参数的集合函数，并出现在广泛的应用中，如基础设施设计，机器学习和医疗保健。本文研究了具有k-次模目标函数的极大化问题。对于任意k-次模函数的子图，我们提出了有效的线性不等式，即k-次模不等式。这类不等式是著名的次模不等式的一个新的推广。我们表明，最大化一个k-次模函数是等价于解决一个混合整数线性规划指数许多k-次模不等式。使用这种表示的延迟约束生成框架，我们设计的第一个精确算法，这是不是一个完整的枚举方法，解决一般的k-子模极大化问题。我们的计算实验上的多类型的传感器布局问题证明了我们的算法在约束非线性k-次模最大化问题，没有其他紧凑的混合整数线性配方的效率。计算实验表明，该算法的性能明显优于唯一可用的精确解方法-穷举搜索。使用我们的方法，需要13年以上才能解决的问题可以在10分钟内解决。
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.