CP-SAT求解器进度测量：优化间隙的计算与应用

本教程详细探讨cp-sat求解器进度测量方法，重点介绍如何利用`objectivevalue`和`bestobjectivebound`计算优化间隙。文章分析了简单百分比计算的局限性，特别是在处理负目标值时的挑战，并提供了标准优化间隙的计算公式及鲁棒实现，旨在帮助用户准确评估求解器性能和收敛情况。

在解决复杂的组合优化问题时，了解求解器的运行进度至关重要。CP-SAT（Constraint Programming - SAT）求解器通过不断寻找更好的可行解并收紧最优界限来逼近全局最优。本教程将深入探讨如何准确测量CP-SAT求解器的进度，重点介绍优化间隙（Optimality Gap）的概念及其在不同场景下的计算方法。

1. 理解CP-SAT求解器进度核心指标

CP-SAT求解器提供了两个关键指标来反映其在搜索过程中的状态：

• ObjectiveValue(): 返回求解器当前找到的最佳可行解的目标函数值。对于最小化问题，这代表了当前已知的最佳上界（Upper Bound, UB）；对于最大化问题，它代表了当前已知的最佳下界（Lower Bound, LB）。在求解器找到第一个可行解之前，此值可能为正无穷（float('inf')）或负无穷（float('-inf')），具体取决于问题类型。
• BestObjectiveBound(): 返回求解器当前计算出的最佳理论界限。对于最小化问题，这代表了当前已知的最佳下界（Lower Bound, LB）；对于最大化问题，它代表了当前已知的最佳上界（Upper Bound, UB）。这个界限是根据模型的松弛或对偶信息推导出来的，表示最优解不可能超出此界限。

求解器的目标是使ObjectiveValue和BestObjectiveBound尽可能接近。当它们相等（或在可接受的浮点误差范围内）时，意味着求解器已找到并验证了全局最优解。

2. 简单百分比计算的局限性

在实践中，一些用户可能会尝试使用一个简单的百分比公式来衡量进度，例如 p = 100 * ObjectiveValue() / BestObjectiveBound()。然而，这种方法存在显著的局限性，使其无法在所有情况下提供准确或有意义的进度评估：

• 负目标值问题: 当目标函数值或其界限为负数时，简单的比率计算会失去其直观意义。例如，对于一个最小化问题，目标值从-100改进到-50，如果界限是-10，那么比率会从1000%变成500%，这与我们期望的“接近0%间隙”的进度衡量方式不符。此外，如果目标值和界限符号不同，结果可能更难以解释。
• 零值问题: 如果BestObjectiveBound()为零，将导致除以零的错误，使计算失效。
• 方向性问题: 这种比率计算没有明确区分最大化和最小化问题，可能导致混淆和错误的解释。
• 不是剩余时间的良好指标: 优化间隙反映的是当前解的质量与理论最优解之间的差距，而非求解器完成任务所需的时间。一个小的间隙可能意味着解的质量很高，但不代表求解器很快就能找到严格的最优解。

3. 标准优化间隙 (Optimality Gap) 的概念与计算

为了克服上述局限性，推荐使用标准的优化间隙（Optimality Gap）来衡量求解器进度。优化间隙是一个鲁棒的指标，它表示当前找到的最佳可行解与理论最优解之间差距的百分比。

AppMall应用商店

AI应用商店，提供即时交付、按需付费的人工智能应用服务

56

查看详情

其核心思想是计算“当前最佳可行解”与“最佳理论界限”之间的绝对差值，然后除以一个基准值以得到相对百分比。为了确保计算的鲁棒性，特别是在目标值接近零或为负数时，通常会在分母中加入一个小的正数（如 1e-10）并取目标值的绝对值。

通用优化间隙公式：Gap = |Best Feasible Solution - Best Bound| / (epsilon + |Best Feasible Solution|) 其中 epsilon 是一个非常小的正数（例如 1e-10），用于避免除以零的情况。

针对CP-SAT的实现： 设 o = solver.ObjectiveValue() 和 b = solver.BestObjectiveBound()。

• 对于最小化问题 (Minimization): 在这种情况下，o 是当前最佳可行解（上界），b 是当前最佳理论下界。 间隙 Gap = (o - b) / (1e-10 + abs(o)) 这个公式确保了分子 (o - b) 始终非负（因为 o >= b），且分母通过 abs(o) 处理了目标值为负的情况，并通过 1e-10 避免了除以零。

• 对于最大化问题 (Maximization): 在这种情况下，o 是当前最佳可行解（下界），b 是当前最佳理论上界。 间隙 Gap = (b - o) / (1e-10 + abs(o)) 类似地，分子 (b - o) 始终非负（因为 b >= o），分母也进行了鲁棒性处理。

重要提示：

• 只有当求解器找到至少一个可行解（即 ObjectiveValue() 返回一个有效的数值，而不是 float('inf') 或 float('-inf')）时，才能计算优化间隙。
• 当求解器找到最优解时，o 和 b 将相等，此时优化间隙为0。

4. 示例代码

以下Python代码演示了如何在CP-SAT求解过程中，通过回调函数实时计算并打印优化间隙：

from ortools.sat.python import cp_model

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

    # 定义一个简单的最小化问题示例
    # 目标是最小化 2*x + 3*y - 5*z
    # 允许变量取负值，以演示优化间隙的鲁棒性
    x = model.NewIntVar(-10, 10, 'x')
    y = model.NewIntVar(-10, 10, 'y')
    z = model.NewIntVar(-10, 10, 'z')

    # 增加一些约束
    model.Add(x + y >= -5)
    model.Add(x - z <= 3)
    model.Add(y + z == 0)

    # 设置目标函数为最小化
    model.Minimize(2*x + 3*y - 5*z)

    solver = cp_model.CpSolver()
    #

以上就是CP-SAT求解器进度测量：优化间隙的计算与应用的详细内容，更多请关注php中文网其它相关文章！