Сумма условного ограничения PuLP (на основе переменной) - PullRequest
Новая
       86

Сумма условного ограничения PuLP (на основе переменной)

1 голос
/ 19 апреля 2020

Я пытаюсь оптимизировать проблему, когда переменная решения (X) является двоичной матрицей NxN. Я нахожу проблему с выполнением одного из ограничений задачи.

Первое ограничение подразумевает, что сумма X в каждой строке должна быть == 1. (Покрыто)

Второе ограничение (которое я не могу заставить работать) требует, чтобы для тех столбцов, где диагональ == 1, сумма X должно быть> = 2. Я сгенерировал следующее ограничение в PuLP: 

for j in W:
    prob +=  sum(X[i][j] for i in W if X[j][j] >= 1) >= 2

PuLP означает, что решение имеет статус «Невозможно». ¿Что я делаю не так? ¿Это ограничение не может быть реализовано в PuLP?

По сути, пример матрицы решений, которая охватывает предыдущие требования, будет: 

[0,0,0,1,0]
[0,0,0,1,0]
[0,0,0,1,0]
[0,0,0,0,1]
[0,0,0,0,1]

1 Ответ

1 голос
/ 19 апреля 2020

Это среда линейного программирования , и поэтому могут использоваться только линейные функции . Произвольные python -выражения вроде:

  • if
  • abs
  • min

не передаются в решатель, но оцениваются априори (среда моделирования / решатель этого не видят), что обычно приводит к мусору.

Такие вещи должны быть линеаризованы . Некоторые фреймворки могут предоставлять некоторые из них автоматически, но в целом это очень сложная задача (поскольку большинство линеаризаций невозможно без c предположений, определяемых моделью!).

( cvxpy для пример поддерживает переформулировку abs и min, будучи совместимым с некоторым набором правил)

Здесь вам нужно будет сделать это самостоятельно.

Если я правильно понял задачу, это выглядит так:

  • двоичная матрица
  • каждая строка суммируется с 1
  • каждая сумма столбцов является неограниченной, за исключением столбца, где 1 равен диагональная позиция -> тогда эта сумма столбца имеет нижнюю границу 2

Пример решения: 

D!    D!

1  0  0  0   sum = 1 
1  0  0  0   sum = 1
0  0  1  0   sum = 1
0  0  1  0   sum = 1

sums
2  0  2  0

Мы можем линеаризовать выражение как: 

for column in columns:
    (1-diag_elem_of_column) * bigM + sum(column) >= 2

    <-> 

    (1-diag_elem_of_column) * 2 + sum(column) >= 2

Это классическая c big-M формулировка, где есть некоторая двоичная индикаторная переменная (diagonal-element), активирующая / деактивирующая некоторое линейное выражение, используя некоторую большую константу big-M . Эта большая константа делает эти подходы зависимыми от допущений, но в вашем случае эта большая константа не обязательно должна быть очень большой (а ужесточение важно для разрыва целостности -> лучше для решателя).

Идея is:

  • Enforce sum(column) >= 2 за исключением при отсутствии попадания по диагональному элементу
  • при наличии попадания по диагональному элементу -> (1-diag_elem_of_column ) * 2 = 0 -> сумма ограничена и равна> = 2 (так как нам нужно получить 2 ненулевых значения в оставшихся переменных)
  • Когда нет попадания диагонального элемента -> (1- diag_elem_of_column) * 2 = 2> = 2 (сумма оставшихся элементов равна свободна -> нет ограничений, поскольку мы уже выполнили минимум 2)

В коде это может выглядеть как (не проверено): 

# assumption: square-matrix
# assumption: X[row][col] storage-order

N = 5

for diag_element_index, col in enumerate(N):
  prob += (1 - X[diag_element_index][col]) * 2 + sum([X[row][col] for row in range(N)]) >= 2
...