algorithm - 需要一种算法来找到元素子集中的最小成本

Question

我正在尝试找到一种最优算法，该算法可以在覆盖所有元素的同时找到元素总和最低的最大子集。

例如:- 假设 A B C 是零售商，W X Y Z 是产品，目标是尽量减少访问次数并降低价格。

    A    B    C
W   4    9    2  
X   1    3    4 
Y   9    3    9
Z   7    1    1 

So it appears my top two choices are 
a) B:{XYZ} - 7   C:{W} - 2
b) C:{WXZ} - 7   B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9. 

这个问题看起来和顶点覆盖等线性规划算法类似，但是我想不出正确的一个。

更新:

看来我需要添加一个额外的变量。介绍 t。如果访问最少的零售商和下一个最少的零售商的成本 > t，则选择下一个前者。

Continuing with the example.

say t = 5,

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7   C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7   C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7   C:{W} - 2 is picked

真的，我只是感兴趣是否已经有适合这种模式的算法。我不可能是第一个需要这种优化的人。

Answer 1

您有两个目标 - 1. 最大限度地降低产品的总成本，以及 2. 最大限度地减少访问的商店数量。 (@btilly 的评论正确地展示了两个相互竞争的解决方案。)

在这些类型的整数规划问题中，多个目标相当普遍。 See MCDM .要解决此问题，您需要有两种 类型的费用(您目前只有一种。)

1. 从零售商 r(您已指定)购买产品 p 的成本 C_rp
2. 访问零售商的成本:C_r

直觉:如果 C_r 非常高，那么我们将从一家零售商处购买所有产品。如果 C_r 很小，那么我们会去多家零售商，从最便宜的零售商那里购买。

您的问题可以建模为“Assignment Problem”的变体。另外，如果您需要更多引用资料，请阅读所谓的fixed-charge transportation problems (FCTP)。 (访问零售商一次需要支付固定费用。)

接下来是整数规划公式:

决策变量

  Binary
  X_rp = if product p is purchased from retailer r, 0 otherwise 
  Y_r = 1 if retailer r is visited, 0 otherwise 

目标函数

 Min C_rp X_rp + C_r Y_r

约束

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer)

接下来，我们需要确保 Y_r 为 1，即使对于该零售商的 X_rp 之一为 1。通常情况下，我们会求助于大 M 方法，但在这个问题上它更容易。

X_rp <= Y_r  for all p, for all r. 

如果任何 X 变量变为 1，则迫使 Y_r 变为 1。模型将支付价格 C_r。

要求解，您可以使用任何 LP 求解器。好消息是问题具有完整性属性，这意味着即使使用线性规划求解技术，整数解也会自然出现。

希望对您有所帮助。