如何在OR-Tools CP-SAT中当最优解久未更新时终止搜索

问题 #

使用OR-Tools的CP-SAT求解器解决整数规划问题时，发现求解器找到后续被证明为最优的解后，会花费大量时间进行最优性证明，最优当前解（best incumbent solution）与最优边界（best bound）之间的差距收敛速度极慢。

曾尝试当MIP gap百分比（公式：(abs(objective - best_bound) / objective) < 0.05）时输出可行解，但因收敛缓慢未奏效。现有代码如下：

from ortools.sat.python import cp_model as cp
import time

class PrinterClass(cp.CpSolverSolutionCallback):

    def __init__(self):
        cp.CpSolverSolutionCallback.__init__(self)
        self.__solution_count = 0
        self.__start_time = time.time()

    def on_solution_callback(self):
        current_time = time.time()
        objective = self.ObjectiveValue()
        best_bound = self.BestObjectiveBound()
        print("Solution %i, time = %f s, objective = %i, best_bound = %i" %
              (self.__solution_count, current_time - self.__start_time,
               objective, best_bound))
        self.__solution_count += 1
        
        if (abs(objective - best_bound) / objective) < 0.05:
            print('Stop search')
            self.StopSearch()
            
    def total_num_solutions(self):
        return self.__solution_count

需求：实现当最优当前解连续10秒未更新时，输出该可行解并终止搜索，避免求解器花费大量时间缩小最优当前解与最优边界之间的差距。例如日志中2.75秒找到的解#13是最优解，之后花费约25秒证明其最优性，希望在10秒无改进时终止搜索。

解决方案 #

修改CpSolverSolutionCallback类，增加记录最优解更新时间的变量，仅在找到更优解时更新时间戳，每次回调时检查是否超过无改进超时阈值，达到则终止搜索。

修改后的代码 #

from ortools.sat.python import cp_model as cp
import time

class TimeoutCallback(cp.CpSolverSolutionCallback):
    def __init__(self, timeout_seconds=10):
        cp.CpSolverSolutionCallback.__init__(self)
        self.__solution_count = 0
        self.__start_time = time.time()
        # 记录上次找到更优解的时间
        self.__last_best_update_time = self.__start_time
        # 设置无改进超时时间（秒）
        self.__timeout = timeout_seconds
        # 保存当前最优目标值
        self.__best_objective = None

    def on_solution_callback(self):
        current_time = time.time()
        objective = self.ObjectiveValue()
        best_bound = self.BestObjectiveBound()

        # 首次找到解或当前解更优时，更新最优解信息
        if self.__best_objective is None or objective < self.__best_objective:
            self.__best_objective = objective
            self.__last_best_update_time = current_time
            print(f"找到更优解 #{self.__solution_count}, 时间 = {current_time - self.__start_time:.6f} s, 目标值 = {objective}, 最优边界 = {best_bound}")
        else:
            # 非更优解，仅打印基础信息（可根据需要注释）
            print(f"找到可行解 #{self.__solution_count}, 时间 = {current_time - self.__start_time:.6f} s, 目标值 = {objective}, 最优边界 = {best_bound}")
        
        self.__solution_count += 1

        # 检查是否超过无改进超时时间
        if current_time - self.__last_best_update_time >= self.__timeout:
            print(f"\n连续{self.__timeout}秒未找到更优解，终止搜索")
            print(f"最终保留的最优解目标值: {self.__best_objective}")
            self.StopSearch()

    def total_num_solutions(self):
        return self.__solution_count

    def get_best_objective(self):
        return self.__best_objective

关键改动说明 #

• __last_best_update_time：记录上次找到更优解的时间戳，仅在找到比当前最优解更好的解时更新
• __best_objective：保存当前找到的最优目标值，用于判断新解是否更优
• 超时检查逻辑：每次回调时计算当前时间与上次最优解更新时间的差值，超过设定的10秒则触发终止
• 新增get_best_objective方法，方便在搜索结束后获取最终的最优解目标值

使用示例 #

在求解模型时，将该回调类传入求解器的SolveWithSolutionCallback方法：

# 假设已构建好你的CP-SAT模型model
solver = cp.CpSolver()
# 初始化回调，设置10秒无改进超时
callback = TimeoutCallback(timeout_seconds=10)
status = solver.SolveWithSolutionCallback(model, callback)

# 输出结果
print(f"\n求解状态: {solver.StatusName(status)}")
print(f"最终最优目标值: {callback.get_best_objective()}")
print(f"总共找到的解数量: {callback.total_num_solutions()}")

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