使用Gurobi求解图着色色数的ILP模型报错（目标函数相关）

代码中的错误点： #

• 未定义环境变量e：创建Gurobi模型时使用env = e，但e未初始化，Gurobi允许省略环境参数直接使用默认环境。
• 重复导入库：代码中重复导入networkx as nx，需删除冗余导入。
• 约束命名格式化缺失：所有addConstr的name参数使用了占位符（如'NC_%d'）但未传入对应变量，会触发格式字符串错误。
• 变量引用错误：在颜色使用跟踪约束（SH约束）中，循环变量为l，但代码错误引用了未定义的u，应改为x[l][j]。
• 冗余变量TEST：TEST = range(k)属于冗余定义，直接使用range(k)即可。
• 不必要的m.update()调用：Gurobi在调用optimize()前会自动更新模型，无需手动重复调用。

修复后的完整代码： #

!pip install gurobipy
import networkx as nx
import gurobipy as gp
from gurobipy import *

# 创建测试图
n = 70
p = 0.6
G = nx.erdos_renyi_graph(n, p)

nx.draw(G, with_labels=True)

# 计算色数 -- ILP求解
m = gp.Model('chrom_num')  # 移除未定义的env参数

# 获取所需最大颜色数（基于图的最大度数+1）
k = max(dict(nx.degree(G)).values()) + 1

# 创建y变量：y_j表示是否使用颜色j
y = []
for j in range(k):
    y.append(m.addVar(vtype=gp.GRB.BINARY, name=f'y_{j}', obj=1))

# 创建x变量：x_lj表示节点l是否使用颜色j
x = []
for l in range(n):
    x.append([])
    for j in range(k):
        x[-1].append(m.addVar(vtype=gp.GRB.BINARY, name=f'x_{l}_{j}', obj=0))

# 目标函数：最小化使用的颜色数量
m.setObjective(gp.quicksum(y[j] for j in range(k)), gp.GRB.MINIMIZE)

# 约束1：每个节点恰好分配一种颜色
for u in range(n):
    m.addConstr(gp.quicksum(x[u]) == 1, name=f'NC_{u}')

# 约束2：如果任何节点使用颜色j，则y_j=1
for l in range(n):
    for j in range(k):
        m.addConstr(x[l][j] <= y[j], name=f'SH_{l}_{j}')

# 约束3：相邻节点不能使用相同颜色
for u in range(n):
    for v in G[u]:
        if v > u:  # 避免重复添加约束（u-v和v-u）
            for j in range(k):
                m.addConstr(x[u][j] + x[v][j] <= 1, name=f'ADJ_{u}_{v}_COL_{j}')

# 求解模型
m.optimize()
chrom_num = m.objVal
print(f"图的色数为: {chrom_num}")

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