Google OR-Tools CP-SAT调度优化器搜索不彻底的问题与解决

问题背景 #

我基于Google OR-Tools的CP-SAT工具在C#中开发调度优化器，参考了ShiftSchedulingSat和NursesSat示例代码，构建了布尔约束条件，以及带bool * penalty的优化目标数组，逻辑与ShiftSchedulingSat示例的目标函数一致。

我设置了硬约束和软约束，将硬约束权重设为高值、软约束权重设为低值以进行优化，但程序仅在1-2秒内返回可行解而非最优解。只有当硬约束接近手动找到的下界时，才能得到最优解。我需要明确：

• 为何提高硬约束上限后无法找到最优解
• 如何让优化搜索更彻底

尝试的参数配置 #

我测试了多种StringParameters组合：

• "num_search_workers:8, max_time_in_seconds:60"
• "num_search_workers:8"
• "linearization_level:2, enumerate_all_solutions:true"

其中设置enumerate_all_solutions:true后运行时间大幅增加，但总是在约29.9秒时停止，即使配置了更长的max_time_in_seconds。无优化函数时程序可运行数分钟枚举解决方案，添加优化后却快速退出。

我曾怀疑是提前超时的Bug、优化例程存在独立设置，或是线性优化陷入局部极小值。

排查结果 #

修改单个约束的HardMax值并对比日志后发现：

• HardMax设为4时，线性优化器会搜索更多分支点
• HardMax设为5时，几乎未生成解决方案

最终定位问题：遗留自NursesSat示例的停止代码会在找到1个解决方案后立即终止搜索，导致无法继续寻找最优解。

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