本教程详细探讨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）来衡量求解器进度。优化间隙是一个鲁棒的指标，它表示当前找到的最佳可行解与理论最优解之间差距的百分比。
其核心思想是计算“当前最佳可行解”与“最佳理论界限”之间的绝对差值，然后除以一个基准值以得到相对百分比。为了确保计算的鲁棒性，特别是在目标值接近零或为负数时，通常会在分母中加入一个小的正数（如 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_modeldef 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求解器进度测量：优化间隙的计算与应用的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1379824.html
微信扫一扫 
支付宝扫一扫 
