PuLP求解图着色问题仅返回__dummy变量无有效解怎么办

尝试使用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)

可正常运行的OR-Tools参考实现 #

同逻辑下使用Google OR-Tools可正常输出求解结果，实现代码如下：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# 定义决策变量
var = {}
for node in nodes:
    var[node] = model.NewIntVar(0, n_nodes-1, node)

# 定义目标函数
model.Minimize(len(set(var.values())))

# 添加相邻节点异色约束
for edge in edges:
    model.Add(var[edge[0]] != var[edge[1]])

# 求解
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

补充说明：虽然求解状态显示为Optimal，但实际可以使用更少的颜色完成着色。

异常的PuLP实现 #

采用相近逻辑编写的PuLP代码无法得到有效求解结果，代码如下：

from pulp import *

model = LpProblem("coloring", LpMinimize)

# 定义决策变量
var = {}
for node in nodes:
    var[node] = LpVariable(node, lowBound=0, upBound=n_nodes-1, cat=LpInteger)

# 定义目标函数
model += len(set(var.values()))

# 添加相邻节点异色约束
for edge in edges:
    model += var[edge[0]] != var[edge[1]]

# 求解
status = model.solve()
print(f'Status: {LpStatus[status]} \n')

for variable in prob.variables():
    print(f"{variable.name}, {v.varValue}")

运行返回结果：

Status: Optimal 

__dummy, None

错误原因与修正方案 #

代码存在3处核心问题：

• 目标函数不符合线性规划建模规则
  PuLP是整数线性规划求解器，仅支持由决策变量线性组合构成的目标与约束。len(set(var.values()))是Python原生集合操作，在模型构建阶段就会被计算为固定值（等于节点总数），完全不会作为和决策变量联动的动态目标传入求解器，这是返回无意义__dummy变量的核心原因。
  最小化颜色使用数的标准线性建模方法需要引入辅助二进制变量：
  1. 预设最大可用颜色数上界（可直接取节点总数，也可提前估算图的色数上界减少计算量）
  2. 定义二进制变量y[c]：颜色c被任意节点使用时取1，否则取0
  3. 目标函数设置为最小化所有y[c]的和
  4. 添加约束：如果某节点被分配颜色c，则y[c]必须等于1。
• 不支持直接使用不等号约束
  PuLP无法识别var[edge[0]] != var[edge[1]]这种非线性不等关系，需要通过大M法转换为线性约束：对每条边的两个节点u、v，要么u的颜色编号比v大至少1，要么v的颜色编号比u大至少1，引入0-1变量控制两个互斥条件的触发即可，参考实现如下：

  # 大M取值不小于最大可用颜色数即可
  M = n_nodes
  for u, v in edges:
      is_diff = LpVariable(f"diff_{u}_{v}", cat=LpBinary)
      model += var[u] - var[v] >= 1 - M*(1 - is_diff)
      model += var[v] - var[u] >= 1 - M*is_diff
  

• 存在基础变量拼写错误
  定义的模型对象名为model，最后遍历变量时错误引用了未定义的prob对象；打印变量值时使用的v也没有提前定义，会直接触发运行报错。

另外OR-Tools返回的6色结果不是最优解，该测试图的最优色数为4，修正建模逻辑后即可得到正确结果。

内容的提问来源于stack exchange，提问作者Zolzaya Luvsandorj