Я пытаюсь решить проблему минимальной окраски графа. Я пытаюсь решить это как mip , используя cvxpy. Я следую плану решения, описанному в этом URL:
https://manas.tech/blog/2010/09/16/modelling-graph-coloring-with-integer-linear-programming.html
Я не уверен, понимаю ли я, как правильно создаются переменные cvxpy, и как я определяю свои ограничения. У меня есть пример входных данных ниже вместе с кодом, создающим переменные, ограничения и целевую функцию, решение проблемы и возвращаемое решение.
Я думаю, что правильный ответ для этого ввода должен быть:
‘2 1\n0 1 0 0’
То есть минимально необходимое количество цветов равно 2, и все узлы одного цвета, кроме узла 1.
Я создаю переменную w для подсчета количества используемых цветов:
w = cvxpy.Variable(j, boolean=True)
То, что я думаю, я делаю, это создание двоичной переменной длины, равной количеству узлов. Идея заключается в том, что максимальное количество цветов, которое вы можете использовать, будет равно количеству узлов. Так что максимум цветов:
w=[1,1,1,1]
Я представляю w как двоичную переменную, подобную списку, значения которого могут быть 0 или 1, указывая, используется ли этот цвет любым из узлов.
Затем для создания целевой функции:
obj=cvxpy.sum(w,axis=0)
Я думаю, что я суммирую записи в строке, которые равны 1, например:
w=[1,1,0,0]
obj=2
Я также создаю переменную x, чтобы указать цвет данного узла:
x = cvxpy.Variable((j,int(first_line[0])), boolean=True)
Я представляю это как двумерный массив с двоичными значениями, где столбец указывает узел, а строка указывает цвет.
Так, например, если узел 0 имел цвет 0, узел 1 имел цвет 1, узел 2 имел цвет 2, а узел 3 имел цвет 2, я бы предположил, что x будет выглядеть так:
[[1,0,0,0],[0,1,0,0],[0,0,1,1],[0,0,0,0]]
Может кто-нибудь сказать мне, правильно ли я понимаю и создаю свои переменные выбора? Также я понимаю и правильно ли я создал свою целевую функцию? То есть способ, которым я описал свою целевую функцию, совпадает с тем, как я ее создал? И любая информация о других ограничениях, которые я определил или мой код, будет принята с благодарностью. Я изучаю линейное программирование и пытаюсь понять синтаксис cvxpy.
Пример данных:
input_data
'4 3\n0 1\n1 2\n1 3\n'
# parse the input
lines = input_data.split('\n')
first_line = lines[0].split()
node_count = int(first_line[0])
edge_count = int(first_line[1])
edges = []
for i in range(1, edge_count + 1):
line = lines[i]
parts = line.split()
edges.append((int(parts[0]), int(parts[1])))
edges
# Output:
[(0, 1), (1, 2), (1, 3)]
# solution using cvxpy solver
import numpy as np
import cvxpy
from collections import namedtuple
# selection variables
# binary variable if at least one node is color j
j=int(first_line[0])
# w=1 if at least one node has color j
w = cvxpy.Variable(j, boolean=True)
# x=1 if node i is color j
x = cvxpy.Variable((j,int(first_line[0])), boolean=True)
# Objective function
# minimize number of colors needed
obj=cvxpy.sum(w,axis=0)
# constraints
# 1 color per node
node_color=cvxpy.sum(x,axis=1)==1
# for adjacent nodes at most 1 node has color
diff_col = []
for edge in edges:
for k in range(node_count):
diff_col += [
# x[edge[0],k]+x[edge[1],k]<=1
x[k,edge[0]]+x[k,edge[1]]<=1
]
# w is upper bound for color of node x<=w
upper_bound = []
for i in range(j):
for k in range(j):
upper_bound += [
x[k,i]<=w[i]
]
# constraints
constraints=[node_color]+diff_col+upper_bound
# solving problem
# cvxpy must be passed as a list
graph_problem = cvxpy.Problem(cvxpy.Minimize(obj), constraints)
# Solving the problem
graph_problem.solve(solver=cvxpy.GLPK_MI)
value2=int(graph_problem.solve(solver=cvxpy.GLPK_MI))
# taken2=[int(i) for i in selection.value.tolist()]
# taken2=[int(i) for i in w.value.tolist()]
taken2=[int(i) for i in w.value.tolist()]
# prepare the solution in the specified output format
output_data2 = str(value2) + ' ' + str(0) + '\n'
output_data2 += ' '.join(map(str, taken2))
output_data2
'1 0\n0 0 0 1'