R中使用Symphony/CBC求解器的gap与first feasible参数使用疑问

问题解答 #

基础理解确认 #

你对first feasible和gap参数的初始认知完全正确：开启first feasible后求解器找到第一个满足约束的可行解就会停止，结果可能和最优值差距极大；设置最大gap可以控制解的质量边界，相比求绝对最优解可以大幅缩短运行时间。
你实际问题包含连续变量的情况不会影响本次测试的参考性，gap和first feasible的逻辑对所有混合整数规划场景通用。

第一组问题解答 #

• 为什么启用first feasible时CBC远快于Symphony，不启用时CBC更慢？
  这是两个求解器默认的启发式策略、分支定界流程适配性差异导致的：

  1. 关闭first feasible求全局最优时，Symphony默认的剪枝、分支变量排序规则刚好适配你当前这个小规模问题的结构，执行的搜索步骤更少，速度更快；CBC默认的预处理、分支逻辑在这个场景下有更多冗余步骤，所以耗时更长。
  2. 开启first feasible时，CBC自带的初始可行解启发式（如松弛取整、潜水启发式）性能远强于Symphony，能更快找到第一个可行解，所以速度明显更快。

• 为什么设置了R的随机种子，Symphony运行结果仍有波动？
  你设置的set.seed只能控制R语言层面的随机数生成，而Symphony、CBC这类求解器的核心逻辑是C++实现的，内部的分支变量随机排序、启发式搜索的随机扰动等逻辑不受R的随机种子控制。Symphony默认启用了随机分支策略，所以多次运行结果会出现波动，如果需要固定结果，需要额外设置求解器本身的随机种子参数，R层面的种子无法控制求解器内部逻辑。

• 为什么开启first feasible时CBC仍能输出最优解，是不是CBC的first feasible安全性更高？
  这是你当前测试问题规模小、结构简单导致的，并非CBC的first feasible本身更安全。你当前测试只有4个供应商、500个商品，CBC的初始启发式刚好第一步就找到了最优解，所以开启first feasible也返回最优结果。如果是你实际的大规模、约束更复杂的问题，CBC的初始启发式大概率找不到最优解，first feasible返回的结果也会和最优值有很大差距，不要在生产环境依赖first feasible获取接近最优的结果。

gap参数相关解答 #

gap的核心定义

对于最小化问题，MIP求解过程中会实时维护两个值：

• UB（上界）：当前找到的最优可行整数解的目标值，也就是你看到的当前输出目标值
• LB（下界）：通过线性松弛得到的理论最优值的下限，不可能存在比LB更小的可行解
  通用的相对gap计算公式为：相对gap = (UB - LB) / min(|UB|, |LB|) * 100%，代表当前解和理论最优值的最大可能差距比例。

两个求解器的gap参数差异

1. CBC的ratio参数是相对gap的小数形式，和文档描述一致：设0.15就代表允许最大15%的相对gap，设0代表要求UB=LB，也就是绝对最优解。你测试中把gap设为100甚至更大时CBC仍返回最优解，是因为CBC在预处理阶段就已经找到了最优解，且LB也同步提升到和UB相等，不管gap设多大，只要上下界相等，求解器都会停止返回最优解，所以你看到的结果不变。
2. Symphony的gap_limit参数默认是绝对gap，也就是允许的UB-LB的最大绝对值，使用前建议查阅官方文档确认定义，不同版本可能存在差异。

10%精度需求的设置方法

要保证目标值在绝对最优值的10%以内，直接给CBC的ratio参数设为0.1即可，这个设置是行业通用的，只要求解器正常收敛，就能保证结果和最优值的差距不超过10%，完全可以实现你的需求。如果要使用Symphony，先确认它的gap参数定义，如果是相对小数就设0.1，如果是相对百分比就设10，如果是绝对gap，需要先预估最优值的大致范围，再计算对应的绝对gap值设置。

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