Дискретная оптимизация Python с линейной целевой функцией - PullRequest
Новая
       34

Дискретная оптимизация Python с линейной целевой функцией

0 голосов
/ 09 мая 2018

У меня есть несколько очков (N). Для этих точек у меня есть матрица расстояний D (N * N). Также у меня есть данные атрибута для этих точек A (1 * N). Я хочу выбрать фиксированное количество точек (K), чтобы sum of attribute is maximum, в то время как расстояние между выбранными точками лежит в диапазоне (min_dis, max_dis).

Я пытался реализовать эту задачу оптимизации в Pulp с N = 10, K = 3.

A = [300,436,234,11,23,897,439,56,123,432]. 

    import pulp
    import numpy as np

    inds = range(10)

    #create a vector x which will only accept value 0,1
    x = pulp.LpVariable.dicts('x', inds, lowBound = 0,upBound = 1,cat = pulp.LpInteger)

    my_lp_problem = pulp.LpProblem("My LP Problem", pulp.LpMaximize)

    #sum of x should be equal to no of points I want (which is 3)
    my_lp_problem += sum([x[store] for store in inds]) == 3

    #maximize dot product A.x (which would be sum of attributes)
    my_lp_problem += sum([A[point] * x[point] for point in inds])

Однако я не могу наложить ограничения на матрицу расстояний. Что будет примерно так: 

    np.multiply(x,D).max() < max_dis and np.multiply(x,D).min() > min_dis

Поскольку я не мог найти, как использовать max (), min () и умножение матрицы в вещах. Я понимаю, что это имеет линейную целевую функцию, в то время как ограничения не являются линейными. Я также исследовал scipy.optimize, но поскольку x может содержать только 0 и 1, а не непрерывную переменную, я начал с целлюлозы. Любая помощь приветствуется!

1 Ответ

0 голосов
/ 09 мая 2018

Я не вижу здесь нелинейностей.Если я правильно понял задачу, вы могли бы:

  • ввести aux-vars P[i,j] in {0,1}
    • точка, которую я выбрал (предположим,: S[i] = 1) & выбрана точка j ПОДРАЗДЕЛЕНИЯ P[i,j] = 1
    • с удалением симметрии, этот набор имеет размер C(N,2)
    • , который вы можетеинтерпретируйте его как индикатор активной пары
  • сформулируйте вышеприведенное соотношение:
    • P[i,j] >= S[i] + S[j] - 1 (для всех i; для всех j)
    • предупреждение: мы только формулируем подтекст (не эквивалентность);не обязательно заинтересованы в другом направлении
  • добавить ограничивающее ограничение для всех расстояний C (N, 2) (эквивалентно ограничению максимального значения; общая переформулировка):
    • P[i,j] * DIST[i,j] <= max-dist (для всех i; для всех j)
    • это аффинное ограничение (DIST и max-dist являются константами)

Примечаниевышеизложенное несколько неформально в отношении размерности P (плоское 1D против 2D) и для всех i;для всех j .Детали зависят от этого решения и от того, удаляются ли симметрии.

...