纸浆仅显示__不明变量

Question

我正在尝试在虚拟上使用纸浆图形着色问题。为了解决问题，我们需要为每个节点分配一种颜色，以使任何相邻节点都不共享共同的颜色，同时最小化所使用的颜色总数。

这是一个虚拟的数据：

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的或工具，我可以找到一个解决方案：

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

旁注：虽然状态表明最佳，但我觉得可以使用颜色更少。

，但是，当使用类似的方法时使用纸浆，我看不到任何解决方案。

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

对我出错的任何帮助，将不胜感激。

Answer 1

因此，您的配方中有2个问题会导致您的问题。首先，len（set（...））是非线性操作。当您向问题添加表达式时，它们需要表示为线性方程。您的约束存在相同的问题。您的逻辑是正确的，但是您不能将x！= y传递给求解器，这也是非线性的。您必须查看如何用线性表达式制定这些逻辑以重新制定。

请注意，您可以在纸浆中始终print（模型），以查看建造的内容，如果您打印出来，则没有任何有用的东西……谁知道如何评估这些内容并将其放入模型中。我怀疑它们一次在施工时进行评估，您将琐碎的表达式投入到X = true或其他内容之类的模型中，而不会遇到错误。

因此，这是通过线性表达式对问题的替代表述。 this_color！= that_color约束有点复杂，并且依赖于指示变量来启用一个或构造。

我不使用Google的工具或工具太多，但是在这些概念之上，它主要只是句法糖，所以也许有一种方法可以优雅地陈述它或工具，但是到了一天结束时，类似的事情正在开始生成并传递给求解器。

在图理论中可能会更好地表达这种情况，但是对于简单的ILP来说，这很好。 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]