OR-Tools CP-SAT 求解器版本差异导致的模型可行性问题分析

问题背景

在OR-Tools优化工具库中，CP-SAT求解器在9.8和9.10版本之间出现了模型可行性判断不一致的情况。具体表现为：同一个模型在9.8版本中可以正常求解并获得最优解，但在9.10版本中却被判定为不可行。当在9.10版本中禁用预求解(presolve)功能后，模型又能重新获得可行解。

技术细节分析

预求解功能的变更

OR-Tools 9.10版本中引入了一个重要变更：线性区间(linear part of intervals)的处理被移到了预求解阶段。这一变更旨在提高求解效率，但同时也改变了模型的预处理方式，导致某些特定情况下模型可行性的判断出现差异。

问题重现条件

通过对比分析发现：

1. 在OR-Tools 9.8版本中，无论是否启用预求解，模型都能获得最优解
2. 在OR-Tools 9.10版本中：
   • 启用预求解时，模型被判定为不可行
   • 禁用预求解时，模型能正常求解并获得最优解

解决方案

开发团队已经在v99bugfix分支中修复了这个问题，该修复将包含在即将发布的9.11版本中。对于当前遇到此问题的用户，可以采取以下临时解决方案：

1. 在9.10版本中暂时禁用预求解功能
2. 回退到9.8版本使用
3. 等待9.11版本发布后升级

对开发者的建议

1. 版本兼容性测试：在升级OR-Tools版本时，建议对关键模型进行回归测试，确保模型行为一致
2. 预求解功能理解：深入了解预求解的工作原理，它虽然能提高求解效率，但也可能改变模型的行为
3. 错误处理：在代码中添加对求解状态的检查逻辑，当遇到不可行情况时，可以尝试调整求解器参数

总结

这个案例展示了优化求解器内部算法变更可能带来的兼容性问题。作为开发者，我们需要：

• 关注版本更新日志中的重要变更
• 建立完善的测试机制
• 理解求解器参数对模型求解的影响
• 保持与开源社区的沟通，及时报告发现的问题

OR-Tools团队对此问题的快速响应和修复体现了开源社区的优势，也提醒我们在使用复杂数学优化工具时需要保持谨慎和全面的测试策略。