避免大M取值过大引起的数值问题

在数学建模当中，常常会见到大M法，它之所以叫大M法，是因为它涉及到一个（绝对值）较大的系数M，这个大M的值应大于约束中的连续变量或者约束表达式可能取到的任何合理值，M值取过大往往会造成优化问题求解的不稳定性。举以下例子：

x ≤ 1 0 6 y x ≥ 0 y ∈ { 0 , 1 } x\leq 10^6y\\x\geq 0\\ y\in \{0,1\} x≤106yx≥0y∈{0,1}

大M约束通常用在将二元变量的信息传播给连续变量，如上述例子，只有当 $y=1$ 时，$x$ 才能取到非0的整数值，假如求解器的整数容忍误差为 $10^{-5}$（详见相关文章），则 $y=0.000009999$ 满足整数条件，被视为等于0，但此时代入上述约束后，得到 $x\le 9.999$，$x$ 最大可以取到 9 的正整数值，并不符合一开始说的只有 $y=1$ 时，$x$ 才能取到非 0 整数值的关系。尽管我们能够调整求解器的整数容忍误差，但当大M的取值更大时，就不能避免这种情况。

因此，另一个常用的方式是通过额外的信息来收紧大M的值（详见相关文章），对于整数容忍误差为 $10^{-5}$ 的求解器而言，大M的值比 $10^{-5}$ 小就能实现目标，例如上述约束，在如下形式：

x ≤ 1 0 3 y x ≥ 0 y ∈ { 0 , 1 } x\leq 10^3y\\x\geq 0\\ y\in \{0,1\} x≤103yx≥0y∈{0,1}

即使 $y=0.000009999$，约束也仅允许 $x\le 0.009999$，满足约束的初始意图。

特别的，如果我们自己用大M法实在是难以收紧大M的取值，不得不用较大的值进行约束，则可以利用一些求解器自带的SOS约束函数（当$y=0\Rightarrow x=0$），这些SOS约束函数在求解器内部也是通过大M法进行转化，且会以一定的额外求解时间为代价。