Почему мое ограничение cplex замедляет работу моей модели? - PullRequest
Новая
       110

Почему мое ограничение cplex замедляет работу моей модели?

0 голосов
/ 13 июля 2020

У меня есть модель MILP, которую я пытаюсь решить. У меня есть новая константа, которую я объяснял ранее на этот вопрос Мое новое ограничение:

if: y [(i, j, k)] == 1

затем: y [(j, i, k + 1)], y [(j, i, k + 2)], y [(j, i, k + 3)], y [(j, i, k + 4)], y [(j, i, k + 5)], y [(j, i, k + 6)], y [(j, i, k + 7)], y [(j, i, k + 8) == 0.

Я наложил это ограничение на свой режим следующим образом: 

        mdl.add_constraints((y[(i,j,k)]+y[(j,i,k+1)] +y[(j,i,k+2)]+y[(j,i,k+3)]
       +y[(j,i,k+4)]+y[(j,i,k+5)]+y[(j,i,k+6)]+y[(j,i,k+7)]+y[(j,i,k+8)]  )<=1 for k in K4 for i in T for j in T )

Но запуск моей модели с этой новой константой приводит к очень медленному решению моей модели . Что-то не так с моим ограничением или есть способ изменить его таким образом, чтобы моя модель могла быть решена быстрее?

Редактировать: Когда я задаю свое условие таким образом, запускается время быстро, но модель не учитывает ограничение «если то, то» в решениях. мой код: 

        for i in T:
            for j in T:
                if i!=j:
                    for k in K4:
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+1)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+2)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+3)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+4)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+5)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+6)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+7)]==0))
                        mdl.add( mdl.if_then( y[(i,j,k)]==1 , y[(j,i,k+8)]==0))

1 Ответ

0 голосов
/ 15 июля 2020

относительно второй формулировки: хорошо ли я понимаю, что Cplex дает вам решение, в котором нарушается if_then, то есть y [i, j, k] равно 1, а любые другие y [j, i, k + .. ] не 0? Если так, это странно и заслуживает расследования. Как сказал Тим, выгрузите LP, используя Model.export_as_lp(), и мы посмотрим.

Кроме того, у меня есть два замечания по этой альтернативной формулировке:

  • ваш 'if constraint' в if_then на самом деле представляет собой некоторую переменную, равную 1, поэтому это можно переписать с использованием ограничения индикатора. равным нулю может быть выполнено в одном ограничении, указав, что их сумма равна 0. Таким образом, я бы переписал внутренний оператор в альтернативной формулировке как: 

    mdl.add_indicator(y[i,j,k],
                  mdl.sum(y[j,i,k+d] for d in range(9)) ==0))

Это означает, что всякий раз, когда переменная y [i, j, k] равно 1, тогда все переменные y [j, i, k + d] равны нулю (при условии, что они двоичные)

В отличие от if_then, ограничения индикатора не генерируют промежуточные двоичные переменные , поэтому эта формулировка создает модель меньшего размера. Опять же, если эта формулировка сгенерирует решение, которое ее нарушает, тогда отправьте нам LP-файл для исследования.

...