在vast.ai云Bash环境运行Pulp时出现求解报错问题

环境配置 #

已在vast.ai的Bash环境中完成以下安装：

sudo apt-get install software-properties-common
sudo apt-add-repository universe
sudo apt-get update
sudo apt-get install python3-pip

sudo pip install pulp
sudo apt-get install glpk-utils
sudo apt-get install coinor-cbc

问题现象 #

当参数n<25时，程序正常运行，可返回解或状态值-1（无解）；但n>30时，执行报错，错误栈如下：

Traceback (most recent call last):
  File "Test.py", line 58, in <module>
    Problem.solve()
  File "/usr/local/lib/python3.6/dist-packages/pulp/pulp.py", line 1913, in solve
    status = solver.actualSolve(self, **kwargs)
  File "/usr/local/lib/python3.6/dist-packages/pulp/apis/coin_api.py", line 137, in actualSolve
    return self.solve_CBC(lp, **kwargs)
  File "/usr/local/lib/python3.6/dist-packages/pulp/apis/coin_api.py", line 208, in solve_CBC
    + self.path
pulp.apis.core.PulpSolverError: Pulp: Error while trying to execute, use msg=True for more details/usr/local/lib/python3.6/dist-packages/pulp/solverdir/cbc/linux/64/cbc

核心代码 #

from pulp import LpVariable, LpInteger, LpProblem, LpMaximize, lpSum

n = int(input())
m = int(input())
r = 3 * m - 2

# Vertices
Triple = []
for i in range(n):
    for j in range(n):
        for k in range(n):
            Triple.append((i,j,k))

# Variables
Variable = LpVariable.dicts("Variables",[triple for triple in Triple],0,1,LpInteger)

# Objective
Problem = LpProblem("Problem",LpMaximize)
Problem += Variable[(0,0,0)]

# Constraints
# 1
Exclusion = []
for i in range(n):
    for j in range(n):
        for k in range(n - 1):
            for l in range(k + 1,n):
                Exclusion.append(((i,j,k),(i,j,l)))
                Exclusion.append(((i,k,j),(i,l,j)))
                Exclusion.append(((k,i,j),(l,i,j)))

for exclusion in Exclusion:
    s = exclusion[0]
    t = exclusion[1]
    Problem += Variable[s] + Variable[t] <= 1

# 2
for i in range(n):
    Problem += lpSum([Variable[(i,j,k)]] for j in range(n) for k in range(n)) == m
    Problem += lpSum([Variable[(j,i,k)]] for j in range(n) for k in range(n)) == m
    Problem += lpSum([Variable[(j,k,i)]] for j in range(n) for k in range(n)) == m

# 3
for i in range(n):
    for j in range(n):
        for k in range(n):
            Ones = [triple for triple in Triple if triple[0] == i or triple[1] == j or triple[2] == k]
            Problem += lpSum([Variable[(triple)]] for triple in Ones) >= r
    
# Result
Problem.solve()

s = Problem.status

if s == 1:
    Triangle = []
    for triple in Triple:
        if Variable[triple].value() == 1:
            Triangle.append(triple)
    print(Triangle)
else:
    print(s)

修复方案 #

1. 启用详细日志定位具体错误 #

修改求解代码，添加msg=True参数获取CBC求解器的详细输出，明确错误原因（如内存不足、求解器路径异常等）：

Problem.solve(msg=True)

2. 优化问题规模，减少冗余计算 #

• 约束1优化：当前Exclusion列表存在大量重复约束，可通过集合去重减少约束数量：

  Exclusion = set()
  for i in range(n):
      for j in range(n):
          for k in range(n - 1):
              for l in range(k + 1,n):
                  Exclusion.add(((i,j,k),(i,j,l)))
                  Exclusion.add(((i,k,j),(i,l,j)))
                  Exclusion.add(((k,i,j),(l,i,j)))
  Exclusion = list(Exclusion)
  

• 约束3优化：使用容斥原理替代遍历所有Triple，避免生成庞大的Ones集合，节省内存：

  for i in range(n):
      for j in range(n):
          for k in range(n):
              # 容斥原理计算：行i + 列j + 层k - 行i列j交集 - 行i层k交集 - 列j层k交集 + 行i列j层k交集
              row_i = lpSum(Variable[(i, x, y)] for x in range(n) for y in range(n))
              col_j = lpSum(Variable[(x, j, y)] for x in range(n) for y in range(n))
              layer_k = lpSum(Variable[(x, y, k)] for x in range(n) for y in range(n))
              row_col = lpSum(Variable[(i, j, y)] for y in range(n))
              row_layer = lpSum(Variable[(i, x, k)] for x in range(n))
              col_layer = lpSum(Variable[(x, j, k)] for x in range(n))
              triple_intersect = Variable[(i,j,k)]
              Problem += row_i + col_j + layer_k - row_col - row_layer - col_layer + triple_intersect >= r
  

3. 调整求解器参数或切换求解器 #

• 配置CBC求解器参数：设置时间限制、允许路径等参数，避免无限制占用资源：

  from pulp import CBC_CMD
  solver = CBC_CMD(maxSeconds=300, msg=True, allowPaths=True)
  Problem.solve(solver)
  

• 切换到GLPK求解器：若CBC因内存问题崩溃，可尝试使用GLPK求解器：

  from pulp import GLPK
  Problem.solve(GLPK(msg=True))
  

4. 检查系统资源 #

在vast.ai实例中执行free -h查看内存使用情况，当n>30时，变量数为n³（n=30时达27000个），约束量更是呈指数级增长，若内存不足，需升级实例的内存配置。

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