Раскраска графа ограничений Гуроби - PullRequest
Новая
       13

Раскраска графа ограничений Гуроби

0 голосов
/ 26 октября 2018

Я пытаюсь исправить некоторые ограничения для проблемы окраски Графа, используя networkx и gurobi.Это весь код, который я написал: 

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 ([1,2,3,4,5])
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(1,4)
G.add_edge(1,5)
G.add_edge(2,3)
G.add_edge(2,4)
G.add_edge(3,5)
G.add_edge(4,5)
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()

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

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: 

mdic = gb.Model()
indices = []

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

# binary variable that assing 1.0 to the color associated to the edge and 0.0 to the others

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

# decision variable S i for i ∈ V represents the maximum color in the set of colors assigned to edges incident to vertex i

S_i = []
for u in U:
    S_i.append(mdic.addVar(vtype=gb.GRB.CONTINUOUS, lb = G.degree[u] - 1, ub = K - 1, \
                        name = 'max_color'+str(u)))

# decision variable s_i for i ∈ V represents the minimum color in the set of colors assigned to edges incident to vertex i
s_i = []
for u in U:
    s_i.append(mdic.addVar(vtype=gb.GRB.CONTINUOUS, lb = 0.0, ub = K - G.degree[u], \
                        name='min_color'+str(u)))

mdic.update()

А затем ограничения: 

# 1a- Guarantee that adjacent edges take different colors

for u in U:
    for z in Z: 
        mdic.addConstr(x.sum(u,'*',z) <= 1, name='different_color')


mdic.update()


# 1a- Guarantee that adjacent edges take different colors

for u in U:
    for z in Z:
        mdic.addConstr(x.sum('*',u,z) <= 1, name='different_color')


mdic.update()

# 1b- Guarantee that every edge takes exactly one color
for u,v in G.edges():
    mdic.addConstr(x.sum(u,v) == 1, name='one_color')

mdic.update()

# 1c- Enforce Si to be greater than or equal to the max color assigned to the edges incident to vertex i

expr = 0
for u,v in G.edges():
    for z in Z:       
        expr += z * x[u,v,z]
    mdic.addConstr(S_i[u] >= expr, name='max')
    expr = 0

# 1d- Enforce si to be less than or equal to the min color assigned to the edges incident to vertex i

expr = 0
for u,v in G.edges():
    for z in Z:       
        expr += z * x[u,v,z]
mdic.addConstr(s_i[u] <= expr, name='min')
expr = 0

mdic.update()

, где Z - набор доступных цветов. 

# objective function
expr20=0
for u in U:
    expr20+=(S_i[u] - s_i[u] - G.degree[u] + 1)
mdic.setObjective(expr20, gb.GRB.MINIMIZE)

mdic.update()

mdic.optimize()

Ограничения

Первыйодна - целевая функция, 1a-1d - ограничения, а другие - ub и lb.

1 Ответ

0 голосов
/ 30 октября 2018

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

Ограничение (1a) на вашем скриншоте гарантирует, что смежные ребра имеют разные цвета.Однако, с вашей реализацией этого ограничения может случиться так, что входящий и исходящий фронт будут иметь одинаковый цвет.Например, ребро {1,3} и {3,5} могут иметь одинаковый цвет.Это потому, что вы обрабатываете входящие и исходящие края отдельно.В качестве решения вы можете объединить ваши циклы в один: 

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

Ограничение (1c) также учитывает только исходящие ребра в вашей реализации.Например, S_i[5] не будет назначен, потому что он имеет только входящие ребра.Это должно работать: 

expr = 0
for u,v in G.edges():
    for z in Z:       
        expr += z * x[u,v,z]
    mdic.addConstr(S_i[u] >= expr, name='max')
    mdic.addConstr(S_i[v] >= expr, name='max')
    expr = 0

То же самое касается ограничения (1d).Более того, строка addConstr находится вне цикла, но это может быть просто ошибкой форматирования: 

expr = 0
for u,v in G.edges():
    for z in Z:       
        expr += z * x[u,v,z]
    mdic.addConstr(s_i[u] <= expr, name='min')
    mdic.addConstr(s_i[v] <= expr, name='min')
    expr = 0
...