在OR-Tools的CP求解器使用场景中，复杂约束规划问题通常需要较长的求解时间才能得到优质解，但固定单一的时间限制要么导致求解不充分，要么浪费计算资源。分阶段时间限制策略通过把求解过程拆分成多个阶段，为每个阶段分配不同的时间预算和求解参数，能够在前期快速找到可行解，后期集中资源优化解的质量，大幅提升求解效率。
分阶段时间限制策略的核心思路
分阶段时间限制的核心是将求解过程拆分为探索阶段和优化阶段，不同阶段设置不同的时间配额和求解侧重：
- 探索阶段：分配较短的时间，关闭复杂的剪枝策略，优先快速遍历解空间，找到第一个可行解或者多个初始可行解。
- 优化阶段：如果探索阶段找到了可行解，分配剩余的大部分时间，开启更严格的剪枝、调整搜索策略，对已有解进行优化，提升解的质量。
- 兜底阶段：如果探索阶段未找到可行解，适当延长探索时间或者调整约束宽松度，避免直接返回无解结果。
OR-Tools CP求解器的相关接口
OR-Tools的CP求解器提供了时间限制设置和求解状态查询的接口，是实现分阶段策略的基础：
CpSolver类的SetTimeLimit方法可以设置当前求解的时间限制，单位是毫秒。CpSolver的Solve方法返回CpSolverStatus枚举，包含OPTIMAL、FEASIBLE、INFEASIBLE、MODEL_INVALID、UNKNOWN等状态，可以用来判断当前阶段的求解结果。CpSolver的BestObjectiveBound和ObjectiveValue方法可以获取当前最优目标值的上下界，用于判断是否需要进入优化阶段。
分阶段时间限制的实现步骤
1. 定义阶段参数
首先定义每个阶段的时间配额、搜索参数等配置，这里以两个阶段的策略为例：
from ortools.sat.python import cp_model # 总求解时间限制，单位毫秒 TOTAL_TIME_LIMIT = 10000 # 探索阶段时间占比 EXPLORATION_RATIO = 0.3 # 探索阶段时间配额 exploration_time = int(TOTAL_TIME_LIMIT * EXPLORATION_RATIO) # 优化阶段时间配额 optimization_time = TOTAL_TIME_LIMIT - exploration_time
2. 构建CP模型
构建一个简单的示例模型，比如经典的作业车间调度问题简化版，包含三个任务，每个任务有开始时间和持续时间，目标是最小化最大完成时间：
def build_model():
model = cp_model.CpModel()
# 三个任务的持续时间
durations = [3, 5, 2]
# 任务开始时间变量
starts = [model.NewIntVar(0, 10, f'start_{i}') for i in range(3)]
# 任务结束时间变量
ends = [model.NewIntVar(0, 10, f'end_{i}') for i in range(3)]
# 添加结束时间约束：结束时间 = 开始时间 + 持续时间
for i in range(3):
model.Add(ends[i] == starts[i] + durations[i])
# 任务之间无重叠约束（简化示例，假设所有任务使用同一台机器）
for i in range(3):
for j in range(i+1, 3):
model.Add(starts[i] + durations[i] <= starts[j]).OnlyEnforceIf(starts[i] <= starts[j])
model.Add(starts[j] + durations[j] <= starts[i]).OnlyEnforceIf(starts[j] <= starts[i])
# 目标：最小化最大结束时间
makespan = model.NewIntVar(0, 10, 'makespan')
for i in range(3):
model.Add(makespan >= ends[i])
model.Minimize(makespan)
return model, starts, ends, makespan
3. 实现探索阶段求解
设置探索阶段的时间限制，关闭部分优化参数，优先找到可行解：
def run_exploration(model, time_limit):
solver = cp_model.CpSolver()
# 设置探索阶段时间限制
solver.SetTimeLimit(time_limit)
# 探索阶段关闭部分剪枝，加快初始解查找
solver.parameters.keep_all_feasible_solutions = False
solver.parameters.search_branching = cp_model.FIXED_SEARCH
# 求解模型
status = solver.Solve(model)
return solver, status
4. 实现优化阶段求解
根据探索阶段的结果，判断是否进入优化阶段，调整时间限制和求解参数：
def run_optimization(model, time_limit, existing_solver=None):
if existing_solver is None:
solver = cp_model.CpSolver()
else:
solver = existing_solver
# 设置优化阶段时间限制
solver.SetTimeLimit(time_limit)
# 优化阶段开启更严格的剪枝策略
solver.parameters.keep_all_feasible_solutions = True
solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH
# 求解模型
status = solver.Solve(model)
return solver, status
5. 整合分阶段逻辑
将各个阶段串联起来，完成完整的分阶段求解流程：
def solve_with_staged_time_limit():
model, starts, ends, makespan = build_model()
# 第一阶段：探索阶段
print("开始探索阶段求解...")
exploration_solver, exploration_status = run_exploration(model, exploration_time)
print(f"探索阶段求解状态：{exploration_status}")
# 判断是否需要进入优化阶段
if exploration_status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
print(f"探索阶段找到可行解，最优目标值：{exploration_solver.ObjectiveValue()}")
# 第二阶段：优化阶段，复用探索阶段的求解器，减少重复初始化开销
print("开始优化阶段求解...")
optimization_solver, optimization_status = run_optimization(
model, optimization_time, exploration_solver
)
print(f"优化阶段求解状态：{optimization_status}")
if optimization_status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
print(f"最终最优目标值：{optimization_solver.ObjectiveValue()}")
# 输出任务开始时间
for i in range(3):
print(f"任务{i}开始时间：{optimization_solver.Value(starts[i])}")
else:
print("优化阶段未找到更优解，使用探索阶段结果")
print(f"最终最优目标值：{exploration_solver.ObjectiveValue()}")
else:
print("探索阶段未找到可行解，尝试延长探索时间...")
# 兜底逻辑：延长探索时间再次求解
fallback_solver = cp_model.CpSolver()
fallback_solver.SetTimeLimit(TOTAL_TIME_LIMIT)
fallback_status = fallback_solver.Solve(model)
if fallback_status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
print(f"兜底阶段找到可行解，目标值：{fallback_solver.ObjectiveValue()}")
else:
print("所有阶段均未找到可行解")
if __name__ == "__main__":
solve_with_staged_time_limit()
策略优化建议
实际应用中可以根据问题特点调整分阶段策略：
- 如果问题规模较大，可以增加探索阶段的时间占比，优先保证找到可行解。
- 如果问题约束较松，优化阶段可以开启更多的搜索启发式策略，提升解的质量。
- 可以添加阶段间的状态传递，比如把探索阶段找到的可行解作为优化阶段的初始解，进一步加快优化速度。
- 对于多目标优化问题，可以拆分为更多阶段，每个阶段侧重优化不同的目标维度。
注意事项
OR-Tools的CP求解器时间限制是软限制，实际求解时间可能略超过设置的时间值，但不会偏差太大。另外，分阶段设置时间限制时，每次调用SetTimeLimit会覆盖之前的时间设置，如果需要累加时间，需要自己维护时间计数逻辑。通过分阶段时间限制策略，能够更灵活地利用求解资源，在求解效率和解质量之间找到更好的平衡，尤其适合复杂、求解时间波动大的约束规划问题。