Fractional 0–1 programming and submodularity
Fractional 0–1 programming and submodularity
复制标题
DOI：
10.1007/s10898-022-01131-5
复制
发表时间：
2020-12
影响因子：
1.8
通讯作者：
Shaoning Han;A. Gómez;O. Prokopyev
中科院分区：
文献类型：
--
作者：
Shaoning Han;A. Gómez;O. Prokopyev
在这篇文章中，我们研究了多重比率分数0-1规划，这是一大类难的组合优化问题。特别地，在一些相对温和的假设下，我们给出了条件的完整刻画，这些条件确保了单比函数是子模的。然后，我们用分类优化和设施选址问题来说明我们的理论结果，并讨论了在所考虑的应用环境中保证子模块的实际情况。在这种情况下，可以通过简单的贪婪算法找到多比率分数0-1规划的近最优解。
In this note we study multiple-ratio fractional 0–1 programs, a broad class of-hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0–1 programs can be found via simple greedy algorithms.