Python中PuLP/Pyomo的开源MILP求解器无可行方案的解决咨询

现有n个不同宽度的订单，需组合成多个pattern，约束条件如下：

• 每个订单只能被分配一次；
• 单个pattern的总宽度需大于335且小于340。
  目标函数为最大化分配至各pattern的订单总量。

目前使用PuLP库测试多个求解器后，仅CPLEX能给出可行解（超90%的订单被分配），但部署必须使用开源求解器。尝试GLPK与CBC求解器（通过Pyomo和PuLP）时，运行超2小时仍得到0%的分配结果，待分配订单约500个，代码如下：

import pulp

# Create a LP problem
problem = pulp.LpProblem("Assign_Orders", pulp.LpMaximize)

# Decision variables
num_orders = len(df_order)  # Number of orders
num_patterns = round(len(df_order)/4)  # for pattern assignment

# Binary variable for order assignment
assign = pulp.LpVariable.dicts("Assign", ((i, j) for i in range(num_orders) for j in range(num_patterns)), cat='Binary')

# Binary variable for pattern selection
pattern = pulp.LpVariable.dicts("Pattern", range(num_patterns), cat='Binary')

# Objective function - for maximizing total assigned orders, Column name is width new; order width
problem += pulp.lpSum(df_order.iloc[i]['Width new']*assign[i, j] for i in range(num_orders) for j in range(num_patterns))

# Constraints
# Each order must be assigned to exactly one pattern
for i in range(num_orders):
    problem += pulp.lpSum(assign[i, j] for j in range(num_patterns)) <= 1

# Capacity constraint for each pattern - total width should not exceed a limit

for j in range(num_patterns):
    problem += pulp.lpSum(df_order.iloc[i]['Width new'] * assign[i, j] for i in range(num_orders)) <= 340 * pattern[j]
for j in range(num_patterns):
    problem += pulp.lpSum(df_order.iloc[i]['Width new'] * assign[i, j] for i in range(num_orders)) >= 335 * pattern[j]

# Solve the problem

problem.solve() # have tried multiple solvers here such as glpk, default solver and cplex. only cplex is giving a solution

请问是否可使用其他开源求解器，或修改代码使GLPK/CBC能找到可行解？

一、代码优化方向 #

1. 变量与约束精简

• 缩小变量规模：当前num_patterns = round(len(df_order)/4)生成约125个pattern，对应assign变量有500*125=62500个二进制变量，对开源求解器负担过重。可先预先生成所有有效pattern（总宽度在335-340之间的订单组合），再从中选择不重叠的集合，能大幅减少无效变量。
• 合并约束形式：将pattern的上下界约束合并为单条约束，减少求解器的约束处理量：

  for j in range(num_patterns):
      problem += 335 * pattern[j] <= pulp.lpSum(df_order.iloc[i]['Width new'] * assign[i, j] for i in range(num_orders)) <= 340 * pattern[j]
  

• 调整目标函数：若订单宽度差异不大，改为最大化分配的订单数量而非总宽度，可降低求解难度：

  problem += pulp.lpSum(assign[i, j] for i in range(num_orders) for j in range(num_patterns))
  

2. 求解器参数调优

• CBC求解器：启用启发式算法、设置时间限制与最优解间隙，快速找到可行解：

  problem.solve(pulp.PULP_CBC_CMD(maxSeconds=3600, heur=True, fracGap=0.05))
  

  • maxSeconds：设置最大运行时间（秒）；
  • heur：开启启发式搜索，优先找可行解；
  • fracGap：允许5%的最优解间隙，满足条件即停止计算。
• GLPK求解器：配置时间限制与间隙参数：

  problem.solve(pulp.GLPK_CMD(options=['--tmlim', '3600', '--mipgap', '0.05']))
  

二、其他开源求解器选项 #

• SCIP：性能优于CBC/GLPK的开源MIP求解器，支持PuLP调用（需安装pulp-scip），对大规模整数规划问题处理能力更强。
• HiGHS：近年流行的开源求解器，性能接近商业软件，PuLP已原生支持，调用示例：

  problem.solve(pulp.HiGHS_CMD())
  

三、问题重构思路 #

将问题转化为0-1背包变种：

1. 预先生成所有有效pattern（遍历订单组合，筛选总宽度335-340的集合）；
2. 定义二进制变量x_k表示是否选择第k个pattern；
3. 添加约束：每个订单只能出现在最多一个选中的pattern中；
4. 目标：最大化选中pattern的总宽度（或订单数）。

这种形式通过提前筛选有效组合，能降低求解器的搜索空间，提升开源求解器的处理效率。

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