Я пытаюсь закодировать ограничения для задачи раскраски графа с помощью CVXPY.Я довольно новичок в смешанно-целочисленном программировании (MIP), и у меня возникли некоторые трудности при определении ограничений.У меня есть входные данные, такие как список «ребер» ниже.Где каждый кортеж в списке - это ребро, которое начинается на одном узле и заканчивается на другом.Например, первое ребро начинается в узле «0» и заканчивается в узле «1».
Я хотел бы указать следующие ограничения:
каждый узел может иметьтолько один цвет.
вершины, имеющие одно ребро, должны иметь разные цвета.
каждый узел должен иметь хотя бы один цвет.
Целевой функцией будет количество используемых цветов.
Для переменной выбора я хочу указать цвет, который принимает каждый узел.
Я используюcolors массив для умножения на переменную выбора и затем суммирования для каждого узла, чтобы выбрать цвет для узла и указать, что каждый узел может иметь только один цвет.
Я получаю ошибку ниже.Правильно ли я строю переменную выбора?
Кроме того, это похоже на большую работу, кто-нибудь видит более простой способ сделать это?Или кто-нибудь знает пример решения проблемы раскраски графа с помощью CVXPY?
Еще одна вещь, если я перенесу массив цветов, ошибка исчезнет.
Входные данные:
ребра
[(0, 1), (1, 2), (1, 3)]
код:
# selection variable
# 4 is the number of nodes
selection = cvxpy.Variable(4, boolean=True)
# array for colors
colors = np.array([[1,0,0,0],
[0,1,0,0],
[0,0,1,0],
[0,0,0,1],
[1,1,0,0],
[1,1,1,0],
[1,1,1,1],
[0,1,1,1],
[0,0,1,1],
[1,0,1,0],
[0,1,0,1],
[0,1,1,0],
[1,1,0,0],
[0,0,0,0]])
# each node can only have one color constraint
one_color = cvxpy.sum(selection * colors, axis=0) == 1
ошибка:
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-18-b22226c89a2f> in <module>()
1 # each node can only have one color constraint
2
----> 3 one_color = cvxpy.sum(selection * colors, axis=0) == 1
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/expressions/expression.py in cast_op(self, other)
47 """
48 other = self.cast_to_const(other)
---> 49 return binary_op(self, other)
50 return cast_op
51
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/expressions/expression.py in __mul__(self, other)
385 return cvxtypes.multiply_expr()(self, other)
386 elif self.is_constant() or other.is_constant():
--> 387 return cvxtypes.mul_expr()(self, other)
388 else:
389 warnings.warn("Forming a nonconvex expression.")
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/atoms/affine/binary_operators.py in __init__(self, lh_exp, rh_exp)
41
42 def __init__(self, lh_exp, rh_exp):
---> 43 super(BinaryOperator, self).__init__(lh_exp, rh_exp)
44
45 def name(self):
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/atoms/atom.py in __init__(self, *args)
42 self.args = [Atom.cast_to_const(arg) for arg in args]
43 self.validate_arguments()
---> 44 self._shape = self.shape_from_args()
45 if len(self._shape) > 2:
46 raise ValueError("Atoms must be at most 2D.")
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/atoms/affine/binary_operators.py in shape_from_args(self)
107 """Returns the (row, col) shape of the expression.
108 """
--> 109 return u.shape.mul_shapes(self.args[0].shape, self.args[1].shape)
110
111 def is_atom_convex(self):
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/utilities/shape.py in mul_shapes(lh_shape, rh_shape)
140 lh_old = lh_shape
141 rh_old = rh_shape
--> 142 lh_shape, rh_shape, shape = mul_shapes_promote(lh_shape, rh_shape)
143 if lh_shape != lh_old:
144 shape = shape[1:]
~/anaconda2/envs/py36/lib/python3.6/site-packages/cvxpy/utilities/shape.py in mul_shapes_promote(lh_shape, rh_shape)
107 if lh_mat_shape[1] != rh_mat_shape[0]:
108 raise ValueError("Incompatible dimensions %s %s" % (
--> 109 lh_shape, rh_shape))
110 if lh_shape[:-2] != rh_shape[:-2]:
111 raise ValueError("Incompatible dimensions %s %s" % (
ValueError: Incompatible dimensions (1, 4) (14, 4)