algorithm - 持续资源分配/背包问题

Question

我正在尝试创建一个算法来解决以下优化问题，其中每个 x_i 和 B 作为整数，并且所有 f_i 都是单调的非线性函数。对我来说，这看起来像是一个背包或连续资源分配问题。编辑：常数 C 是一个整数

我最初尝试通过比较所有 g_i(x) 的边际成本来解决它，但由于 Cs 取消，这不起作用。我正在做的比较是寻找最小化 g_i(x) - g_i(x - j) 的 i，其中 j 是一个小值。在这种情况下：

g_i(x) - g_i(x - j) = f_i(x) + c - (g_i(x - j) + c)，所以 cs 会抵消。

有谁知道这个的解决方案，或者对如何尝试这个有任何线索？如果有人有关于这个主题的任何文献，我将不胜感激。

谢谢你。

标签： algorithmmachine-learningoptimizationmathematical-optimizationknapsack-problem

Answer 1

所以我们有一些设施可以以成本 C 开放或以成本 0 关闭，并且开放设施为每个额外单元提供服务的边际成本永远不会下降（f_i是凸的）。

如果我们知道哪些设施是开放的，那么当每个设施的下一个单元的所有边际成本大于或等于每个设施的最后一个单元的所有边际成本时，我们就会知道我们有一个最佳分配（正如你所观察到的）。如果函数有一些特殊的形式，可能有更好的方法来做到这一点，但通常我们可以使用二进制搜索来找到让我们满足需求的最小边际成本（每次迭代也使用二进制搜索来确定每个开放设施可以服务）。

相反，如果我们只知道确切的 k 个设施应该是开放的，我们仍然可以对最小边际成本进行二分搜索。我们只需要计算出每个设施在不超过建议边际成本的情况下可以服务多少个单元，然后选择前 k 个。

最后，观察我们可以尝试从 0 到 n 的所有 k 并采取我们找到的最佳解决方案。