OR-Tools求解器参数控制

混合整数规划（Mixed Integer Programming, MIP）是一类包含整数变量和连续变量的优化问题。在求解MIP问题时，通常会使用分支定界（Branch and Bound）或割平面法（Cutting Plane Method）等算法。这些算法在求解过程中会生成一个上界（Upper Bound）和一个下界（Lower Bound）。

• 上界（Upper Bound）：这是当前已知的可行解的目标函数值。由于MIP问题中包含整数变量，找到一个可行解并不总是容易的，因此上界通常是通过启发式方法或部分求解得到的。
• 下界（Lower Bound）：这是通过松弛问题（通常是线性松弛，即将整数变量放宽为连续变量）得到的目标函数值。下界是对最优解的一个估计，它表示在当前约束条件下，目标函数值不可能低于这个值。

上下界的Gap（差距）是指上界和下界之间的差值，通常用相对差距（Relative Gap）来表示：

Gap

=

Upper Bound

−

Lower Bound

Upper Bound

ext{Gap} = \frac{ ext{Upper Bound} – ext{Lower Bound}}{ ext{Upper Bound}}

Gap=Upper BoundUpper Bound−Lower Bound​
在MIP求解过程中，算法会不断改进上界和下界，使它们逐渐收敛。当上下界的Gap较小时，意味着上界和下界非常接近，这时可以认为当前的可行解已经非常接近最优解。当上下界的Gap足够小时（通常设定一个容忍度，比如1%或0.1%），可以认为当前的可行解已经是最优解或非常接近最优解，因为此时上界和下界之间的差距已经很小，进一步改进的空间有限。

一、Relative MIP Gap、Absolute MIP Gap、Primal Tolerance

• 相对MIP间隙（Relative MIP Gap）：相对 MIP 间隙是指当前最优整数解（可行解）与当前最优松弛解（忽略整数约束的解）之间的相对差距。这个差距通常用以下公式表示：
  

  Relative MIP Gap

  =

  ∣

  Best Integer Solution

  −

  Best Relaxed Solution

  ∣

  ∣

  Best Relaxed Solution

  ∣

  ext{Relative MIP Gap} = \frac{| ext{Best Integer Solution} – ext{Best Relaxed Solution}|}{| ext{Best Relaxed Solution}|}

  Relative MIP Gap=∣Best Relaxed Solution∣∣Best Integer Solution−Best Relaxed Solution∣​
  相对 MIP 间隙的值通常是一个百分比，用来衡量当前解与最优解之间的相对差距。求解器会在相对 MIP 间隙小于设定的阈值时停止求解。

• 绝对 MIP 间隙（Absolute MIP Gap）：绝对 MIP 间隙是指当前最优整数解与当前最优松弛解之间的绝对差距。这个差距通常用以下公式表示：
  

  Absolute MIP Gap

  =

  ∣

  Best Integer Solution

  −

  Best Relaxed Solution

  ∣

  ext{Absolute MIP Gap} = | ext{Best Integer Solution} – ext{Best Relaxed Solution}|

  Absolute MIP Gap=∣Best Integer Solution−Best Relaxed Solution∣
  绝对 MIP 间隙的值是一个绝对数值，用来衡量当前解与最优解之间的绝对差距。求解器会在绝对 MIP 间隙小于设定的阈值时停止求解。

• 原始容差：原始容差是指求解器在求解过程中允许的解的精度。它通常用于控制求解器在何种精度下认为一个解是可行的。原始容差的值越小，求解器对解的精度要求越高。

二、什么时候需要设置相对间隙、原始容差

什么时候需要设置相对间隙？

• 求解时间过长：如果求解器在找到一个可行解后仍然花费大量时间进行微小的改进，设置相对间隙可以让求解器在达到足够好的解时提前停止。
• 对解的精度要求不高：在某些应用场景中，找到一个接近最优的解比找到绝对最优解更重要。设置相对间隙可以在找到一个足够好的解时停止求解，从而节省时间。
• 资源有限：在计算资源（如时间和内存）有限的情况下，设置相对间隙可以帮助你在有限的资源内找到一个可接受的解。

什么时候需要设置原始容差？

• 对解的精度要求高：如果你的应用场景对解的精度要求非常高，设置较小的原始容差可以确保求解器找到更精确的解。
• 数值稳定性问题：在某些情况下，求解器可能会遇到数值稳定性问题。调整原始容差可以帮助求解器更稳定地找到可行解。
• 默认容差不合适：在某些特定问题中，默认的原始容差可能不适合你的需求。调整原始容差可以更好地适应你的问题。

三、OR-Tools中CBC求解器设置相对间隙和原始容差

solver_params.SetDoubleParam(pywraplp.MPSolverParameters.RELATIVE_MIP_GAP, 1e-6)# 设置相对 MIP 间隙

solver_parameters.SetDoubleParam(pywraplp.MPSolverParameters.ABSOLUTE_MIP_GAP, 1e-10)# 设置绝对 MIP 间隙

solver_params.SetDoubleParam(pywraplp.MPSolverParameters.PRIMAL_TOLERANCE, 1e-6)# 设置原始容差

solver.SetSolverSpecificParametersAsString('MIPGap=0.000001')# 设置相对MIP间隙，对于CBC求解器，设置之后没有效果