基于Pulp的CBC求解器日志分析及优化问题问询

1. 如何估算计算完成所需时间？ #

CBC基于分支定界算法，没有绝对精准的估算方式，但可以通过两个维度大致判断：

• 节点处理速率：对比日志中相邻两次进度更新的时间差和节点数增量，算出每秒处理的节点数，再用当前待处理节点数（on tree数值）除以这个速率，得到剩余时间的粗略参考值。注意后期节点通常更复杂，处理速度会变慢，这个值只能做大概预判。
• 对偶间隙下降趋势：如果间隙下降越来越平缓，说明接近最优的速度变慢，实际所需时间会比估算值更长；如果间隙下降稳定，可按当前下降速率推算达到目标间隙的时间。

另外，直接给求解器设置时间限制（比如maxSeconds参数），反而更实用，避免无限等待。

2. 如何解读CBC日志行？ #

以Cbc0010I After 800 nodes, 403 on tree, -72000 best solution, best possible -72029.13 (24.91 seconds)为例，每个字段的含义：

• Cbc0010I：CBC的日志类型标识，代表分支定界的进度更新
• After 800 nodes：已经完成处理的分支定界节点总数
• 403 on tree：当前分支树中还未处理的节点数量，数值越少，剩余工作量越小
• -72000 best solution：目前找到的最优可行解的目标函数值（最大化问题中数值越大越好，最小化问题则越小越好）
• best possible -72029.13：当前对偶松弛得到的理论最优界（最小化问题中是可行解的下限，最大化问题中是上限）
• (24.91 seconds)：求解器累计运行的时间

还可以通过这个日志计算对偶间隙，公式为：|最优可行解 - 理论界| / |最优可行解| × 100%，本例中间隙约为| -72000 - (-72029.13)| / |-72000| ≈ 0.04%，间隙越小，说明当前解越接近全局最优。

3. 陷入局部最优时，如何调整参数在指定间隙内找到最优可行解？ #

可以通过调整CBC的参数来控制求解过程，在Pulp中可以通过COIN_CMD传递这些参数：

• 设置间隙容忍度：直接指定相对间隙（gapRel）或绝对间隙（gapAbs），比如要1%的相对间隙，代码如下：

  solver = pulp.COIN_CMD(gapRel=0.01, maxSeconds=3600)
  prob.solve(solver)
  

  当求解器找到的解与理论界的间隙小于等于设定值时，会自动停止，返回当前最优可行解。
• 调整启发式策略：开启更强的启发式算法，让求解器更快找到高质量可行解，缩小初始间隙。可以设置heuristicStrategy参数为"strong"。
• 优化分支与剪枝：调整分支策略（branchStrategy）优先处理更有潜力的节点，或者加强剪枝（cutStrategy）减少不必要的节点探索，提升求解效率。
• 设置时间限制：配合间隙参数设置maxSeconds，避免求解器无限运行，在时间或间隙满足任一条件时停止。

如果问题本身容易陷入局部最优，也可以尝试先放松部分约束找到可行解，再逐步收紧，或者调整变量的分支顺序，引导求解器向全局最优方向探索。

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