论文标题
一种空间分支和结合方法，以最大化非分支单调连续下函数
A Spatial Branch-and-Bound Approach for Maximization of Non-Factorable Monotone Continuous Submodular Functions
论文作者
论文摘要
与假设目标函数和约束的许多连续全局优化方法相反，我们研究了如何找到不可分配的问题的全球最大解决方案，重点是特定类别的问题。具体而言，我们开发了一种非降低连续下函数的方法。我们表征了此类功能的射仪，并开发了一种切割平面算法，该算法使用射仪的凸壳的近似方法找到了近似的解和边界。我们还测试了一种空间分支和结合方法，该方法利用近似切割平面算法形成外部近似值并获得子级别的上限，并将我们的方法与最先进的商业求解器进行比较。主要结果是，对于某些问题，属性的性质比以上性性更有用。
In contrast to the many continuous global optimization methods that assume the objective function and constraints are factorable, we study how to find globally maximal solutions to problems that are not factorable, focusing on a particular class of problems. Specifically, we develop a method for non-decreasing continuous submodular functions subject to constraints. We characterize the hypograph of such functions and develop a cutting plane algorithm that finds approximate solutions and bounds using an approximation of the convex hull of the hypograph. We also test a spatial branch-and-bound approach that utilizes the approximate cutting plane algorithm to form an outer approximation and obtain upper bounds for a sub-rectangle and compare our method with a state-of-the-art commercial solver. The main result is that for some problems the property of submodularity is more useful than factorability.
