CP Optimizer Python API如何存储调度问题的多个最优解？

CP Optimizer确实支持存储多个等价最优解，不过它的实现逻辑和MIP的解池不一样，得靠回调函数加参数配置来搞定，下面是具体的做法：

1. 调整求解参数 #

首先得让求解器愿意探索更多最优解空间：

• 开启 allSolutions 参数：cp.param.allSolutions = True，这个参数会让求解器尽可能寻找可行解，后续我们只筛选其中最优的那些。
• 可选调整搜索策略：比如用深度优先（cp.SearchType.DepthFirst）或者广度优先搜索，根据你的调度问题特性选择，深度优先通常能更快找到不同分支下的最优解。

2. 用回调函数捕获最优解 #

定义一个回调函数，每次求解器找到新解时，判断它是否和当前最优解等价（目标值一致），是的话就存起来。代码示例如下：

import cplex.cp as cp

# 存储所有等价最优解的列表
optimal_solutions = []
best_objective = None

def solution_callback(solver, event):
    global best_objective
    if event == cp.EventType.Solution:
        current_obj = solver.getObjectiveValue()
        # 第一次找到解时，记录为最优基准
        if best_objective is None:
            best_objective = current_obj
            # 复制当前解存储，必须用copy，否则后续会被新解覆盖
            optimal_solutions.append(solver.solution.copy())
        else:
            # 考虑浮点精度误差，用容差判断目标值是否等价
            if abs(current_obj - best_objective) < 1e-6:
                optimal_solutions.append(solver.solution.copy())

# 构建你的调度模型
model = cp.CpoModel()
# ... 此处添加任务定义、约束条件、目标函数 ...

# 初始化求解器并注册回调
solver = cp.CpoSolver(model)
solver.addCallback(solution_callback)

# 启动求解，可设置时间限制避免耗时过久，比如 solver.solve(timeLimit=300)
solver.solve()

# 输出结果
print(f"共找到 {len(optimal_solutions)} 个等价最优解")
for i, sol in enumerate(optimal_solutions):
    print(f"\n第 {i+1} 个最优解：")
    # 根据你的调度问题打印具体变量，比如任务的开始/结束时间
    for task in your_task_variables:
        print(f"任务 {task.getName()} 开始时间：{sol.getVarStart(task)}")

3. 关键注意事项 #

• 浮点精度：判断目标值是否相等时必须设置容差，避免因计算精度差异误判等价解。
• 性能权衡：捕获多个最优解会增加求解时间，尤其是大规模调度问题，记得通过 timeLimit 参数设置合理的求解时长。
• 解的去重：如果求解器返回完全相同的解（变量赋值一致），可在存储前添加去重逻辑，减少冗余。

CP Optimizer本身没有像MIP那样现成的解池API，但通过回调的方式完全能实现存储多个等价最优解的需求，本质就是在搜索过程中把每个符合最优条件的解筛选出来留存。

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