论文标题
双歧外体方法最小化的双向函数
A Polyhedral Approach to Bisubmodular Function Minimization
论文作者
论文摘要
我们考虑双向物镜功能的最小化问题。我们提出了有效的不平等，即多双膜不等式，并提供了双次函数凸面的凸壳的完整线性描述。此外，我们开发了一种基于多双膜不等式的约束双子型最小化的切割平面算法。我们对鲁棒耦合传感器放置中最小化子问题的计算实验表明，我们的算法可以解决高度非线性问题，而这些问题不接受紧凑的混合构成线性配方。
We consider minimization problems with bisubmodular objective functions. We propose valid inequalities, namely the poly-bimatroid inequalities, and provide a complete linear description of the convex hull of the epigraph of a bisubmodular function. Furthermore, we develop a cutting plane algorithm for constrained bisubmodular minimization based on the poly-bimatroid inequalities. Our computational experiments on the minimization subproblem in robust coupled sensor placement show that our algorithm can solve highly non-linear problems that do not admit compact mixed-integer linear formulations.
