如何高效配置ortools CP_Solver分阶段时间限制并续接搜索？

问题描述 #

我需要配置OR-Tools的CP-Solver，初始化代码如下：

from ortools.sat.python import cp_model
solver = cp_model.CpSolver()

需求如下：

1. 首先运行time_limit_1时长，若找到解则返回最优解；
2. 若未找到解，则继续运行至以下任一条件满足：
   • 找到第一个可行解；
   • 累计运行时长达到time_limit_2仍未找到解

我当前的实现效率极低：先设置solver.parameters.max_time_in_seconds = time_limit_1，超时未找到解后就重新初始化求解器，再设置stop_after_first_solution=True来快速找第一个解。想问有没有办法让第二次搜索从第一次中断的位置继续？

解决方案 #

可以通过复用求解器实例并动态调整参数，实现从上次中断的位置继续搜索，无需重新初始化求解器。核心逻辑是累计计算已用时间，分阶段调整求解目标（优先最优解→优先可行解）。

具体实现步骤 #

1. 初始化求解器后，第一阶段设置时间限制为time_limit_1，保持默认的stop_after_first_solution=False，优先搜索最优解；
2. 执行第一次求解，根据返回状态判断结果：
   • 若状态为cp_model.OPTIMAL，直接返回最优解；
   • 若未找到任何解且已超时，计算剩余允许运行时间（time_limit_2减去已用时间）；
3. 第二阶段调整参数：设置剩余时间为新的时间限制，开启stop_after_first_solution=True，再次调用求解方法继续搜索，直到找到可行解或用完剩余时间。

示例代码 #

from ortools.sat.python import cp_model

def staged_cp_solve(model, time_limit_1, time_limit_2):
    solver = cp_model.CpSolver()
    
    # 第一阶段：优先搜索最优解，运行time_limit_1秒
    solver.parameters.max_time_in_seconds = time_limit_1
    status = solver.Solve(model)
    
    if status == cp_model.OPTIMAL:
        print("搜索到最优解")
        return solver, status
    
    # 第一阶段未找到解，进入第二阶段
    if not solver.HasSolution():
        used_time = solver.WallTime()
        remaining_time = max(0.0, time_limit_2 - used_time)
        
        if remaining_time <= 0:
            print("已达到总时间限制，未找到任何解")
            return solver, status
        
        # 调整参数：剩余时间内优先找到第一个可行解
        solver.parameters.max_time_in_seconds = remaining_time
        solver.parameters.stop_after_first_solution = True
        status = solver.Solve(model)
        
        if solver.HasSolution():
            print("搜索到可行解")
        else:
            print("总时间限制内未找到任何解")
    
    return solver, status

关键注意点 #

• OR-Tools的CP-Solver实例在调用Solve()后，会保留搜索过程中的约束传播数据、搜索树状态等信息，再次调用Solve()会从上次中断的位置继续推进，无需从头开始；
• 必须准确计算剩余时间，避免累计运行时长超过time_limit_2；
• 分阶段调整stop_after_first_solution参数，确保第一阶段以最优解为目标，第二阶段快速获取可行解。

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