Улучшить ограничение, добавив производительность Gurobi python

У меня есть этот набор переменных решения

for p in projects:
    for u in Skills:
        for v in Skills:
            for i in Experts:
                for j in Experts:
                    if u!=v:
                        if i >= j:
                            z[(i,u,j,v,p)]=m.addVar(vtype=GRB.BINARY,name='Z')
                            y[(i,u,j,v,p)]=m.addVar(vtype=GRB.BINARY,name='Y')

и мне нужно добавить ограничения для каждого, как показано ниже

#Constraint 6: To linearize the product of two decision variables linear  
#z_{i_u_p_j_v_p} <= V_i_u_p + V_i_u_p -1

for p in projects:
    for u in Skills:
        for v in Skills:
            for i in Experts:
                for j in Experts:
                    if u!=v:
                        if i >= j:
                            m.addConstr( z[i,u,j,v,p] <= Viup[i,u,p] )
                            m.addConstr( z[i,u,j,v,p] <= Viup[j,v,p] )
                            m.addConstr( z[i,u,j,v,p] >= Viup[i,u,p] + Viup[j,v,p] -1 )

m.update()

#Constraint 7:                           
for p1 in projects:
    for u1 in Skills:
        for v1 in Skills:
            for i1 in Experts:
                for j1 in Experts:
                    if u1!=v1:
                        if i1 >= j1:
                            m.addConstr( y[i1,u1,j1,v1,p1]  <= z[i1,u1,j1,v1,p1] )
                            m.addConstr( y[i1,u1,j1,v1,p1]  <= Wp[p1] )
                            m.addConstr( y[i1,u1,j1,v1,p1]  >= z[i1,u1,j1,v1,p1]+ Wp[p1] - 1 )

Это занимает огромное количество времени, эксперты находятся в диапазоне (30), а навыки в диапазоне (10). Может ли кто-нибудь помочь мне добавить их более эффективно?

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

— 18.03.2019 17:30

@ Jean-FrançoisFabre Спасибо за ваш быстрый ответ, но я не мог четко понять, что вы имели в виду. Не могли бы вы помочь больше

— 18.03.2019 17:40

Если вы не используете очень старую версию Gurobi, вам следует удалить вызов Model.update().

— 18.03.2019 18:48

python constraints linear-programming gurobi

18.03.2019 17:25

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

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

130

Ответы 1

Не уверен, что вы можете уменьшить сложность, но вы можете уменьшить время внутренних циклов.

во-первых, сравните u != v на внешнем уровне, не выполняйте внутренние циклы только для того, чтобы увидеть, что делать нечего
во-вторых, отсортируйте свой экспертный список и не обрабатывайте 2 «половинки», просто отбросьте половину итераций со сравнением.
затем тайник ваши условные переменные, чтобы избежать их многократного вычисления

вот так (для последнего условия)

sorted_experts = sorted(Experts)
for p1 in projects:
    for u1 in Skills:
        for v1 in Skills:
            if u1!=v1:  # do this check here
                for ei,i1 in enumerate(sorted_experts):
                   for ej in range(ei+1,len(sorted_experts)):
                        j1 = sorted_experts[ej]  # no need to test for indices
                        ycond = y[i1,u1,j1,v1,p1] # cache your condition variables
                        zcond = z[i1,u1,j1,v1,p1]
                        w = Wp[p1]
                        m.addConstr( ycond <= zcond )
                        m.addConstr( ycond <= w )
                        m.addConstr( ycond >= zcond + w - 1 )

Почему бы не сделать эту итерацию один раз при создании словарей y и z, а затем выполнить последующую итерацию по ключам z?

— 18.03.2019 18:51

но ключи y и z зависят от всех 4 переменных цикла.

— 18.03.2019 20:16

18.03.2019 18:19