аюсь исправить некоторые ограничения для проблемы окраски графа, используя networkx и gurobi. Для каждого i ∈ V определим следующий набор интервалов. Каждый интервал [l, u] ∈ Ii представляет возможную пару минимального цвета l и максимального цвета u для набора ребер, инцидентных вершине i. Также для каждого k∈K мы представляем множество интервалов для вершины i ∈ V, которые включают в себя цвет k, следующим образом:

Переменная интервалов

Это весь код, который я написал:

import networkx as nx
import gurobi as gb
from itertools import combinations, chain
import pygraphviz as pygv
import os
import matplotlib.pyplot as plt
from IPython.display import SVG, display

Создание графика, добавление узлов и ребер и двух списков.

G = nx.Graph()
G.add_nodes_from ([0,1,2,3,4])
G.add_edge(0,1)
G.add_edge(0,2)
G.add_edge(0,3)
G.add_edge(0,4)
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,4)
G.add_edge(3,4)
U = list(G.nodes)
K = G.number_of_edges()
Z = []

Создание списка с цветами. Предположим, что K = {0, 1,. , , , K - 1} и K ≤ | E |

def nrofCol():
    Z.clear()
    z = 0
    while z < K - 1:
        Z.append(z)
        z = z+1
    return Z

Z = nrofCol()
Z

здесь я определяю значение интервала (l, u), создавая два списка со всеми цветами.

u = []
l = []

for z in Z:
    u.append(Z[z])
    l.append(Z[z])

Я буду список кортежей

I = []
for z in Z:
    for u in range (z, len(Z)):
        I.append(tuple((z, u)))

добавление атрибута цвета к каждому краю

for colored_arc in ((u,v,z) for u,v in G.edges() for z in Z):
    G[colored_arc[0]][colored_arc[1]][colored_arc[2]] = colored_arc

и добавил переменные в модель, используя Gurobi:

Переменная у

indices = []

for u,v in G.edges(): 
    for z in Z:
        indices.append((u,v,z))

x = mdic.addVars(indices, vtype = gb.GRB.BINARY)

indices2 = []

for u in G.nodes(): 
    for i in range(0,len(I)): 
        indices2.append(tuple((u,I[i])))

for u in U:
    y = mdic.addVars(indices2, vtype = gb.GRB.BINARY)

mdic.update()

Ограничения:Ограничения и целевая функция

Ограничения 2a- Убедитесь, что каждое ребро принимает ровно один цвет

for u,v in G.edges():

        mdic.addConstr(x.sum(u,v) == 1, name='one_color')

mdic.update()

2b- Выберите ровно один интервал (из набора допустимых интервалов) для каждой вершины.

for u in U:       
    mdic.addConstr(y.sum(u) == 1, name='used')

mdic.update()

2c- Гарантируйте, что не только смежные ребра принимают разные цвета, но и ребра, падающие на вершину, берут цвета из набора цветов, включенных в интервал, выбранный для этой вершины.

for u in U:
    for z in Z: 
        mdic.addConstr((x.sum(u,'*',z) + x.sum('*',u,z)) <= y.sum(u,I), name='different_colors')

mdic.update()

целевая функция

expr=0
for u in U:
    for i in range(0,len(I)):
        a = [i[1] for i in I][i]
        b = [i[0] for i in I][i]
        expr += (a - b - G.degree[u] + 1) * y[u,I[i]]
mdic.setObjective(expr, gb.GRB.MINIMIZE)

mdic.update()
mdic.optimize()

Используя этот код, модель неосуществима. Я знаю, что переменная x и ограничения 2a определены правильно. Я не уверен насчет переменной y, других ограничений и целевой функции. Как я могу изменить это?