分支定界算法求解带卡车容量约束运输问题的代码修正求助

核心问题排查方向 #

• 松弛问题边界处理错误：scipy.linprog仅能求解线性松弛问题（允许非整数解），若分支定界过程中未基于整数约束（运输量/装载量的整数要求）正确分支剪枝，会导致松弛解下界不准确，错过更优的整数解。
• 约束条件遗漏或映射错误：检查numpy+scipy代码是否完整复现Pulp版本的所有约束：
  • 卡车6吨装载限制是否正确转化为线性约束
  • 供需平衡约束是否完全匹配
  • 变量的非负整数约束是否在分支流程中正确应用
• 分支策略不合理：若分支时未优先选择整数偏差最大的变量，或未按松弛解下界优先级处理节点，可能提前剪枝掉包含最优解的分支，得到次优结果。

具体代码修正步骤 #

1. 验证松弛问题一致性
   单独运行scipy.linprog求解松弛问题，对比Pulp的松弛解（可先在Pulp中放松整数约束），若结果不一致，说明目标函数或约束定义存在错误：

   import numpy as np
   from scipy.optimize import linprog
   
   # 确保成本矩阵、供需约束与Pulp完全匹配
   cost_matrix = np.array([[...], [...]])  # 替换为你的实际成本矩阵
   c = cost_matrix.flatten()
   # 检查A_eq/b_eq（供需平衡）、A_ub/b_ub（卡车装载限制）的正确性
   res = linprog(c, A_eq=A_eq, b_eq=b_eq, A_ub=A_ub, b_ub=b_ub, method='highs')
   print("松弛解总成本：", res.fun)
   

2. 修正整数约束的分支逻辑
   当松弛解存在非整数变量时，需针对该变量创建两个分支：一个强制变量≤floor(x)，另一个强制变量≥ceil(x)，每次分支后将新约束添加到问题中，确保整数约束被严格执行。
3. 优化剪枝逻辑
   初始化当前最优解为Pulp得到的276美元（或一个较大初始值），每次求解松弛问题后，若松弛解下界≥当前最优解，直接剪枝该节点，避免无效搜索。
4. 确认变量类型处理
   scipy.linprog不支持整数规划，分支定界的核心是手动处理整数约束。若你的代码未对变量整数性做分支处理，得到的330美元可能只是松弛解成本，而非整数最优解。

关键注意事项 #

• 确保Pulp与numpy+scipy代码的问题定义完全一致：包括成本系数、供需量、卡车装载限制的数值，避免数据输入错误导致结果差异。
• 用优先队列（如heapq）管理分支节点，按松弛解下界从小到大排序，优先处理更可能得到最优解的节点，提升搜索效率与准确性。

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