空间成本最小化算法的最佳设计

Question

我正在处理一组 L 地块和一组 C 县。每个地块 L_i 花费 m 美元，占地 b 英亩。每个县 C_i 需要 n 英亩的地块。假设现在，如果分配给他们的最后一块土地“超出”了他们的能力，这些县不关心获得多于 n 英亩的土地。最后，L_i 必须在 C_i 的 x 英里范围内'考虑分配给 C_i.

的质心

我设计了一个分配算法来解决这个问题，使得 C_i 达到 n 英亩，同时最小化成本米。然而，该设计的计算量非常大。令 L_c 为 x 英里内的地块 C_i。我的算法按成本升序对 L_c 进行排序，分配第一个 n 英亩，然后移动到下一个县。

关于如何提高效率的任何想法？是否有针对此类分配问题设计的既定算法？

Answer 1

这道题特别难。即使没有“到质心的距离”限制，问题也会减少到 SUBSET-SUM 即 NP-Complete（并且添加距离限制不会改变这一点）。简短的、非正式的证明是，如果你想解决 SUBSET-SUM 的一个实例，并作为 oracle 解决这个问题，你可以使 C_1 想要目标子集和 [=24] =] 想要休息。也就是说，您找不到一种有效的算法来完美准确地解决这个问题。话虽如此，您可以获得 相当不错 的算法相当快，牺牲解决方案的准确性以大幅加快速度。

解决方案的想法与您的类似，除了您可以使用一些 BST 来查找未选择的最大尺寸但仍不超过 C_i 限制的土地，直到没有额外的包裹溢出C_i。然后，只需用稍微大一点的包裹替换您选择的包裹之一，这样您就可以达到或超过您的配额（或者如果更容易的话，再拿一个）。这将为其他城市留下尽可能多的可用土地，同时仍能满足 C_i 的配额。然后，继续前往下一个城市。

您可以尝试使用某种形式的整数单纯形来解决更好的近似问题，但我不建议沿着这条路走下去。很抱歉告诉你一个坏消息，但你不会很快找到任何令人满意的 100% 准确的高效算法:(

Answer 2

我认为这可以表述为赋值问题的一个版本。作为实验，我用所有随机数据为此制定了一个 MIP（Mixed-Integer 编程）模型。

看起来像：

 min sum(allowed(c,p),cost(p)*x(c,p)) 
 sum(allowed(c,p),x(c,p)) <= 1                 for all parcels p 
 sum(allowed(c,p),area(p)*x(c,p)) >= minacres  for all counties c
 x(c,p) ∈ {0,1}

备注：

c : 县
p : 地块
allowed(c,p) 是允许的分配（即在距离内）
x(c,p) 是二元决策变量（赋值）

有 100 个县和 1000 个地块，很难找到经过验证的最佳解决方案。但是如果我们能在达到差距（最佳解决方案和最佳解决方案之间的差异）时早一点停下来，那么：

 5% gap reached after 1   seconds
 4%                   1.5
 3%                   6
 2%                   275

空间成本最小化算法的最佳设计

Best design for spatial cost-minimizing algorithm

algorithm

optimization

spatial