CP-SAT 求解器进度衡量与最优性间隙分析

from ortools.sat.python import cp_model

def solve_and_monitor_gap():
    model = cp_model.CpModel()

    # 声明变量
    x = model.NewIntVar(-10, 10, 'x')
    y = model.NewIntVar(-10, 10, 'y')

    # 添加约束
    model.Add(x + y >= 5)
    model.Add(x - y <= 3)

    # 定义目标函数 (这里以最小化为例，但公式对最大化也适用)
    # 尝试一个可能产生负值或零的目标函数
    model.Minimize(3 * x - 2 * y)

    solver = cp_model.CpSolver()
    solver.parameters.log_search_progress = True # 打印求解进度
    solver.parameters.num_workers = 8 # 可以根据需要调整并行工作数

    # 定义一个自定义的解决方案回调函数来监控进度
    class GapMonitor(cp_model.CpSolverSolutionCallback):
        def __init__(self):
            cp_model.CpSolverSolutionCallback.__init__(self)
            self.__solution_count = 0
            self.__initial_bound = None # 可以选择记录初始界限

        def on_solution_callback(self):
            self.__solution_count += 1
            current_obj = self.ObjectiveValue()
            best_bound = self.BestObjectiveBound()

            # 记录初始界限（可选）
            if self.__initial_bound is None:
                self.__initial_bound = best_bound

            # 计算最优性间隙
            # 使用一个小的epsilon值来避免除以零，并处理目标值接近零的情况
            epsilon = 1e-10
            if abs(current_obj) < epsilon and abs(best_bound) < epsilon:
                gap = 0.0 # 如果两者都接近零，则认为间隙为零
            else:
                gap = abs(current_obj - best_bound) / (epsilon + abs(current_obj))

            print(f"Solution #{self.__solution_count}:")
            print(f"  ObjectiveValue: {current_obj}")
            print(f"  BestObjectiveBound: {best_bound}")
            print(f"  Optimality Gap: {gap:.4f} ({(gap * 100):.2f}%)")
            print("-" * 30)

    # 创建并注册回调
    monitor = GapMonitor()
    status = solver.Solve(model, monitor)

    print("\nSolver finished.")
    print(f"Solver status: {solver.StatusName(status)}")
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"Final Objective Value: {solver.ObjectiveValue()}")
        print(f"Final Best Objective Bound: {solver.BestObjectiveBound()}")
        final_obj = solver.ObjectiveValue()
        final_bound = solver.BestObjectiveBound()
        epsilon = 1e-10
        if abs(final_obj) < epsilon and abs(final_bound) < epsilon:
            final_gap = 0.0
        else:
            final_gap = abs(final_obj - final_bound) / (epsilon + abs(final_obj))
        print(f"Final Optimality Gap: {final_gap:.4f} ({(final_gap * 100):.2f}%)")
    else:
        print("No solution found or problem is infeasible/unbounded.")

if __name__ == '__main__':
    solve_and_monitor_gap()