Умножение между логическими значениями в линейном программировании (python, Pulp library) - PullRequest
Новая
       24

Умножение между логическими значениями в линейном программировании (python, Pulp library)

0 голосов
/ 23 апреля 2019

Я ищу решение задачи линейного программирования, и мне нужно определить следующие ограничения: 

gji = 1 if guest j is seated at table i, 0 otherwise 
gki = 1 if guest k is seated at table i, 0 otherwise  
pjik = gij * gik = 1 if guest j AND guest k are seated at table i, 0 otherwise

Я написал первые два кострейна (используя библиотеку Pulp), но я не знаю, как представить умножение gji*gki

Мой код: 

Gji = LpVariable.matrix("Gji",(range(0,number_guest),range(0,number_table)),lowBound=0, upBound=1, cat='binary')

Gki = LpVariable.matrix("Gki",(range(0,number_guest),range(0,number_table)),lowBound=0, upBound=1, cat='binary')

for row in range (0,number_guest):
    prob += lpSum(Gji[row])<=1
    prob += lpSum(Gji[row])>=1

for columns in range (0,number_table):
    prob += lpSum(np.matrix(Gji).T[columns].tolist()) <= a

Как мне написать costrain для Pjki?

1 Ответ

2 голосов
/ 24 апреля 2019

Всегда сначала формулируйте правильную математическую модель, прежде чем внедрять ее в PuLp.

Let 

g(i,k) = 1 if guest i sits at table k
         0 otherwise

и 

p(i,j,k) = 1 if guests i and j sit at table k
           0 otherwise

Сначала вам понадобятся некоторые ограничения присваивания: 

sum(i, g(i,k)) <= capacity(k)  for all k
sum(k, g(i,k)) = 1             for all i

Двоичное умножение 

p(i,j,k) = g(i,k) * g(j,k)

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

p(i,j,k) <= g(i,k)
p(i,j,k) <= g(j,k)
p(i,j,k) >= g(i,k)+g(j,k)-1
p(i,j,k) ∈ {0,1}

Обычно нам не нужны все эти переменные и уравнения, но это зависит от деталей модели.Наверняка мы должны рассмотреть только i<j.Интересно, что эта формулировка настолько тесна, что мы можем ослабить p (i, j, k), чтобы быть непрерывным между 0 и 1: они будут автоматически целочисленными.

Это математическое описание легко транскрибируется в Python / Pulp.Вы, вероятно, должны переделать свой код Python, поскольку он содержит некоторые бессмысленные вещи.Некоторые подсказки:

  • двоичные переменные уже имеют границы 0 и 1
  • Pulp может создавать ограничения на равенство (запись <= и> = ограничений глупа)
  • попытатьсясделать вещи более читабельными (ближе к математическому представлению)
  • для другого подхода см. wedding.py
...