数值优化问题-在产品和场景之间进行选择所需的算法

Question

我正在尝试为我有许多不同产品的情况找到最佳算法，每个产品有 4 个场景（彼此不相关）以及它们在该场景中的成本和收入。例如：

然后我想找到最佳方案组合，以便在低于给定成本限制的情况下 return 获得最多收入。例如。我希望它 return:

我考虑过创建每一种可能的组合并计算每种组合的成本和收入（并且只选择成本 < £x 的最大收入）但是组合太多了，因为我有大约 120 种产品和 5 个场景（更多组合比宇宙中的原子数还要多）。

有人知道可以对最佳场景做出最佳猜测的算法吗？

非常感谢

Answer 1

这是著名的运筹学问题“The Knapsack Problem”的一个版本。

一般来说，这是一个 "NP-Hard" 问题，因此目前还没有已知的有效和最佳解决方法。（而且你的版本比基本问题更难。）

如果你还想要最优解，可以使用整数规划optimizer/solver求解如下模型：

maximize sum( Revenue_ik * I_ik ) over all product-scenarios i,k  # maximize revenue

s.t.
sum( Cost_ik * I_ik ) over all product-scenarios i,k <= BUDGET  # Total cost should be lower than the budget
sum( I_ik ) over all scenarios k <= 1 for all products i   # Choose at most 1 scenario per product (we can make it equals if we *have* to choose)

I_ik in {0, 1} # Decision variables are binary: not choose or choose

也就是说，还有其他方法可以找到好的解决方案。例如，您可以使用启发式方法和 local-search 方法，例如：

按 revenue/cost 排序选项，贪婪地总是选择最 cost-effective 可能的产品 x 场景。
得到初步的解决方案后，通过同时交换2个产品的场景来检查是否有改进的可能。即，降低自己的成本，同时增加他人的成本。

此外，通常存在 pseudo-polynomial 算法来解决此类问题。对于您的情况，（除非我遗漏了什么）以下动态编程关系成立：

f(i, w) = max revenue possible using products 0...i, which costs at most w.

f(i, w) = max{ f(i-1, w) , f(i-1, w-Cost_ik) + Revenue_ik for each scenario k for product i }
f(-1, w) = 0 # base case
f(i, w) = -INFINITY if w < 0 # base case

如果您的最大预算 W 合理，该算法可以非常有效地找到最优解。例如，这是一个 Python 片段，它以 275 的预算最佳地解决了您当前的实例：

cache = {}
chosen = {}

revenue = [[0, 200, 240, 250], [0, 207, 257, 398], [0, 115, 400, 350], [0, 240, 300, 340]]
cost = [[0, 30, 40, 60], [0, 35, 38, 70], [0, 110, 160, 240], [0, 80, 200, 350]]
scenarios = [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]
BUDGET = 275

def f(i, w):
    if w < 0:
        return -10000000
    if i == -1:
        return 0
    if (i, w) in cache:
        return cache[(i, w)]

    vals = [f(i - 1, w - cost[i][k]) + revenue[i][k] for k in scenarios[i]]
    max_val = max(vals)
    chosen_scenario = vals.index(max_val)
    chosen[(i, w)] = chosen_scenario
    cache[(i, w)] = max_val
    return max_val

print(f(3, BUDGET))
result = []
W = BUDGET
for i in reversed(range(len(scenarios))):
    chosen_scenario = chosen[(i, W)]
    result.append(chosen_scenario)
    W -= cost[i][chosen_scenario]

result.reverse()
print(result)

输出：

1038
[2, 3, 2, 0]

最大。可能的收入是 1038，依次为每个产品选择方案 2、3、2 和 0。

数值优化问题-在产品和场景之间进行选择所需的算法

Numerical Optimisation Question - Algorithm required to choose between products and scenarios

algorithm

optimization

numeric