宽容和不良条件-一个警告


宽容和不良条件作用——警告

正如本节中几个地方所指出的,有限精度算法限制了Gurobi计算的解的精度。在大多数情况下,这种限制是通过数值公差来实现的;如果违反小于相应的容限,则将解视为满足约束。默认公差被选择为足够大,这样对于大多数模型来说数值误差不是问题。

不幸的是,一些模特患有严重的生病的条件,这会使寻找解决方案变得非常复杂。这可以从几个方面表现出来。不合理的条件会严重损害性能,并且可能导致违反约束的解决方案大于容忍值。

病态条件作用是对求解线性方程组时可能产生的误差量的测量。如前所述,线性规划和混合整数规划是建立在线性求解之上的,因此求解线性系统的误差直接导致LP和MIP解的误差。当求解线性系统的误差与期望公差相当时,就会出现严重的问题。如果你想解决一个线性规划问题到默认的可行性容差< span > < / span > 1美元e-6 < span > < / span >美元,如果你的线性系统解出的误差也大致是< span > < / span > 1美元e-6 < span > < / span >美元,那么你就无法知道你当前的解决方案是否真正可行。这可能会导致振荡,因为你的解决方案在可行和不可行之间跳跃,这仅仅是由于数值误差,这可能会使它极其困难,以实现一个最优的解决方案。

当解决线性和二次规划问题时,我们建议您检查最终的原始和对偶约束违背。对偶理论指出,如果你的解是原始可行的,对偶可行的,和互补的,那么你就有一个最优解。单纯形法自动加强了互补性,因此实现了原可行性和双可行性(公差),确保了解决方案是最优的(公差)。

在求解MIP模型(包括任何包含离散或非凸特征的模型,如非凸目标、一般约束、半连续变量等)时,不幸的是,没有简单的方法来检查结果的最优性。当我们努力识别和管理不良条件的负面影响时,我们无法提供一个数学证明,证明返回的解决方案是真正最优的。

有关数字问题的更多信息,请参阅古罗比数字问题准则本手册的一部分。