algorithm - 从列表中选择 N 个位置以最大化总和，具有最小距离约束

Question

我想从 250 个地点中选择 5 个地点，以最大化预期利润，使每个地点之间的最小距离为 5 英里。给出了与每个位置和它们之间的距离相关的预期利润。

我试图找出这是否是一个标准问题。应用过滤器来获得解决方案似乎是计算密集型的。我一直在探索模拟退火等方法，以获得足够好的解决方案。

Answer 1

由于您使用的是大圆距离，因此有几种可能性可以提供一些质量保证：欧几里得图的近似方案和整数规划。前者在理论上更具可扩展性，但后者给出了精确的最优值，并且在假设求解器可用的情况下更容易实现。（当然，您总是可以做一些特别的事情。）由于您的位置很少，这就是我要描述的那个。

我将通过将您的问题表述为整数程序来简要解释整数程序。

maximize profit1 * x1 + profit2 * x2 + ... + profit250 * x250
subject to
x1 + x2 + ... + x250 = 5  (select exactly 5 localities)
for every pair of localities {i, j} less than 5 miles from each other,
    xi + xj <= 1
x1, x2, ..., x250 in {0, 1}

变量的含义xi是如果选择了locality则为1，如果没有选择ilocality则为0 i。

您需要编写一个小子程序，以将该程序以首选格式传达给您最喜欢的求解器。要查找求解器，请搜索“MIP 求解器”；有与多种语言绑定的免费和商业产品。尝试获得一个支持 clique 切割的工具（我知道商业 CPLEX 和免费的 GLPK 都可以）。如果没有，那没关系；您可以自己实现 Bron–Kerbosch 以生成形式的约束

xa + xb + ... + xz <= 1

a, b, ..., z彼此相距5英里的地方在哪里。