从列表中选择N个位置，以最小距离约束最大化总和 [英] Select N locations from list to maximize sum, with min distance constraint

问题描述

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

I want to select 5 localities out of 250 locations, to maximize expected profit such that minimum distance between each locality is 5 miles. Expected profit associated with each location and distance between them is given.

我试图找出这是否是一个标准问题。应用过滤器得出解决方案似乎需要大量计算。我一直在探索模拟退火等方法来达到足够好的解决方案。

I was trying to find out if this is a standard problem. Applying filters to arrive at the solution seems computationally intensive. I have been exploring methods like simulated annealing to reach at a good enough solution.

推荐答案

由于您使用的是大圆距，有两种方法可以提供一定的质量保证：欧几里得图的逼近方案和整数编程。从理论上讲，前者具有更高的可伸缩性，但后者给出了精确的最优值，并且在假定有求解器可用的情况下更容易实现。 （当然，您总是可以做一些特别的事情。）由于您的位置太少，所以我将描述这个位置。

Since you're using great-circle distances, there are a couple possibilities that provide some quality guarantee: approximation schemes for Euclidean graphs, and integer programming. The former is in theory more scalable, but the latter gives exact optima and is a lot easier to implement assuming that a solver is available. (Of course, you could always do something ad hoc.) Since you have so few locations, that's the one I'll describe.

我将简要介绍整数程序。

I'll explain integer programs briefly by formulating your problem as one.

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 的含义是，如果选择位置 i ，则为1；如果选择位置<，则为0。没有选择code> i 。

The meaning of variable xi is that it's 1 if locality i is selected and 0 if locality i is not selected.

您需要编写一个小的子程序，以将该程序与您最喜欢的求解器进行通信。其首选格式。要查找求解器，请搜索 MIP求解器；有绑定到多种语言的免费和商业产品。尝试获得一种支持集团削减的方法（我知道商业CPLEX和免费的GLPK可以做到）。如果没有，那没关系；您可以自己实现Bron–Kerbosch，以生成以下形式的约束

You'll need to write a small subroutine to communicate this program to your favorite solver in its preferred format. To find a solver, search for "MIP solver"; there are free and commercial offerings with bindings to a variety of languages. Try to get one that supports clique cuts (I know the commercial CPLEX and the free GLPK do). If it doesn't, that's OK; you can implement Bron–Kerbosch yourself to generate constraints of the form

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

其中 a，b，...，z 彼此之间相距5英里以内的地区。

where a, b, ..., z are localities each within 5 miles of one another.

这篇关于从列表中选择N个位置，以最小距离约束最大化总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！