Or Tools MILP模型最优解违反约束问题咨询

核心原因分析 #

• 浮点精度误差：MILP求解器依赖浮点数运算，必然存在舍入误差。即使调整了大M值（从10000改到1000），求解器判断解可行的默认容差（通常在1e-6级别）可能允许解存在微小偏差，手动检查时这些偏差会被放大，导致看起来违反约束。
• 约束建模漏洞：如果约束逻辑本身存在错误（比如大M取值不足以覆盖变量的实际波动范围，或者逻辑约束的方向搞反），求解器会认为满足约束，但实际逻辑上违反。比如某个二进制变量的激活约束中，大M值太小，导致变量取1时对应的连续变量约束没有被正确限制。
• 求解器容差设置：默认的可行性容差可能偏松，求解器会将接近满足约束的解判定为可行并返回最优，但手动验算时因为没有容差缓冲，会判定为违反。

解决方法 #

• 核对约束建模逻辑：逐行检查约束，确保大M的取值严格大于对应变量的最大可能变化范围。比如变量x的取值范围是0到50，那大M至少要设为50，避免因大M不足导致约束失效。
• 收紧求解器精度：在OR-Tools中可以通过调整参数收紧容差，例如：

  model.parameters.linear_programming.tolerance = 1e-9
  model.parameters.integer_programming.tolerance = 1e-9
  

  强制求解器寻找更精确的可行解。
• 手动检查时加入误差缓冲：验证约束时不要使用严格的等式/不等式，而是加入一个小的epsilon值。比如判断sum(coefficients * variables) <= upper_bound + 1e-6，而非严格的<= upper_bound。
• 输出变量完整数值：不要只查看四舍五入后的结果，打印变量的完整浮点值，确认是真的违反约束还是显示精度导致的误判。

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