定义CVXPY变量以解决图形着色问题 [英] Define CVXPY variables for graph coloring problem

问题描述

我正在尝试解决最小的图形着色问题.我正在尝试使用cvxpy将其解决为 mip .我正在遵循此url中描述的解决方案的概述:

I’m trying to solve the minimum graph coloring problem. I’m trying to solve it as an mip using cvxpy. I’m following the outline of a solution described in this url:

https://manas.tech/blog/2010/09/16/modelling-graph-coloring-with-integer-linear-programming.html

我不确定我是否了解如何正确创建cvxpy变量以及如何定义约束.我在下面提供了示例输入数据，以及创建变量，约束和目标函数，解决问题和返回解决方案的代码.

I’m not sure if I’m understanding how the cvxpy variables are created correctly, and how I’m defining my constraints. I have sample input data below along with the code creating the variables, constraints, and objective function, solving the problem and the solution returned.

我认为此输入的正确答案应该是:

I think the correct answer for this input should be:

‘2 1\n0 1 0 0’

这是要求的最少颜色数为2，除节点1外，所有节点都为相同颜色.

That is that the minimum number colors required is 2 and all nodes are the same color except node 1.

我正在创建w变量以计算所用颜色的数量:

I’m creating the w variable to count the number of colors used:

w = cvxpy.Variable(j, boolean=True)

我想我正在做的是创建一个长度等于节点数的二进制变量.这样的想法是，您可以使用的最大颜色数将等于节点数.所以最大的颜色:

What I think I am doing is creating a binary variable of length equal to the number of nodes. The idea being that the maximum number of colors you could use would be equal to the number of nodes. So maximum colors:

w=[1,1,1,1]

我将w描绘成一个二进制变量，例如一个列表，其中值可以是0或1，表示该颜色是否被任何节点使用.

I’m picturing w as binary variable like a list where the values can be 0 or 1 indicating if that color is used by any of the nodes.

然后创建目标函数:

obj=cvxpy.sum(w,axis=0)

我想我正在对行中的条目求和，因此，例如:

I think I’m summing the entries in the row which are 1, so for example:

w=[1,1,0,0]

obj=2

我还创建了一个变量x来指示给定节点的颜色:

I also create a variable x to indicate the color of a given node:

x = cvxpy.Variable((j,int(first_line[0])), boolean=True)

我将其描述为带有二进制值的二维数组，其中列表示节点，行表示颜色.

I’m picturing this as a 2 dimensional array with binary values, where the column indicates the node and the row indicates the color.

因此，例如，如果节点0的颜色为0，节点1的颜色为1，节点2的颜色为2，节点3的颜色为2，我可以想象x看起来像:

So for example if node 0 had color 0, node 1 had color 1, node 2 had color 2, and node 3 had color 2, I would imagine x to look like:

[[1,0,0,0],[0,1,0,0],[0,0,1,1],[0,0,0,0]]

有人可以告诉我我是否正确理解并正确创建了选择变量?我也理解并正确创建了目标函数吗?这就是我描述目标函数的方式是否与我创建目标函数的方式相匹配?而且，对于我定义的其他约束或我的代码提出的任何建议，将不胜感激.我正在学习线性编程，并且试图理解cvxpy语法.

Can someone please tell me if I’m understanding and creating my selection variables correctly? Also do I understand and have I created my objective function correctly? That is does the way I’ve described my objective function match the way I’ve created it? And any input on the other constraints I’ve defined or my code would be greatly appreciated. I’m learning linear programing and I’m trying to understand cvxpy syntax.

样本数据:

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'

推荐答案

您的解决方案几乎是正确的.这里的主要问题是变量x的定义.根据博客文章

Your solution is almost correct. The main problem here is the definition of variable x. According to the blog post

x_ {ij}变量，当且仅当节点i被分配了颜色j时才会为真

x_{ij} variables that will be true if and only if node i is assigned color j

表示x的大小为(节点nb，颜色nb).

which indicates that the size of x is (nb of nodes, nb of colors).

在您的代码中，您需要将x更改为:

In your code you need to change x to:

x = cvxpy.Variable((node_count, j), boolean=True)

，然后是第二和第三个约束:

and then, consequently, the second and third constraints:

# for adjacent nodes at most 1 node has color
diff_col = []

for edge in edges:
    for k in range(j):
        diff_col += [
            x[edge[0],k]+x[edge[1],k]<=1
        ]


# w is upper bound for color of node x<=w

upper_bound = []

for i in range(node_count):
    for k in range(j):
        upper_bound += [
            x[i,k]<=w[k]
        ]

然后输出是预期的，即使用2种颜色:节点1的一种颜色和节点0、2、3的另一种颜色(因为它们不相邻).

Then the output is as expected i.e. 2 colors are used: one color for node 1 and another color for nodes 0, 2, 3 (because they are not adjacent).

这篇关于定义CVXPY变量以解决图形着色问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！