Выберите N местоположений из списка, чтобы максимизировать общую прибыль из окрестностей выбранных мест.

Question

Из 1000 мест, 250 мест имеют право на установку розетки. Я хочу выбрать 5 мест из этих 250, чтобы максимизировать сумму прибыли из окрестностей выбранных мест, а выходы расположены не менее чем на 5 миль друг от друга. Готовность людей путешествовать из одного места в другое дается (что определяет окрестности этого местоположения)

Я пробовал целое программирование, но имел проблемы с определением целевой функции. Любой метод кластеризации/оптимизации, который может решить эту проблему?

EDIT:

Дано:

• 1000 мест и расстояние по дуге большого круга между любыми двумя точками
• Готовность людей для перемещения из одного места в другое для всех 1000 мест
• 250 правомочных местонахождение

Цель:

Чтобы максимизировать прибыль от 5 кластеров, где каждый кластер содержит выбранное местоположение и все местоположения, откуда люди хотят путешествовать в выбранное место.

Ограничения:

• Всего выбранных местах должны быть 5 и должны быть из 250 подходящих мест
• Выбранные места должны быть не менее 5 миль друг от друга
• Каждое место может принадлежать только один кластер

Answer 1

Если я правильно понимаю вашу проблему правильно, вы хотите следующее:

позволяют переменным Li указать местоположение i. (Я = 1..250)

Пусть Si = {Lj for all j such that distance(Li, Lj) <= 5 miles}

Пусть Ci быть константой, представляющее значение окрестности Li

ограничения являются:

Sum Si <= 1 
Li = 1 or 0 
Sum(Li for all i) == 5 

целевая функция максимизировать Sum(Li*Ci for all i)

Answer 2

ограниченный fu ll перечисление должно сделать для этой проблемы размер:

1. перечисляет все возможные варианты местоположения, не нарушая ограничение «не менее 5 миль». Простая рекурсия, легко распараллеливается.
2. для каждой комбинации из # 1 рассчитайте общее количество мест, «покрытых» макетом, и выберите максимальное значение. Для каждого узла в этих 1000 найдите, какой выход, если кто-либо из узла будет идти, и +1, если какая-либо выходная точка достижима. Легко распараллеливается, снова.
3. Дополнительно. Из тех одинаково хороших предпочитают те, у кого лучшая «балансировка нагрузки».

Проблема вы работаете на это: http://en.m.wikipedia.org/wiki/Quadratic_assignment_problem

Классические эвристики приближающейся эти ветви & связаны, генетический, отжиг. Полное перечисление будет использоваться для проверки того, что эвристика способна эффективно приближаться к глобальному минимуму при небольших размерах проблем.