我正在尝试使用PuLP来解决虚拟图的着色问题。为了解决这个问题，我们需要为每个节点分配一种颜色，这样任何相邻节点都不会共享相同的颜色，同时最小化使用的颜色总数。
这是一个虚拟的数据:
edges = [('A', 'H'), ('A', 'B'), ('H', 'G'), ('H', 'K'), ('H', 'J'),
('H', 'I'), ('G', 'F'), ('G', 'K'), ('F', 'E'), ('K', 'E'),
('K', 'J'), ('K', 'D'), ('I', 'J'), ('I', 'D'), ('D', 'C'),
('D', 'B')]
nodes = set(sum(edges, ()))
n_nodes = len(nodes)
使用Google的OR-Tools，我可以找到一个解决方案:
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# Set decision variables
var = {}
for node in nodes:
var[node] = model.NewIntVar(0, n_nodes-1, node)
# Set objective
model.Minimize(len(set(var.values())))
# Add constraints
for edge in edges:
model.Add(var[edge[0]] != var[edge[1]])
# Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
print('Status: Optimal n')
for node in nodes:
print(f"{node}: {solver.Value(var[node])}")
的回报:
Status: Optimal
C: 0
A: 5
H: 4
K: 2
F: 1
E: 0
D: 1
J: 0
I: 2
B: 0
G: 3
边注:虽然状态显示最佳，但我觉得可以使用的颜色较少。
然而，当对PuLP使用类似的方法时，我看不到任何解决方案。
from pulp import *
model = LpProblem("coloring", LpMinimize)
# Set decision variables
var = {}
for node in nodes:
var[node] = LpVariable(node, lowBound=0, upBound=n_nodes-1, cat=LpInteger)
# Set objective
model += len(set(var.values()))
# Add constraints
for edge in edges:
model += var[edge[0]] != var[edge[1]]
# Solve
status = model.solve()
print(f'Status: {LpStatus[status]} n')
for variable in prob.variables():
print(f"{variable.name}, {v.varValue}")
的回报:
Status: Optimal
__dummy, None
如果您能告诉我哪里出了问题，我将不胜感激。
所以你的配方中有两个问题导致了你的问题。首先，len(set(...))是一个非线性操作。当你在问题中添加表达式时，它们需要被表示为线性方程。你的约束也有同样的问题。你的逻辑是正确的，但是你不能把x != y传递给求解器，那也是非线性的。你必须考虑如何用线性表达式来重新表述这些逻辑片段。
注意，你总是可以在纸浆中print(model)来看看建造了什么，如果你打印你的，没有任何有用的东西出现…谁知道这些东西是如何被评估并放进模型的。我怀疑它们在构造时被评估一次，而你正在将琐碎的表达式扔到模型中，如x = True或其他东西，而没有得到错误。
这是线性表达式问题的另一种表述。this_color != that_color约束有点复杂，它依赖于一个指示符变量来启用非此即彼的构造。
我不太使用谷歌的OR工具，但它主要是这些概念之上的语法糖，所以也许有一种方法可以在OR工具中优雅地陈述它，但在一天结束时，像这样的东西被生成并传递给求解器。
这可能是一个更好的制定在图论中,但这对简单的独立工作。3种颜色是答案。
from pulp import *
edges = [('A', 'H'), ('A', 'B'), ('H', 'G'), ('H', 'K'), ('H', 'J'),
('H', 'I'), ('G', 'F'), ('G', 'K'), ('F', 'E'), ('K', 'E'),
('K', 'J'), ('K', 'D'), ('I', 'J'), ('I', 'D'), ('D', 'C'),
('D', 'B')]
nodes = set(sum(edges, ()))
n_nodes = len(nodes)
M = n_nodes + 1
model = LpProblem("coloring", LpMinimize)
# Set decision variables
color = {}
for node in nodes:
color[node] = LpVariable(node, lowBound=1, cat=LpInteger)
num_colors = LpVariable('count', cat = LpInteger)
color_diff = {}
for idx, edge in enumerate(edges):
color_diff[edge] = LpVariable(str(idx), cat=LpBinary)
# Set objective
# model += len(set(var.values()))
model += num_colors # seek to minimize the maximal color index
# Add constraints
# get the max value of the colors...
for node in nodes:
model += num_colors >= color[node]
# ensure the adjacent nodes are different color
for edge in edges:
# force one or the other of these to be true, based on the color_diff
# variable, which is just a binary indicator
model += -M * color_diff[edge] + 1 <= color[edge[0]] - color[edge[1]]
model += -M * (1-color_diff[edge]) + 1 <= color[edge[1]] - color[edge[0]]
# Solve
status = model.solve()
print(f'Status: {LpStatus[status]} n')
for variable in model.variables():
print(f"{variable.name}, {variable.varValue}")
Result - Optimal solution found
Objective value: 3.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.01
Time (Wallclock seconds): 0.01
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01
Status: Optimal
0, 1.0
1, 0.0
10, 0.0
11, 1.0
12, 0.0
13, 1.0
14, 0.0
15, 0.0
2, 0.0
3, 0.0
4, 0.0
5, 0.0
6, 1.0
7, 1.0
8, 0.0
9, 0.0
A, 2.0
B, 1.0
C, 1.0
D, 3.0
E, 1.0
F, 3.0
G, 1.0
H, 3.0
I, 2.0
J, 1.0
K, 2.0
count, 3.0
[Finished in 96ms]