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

o = solver.ObjectiveValue()
b = solver.BestObjectiveBound()
p = 100 * o / b

from ortools.sat.python import cp_model

def calculate_optimality_gap(solver, model_type="minimization", epsilon=1e-10):
    """
    计算CP-SAT求解器的最优性间隙。

    Args:
        solver: 已经运行并获得结果的cp_model.CpSolver对象。
        model_type: 模型的类型，可以是 "minimization" 或 "maximization"。
        epsilon: 一个小的正数，用于避免除以零。

    Returns:
        最优性间隙的百分比（0到100之间），如果无法计算则返回None。
    """
    if solver.Status() not in [
        cp_model.OPTIMAL,
        cp_model.FEASIBLE,
        cp_model.MODEL_INVALID,
        cp_model.INFEASIBLE,
        cp_model.UNKNOWN
    ]:
        return None # 求解器状态不适合计算间隙

    objective_value = solver.ObjectiveValue()
    best_bound = solver.BestObjectiveBound()

    # 如果尚未找到可行解，或者目标值/界限不合理，则无法计算有意义的间隙
    if solver.Status() == cp_model.UNKNOWN and not (objective_value is not None and best_bound is not None):
        return None

    # 确保objective_value和best_bound是数值类型
    if not isinstance(objective_value, (int, float)) or not isinstance(best_bound, (int, float)):
        return None

    gap = 0.0
    if model_type == "minimization":
        # 对于最小化问题，ObjectiveValue是上界，BestObjectiveBound是下界
        # 间隙 = (UB - LB) / (|UB| + epsilon)
        numerator = objective_value - best_bound
        denominator = abs(objective_value) + epsilon
        if denominator == 0: # 避免除以零，即使epsilon很小也可能遇到
            return 0.0 if numerator == 0 else float('inf') # 如果分子为0，间隙为0；否则为无穷大
        gap = numerator / denominator
    elif model_type == "maximization":
        # 对于最大化问题，ObjectiveValue是下界，BestObjectiveBound是上界
        # 间隙 = (UB - LB) / (|LB| + epsilon)
        numerator = best_bound - objective_value
        denominator = abs(objective_value) + epsilon
        if denominator == 0:
            return 0.0 if numerator == 0 else float('inf')
        gap = numerator / denominator
    else:
        raise ValueError("model_type 必须是 'minimization' 或 'maximization'")

    # 将间隙转换为百分比，并确保非负
    return max(0.0, gap * 100.0)

# 假设你已经定义并运行了一个CP-SAT模型
# model = cp_model.CpModel()
# # ... 添加变量和约束 ...
# # model.Minimize(...) 或 model.Maximize(...)
# solver = cp_model.CpSolver()
# status = solver.Solve(model)

# # 在求解过程中或结束后调用
# if status in [cp_model.OPTIMAL, cp_model.FEASIBLE]:
#     current_gap = calculate_optimality_gap(solver, model_type="minimization") # 根据你的模型类型选择
#     if current_gap is not None:
#         print(f"当前最优性间隙: {current_gap:.2f}%")
#     else:
#         print("无法计算最优性间隙。")
# else:
#     print(f"求解器状态: {solver.Status()}")