如何测量CP-SAT求解器的求解进度？寻求替代方法

通用核心：基于相对间隙的进度计算 #

你之前的方法仅适用于正系数最大化问题，行业里通用的是**相对间隙（Relative MIP Gap）**转进度的方式，能覆盖所有线性目标（含负系数）、最大化/最小化场景：

通用公式实现 #

o = solver.ObjectiveValue()
b = solver.BestObjectiveBound()

# 避免除以0，添加极小值兜底
denominator = max(abs(o), abs(b), 1e-9)
# 计算相对间隙：当前可行解与理论最优边界的相对距离
relative_gap = abs(o - b) / denominator
# 进度为100%减去间隙占比
progress = 100 * (1 - relative_gap)

这个逻辑的核心是：相对间隙越小，说明当前解越接近最优，进度越高。不管目标函数有没有负系数，是最大化还是最小化，都能给出合理的进度值。

负系数场景的注意事项 #

当目标包含负系数时，初始阶段的BestObjectiveBound可能非常极端（比如最大化含负系数的目标时，初始上界可能是正无穷），这时候：

• 可以先等待求解器找到第一个可行解后，再开始计算进度，避免初始无效值干扰。
• 如果问题本身有明确的目标上下界（比如通过约束推导得出），可以手动设置这些边界，替换初始的BestObjectiveBound，让进度计算更稳定。

是否需要结合初始边界值？ #

分两种情况选择：

• 若要体现从初始状态到当前的整体优化幅度：可以记录求解开始时的初始边界b_initial和第一个可行解的目标值o_initial，然后计算：

  # 最大化场景示例
  total_possible_gain = b_initial - o_initial
  current_gain = o - o_initial
  progress = 100 * current_gain / total_possible_gain
  

  但这种方法仅适用于初始边界明确且合理的场景，如果初始边界过于宽松（比如无穷大），会导致计算失效。
• 若只关注当前解离最优解的接近程度：直接用相对间隙转进度的方法更可靠，它不依赖初始值，只看当前的收敛状态。

其他辅助进度参考指标 #

如果需要更全面的进度判断，还可以结合：

• 可行解更新频率：长时间没有找到更优的可行解，说明可能接近最优解，或者求解进入瓶颈。
• 已探索分支节点数：部分求解器会暴露分支定界的节点统计，节点数增长趋势可以反映求解的推进速度（但无法知道总节点数，只能做趋势参考）。

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