C++中基于Google OR-Tools的线性规划：用回调函数终止搜索

问题描述 #

我正在使用Google OR-Tools库结合SCIP求解器，通过MPSolver类求解整数线性规划（ILP）。希望实现一个自定义回调函数，每次找到新的候选解时触发，根据用户自定义条件评估解是否“足够好”，满足则提前终止ILP求解器。

以下是Gurobi-py中的等效实现示例：

def callback(model_cb: gp.Model, where):
    assert where != gp.GRB.Callback.MULTIOBJ
    if where == gp.GRB.Callback.MIPSOL:
        if model_cb._check_is_success(model_cb.cbGetSolution(s)):
            model._interrupted_success = True
            model_cb.terminate()

model = gp.Model()
model._check_is_success = check_is_success
model._interrupted_success = False
# ... 模型构建代码
model.optimize(callback)

我在MPSolver类的OR-Tools文档中找到了SetCallback方法，但未发现使用示例。请问如何在OR-Tools中实现类似功能？

实现方案与示例 #

OR-Tools的MPSolver回调需要继承MPCallback类，重写NewSolution方法捕获新可行解，再通过InterruptSolve方法提前终止求解。结合SCIP求解器的示例如下：

from ortools.linear_solver import pywraplp

# 自定义回调类，继承MPCallback
class TerminationCallback(pywraplp.MPCallback):
    def __init__(self, check_success_func):
        super().__init__()
        self.check_success_func = check_success_func
        self.interrupted_success = False

    def NewSolution(self):
        # 获取当前求解器实例
        solver = self.solver()
        # 提取所有变量的当前解值
        variable_values = [solver.Value(var) for var in solver.variables()]
        
        # 调用自定义检查函数判断解是否"足够好"
        if self.check_success_func(variable_values, solver.Objective().Value()):
            self.interrupted_success = True
            # 触发求解终止
            solver.InterruptSolve()

# 自定义的解检查函数（根据实际需求修改）
def check_is_success(solution_values, objective_value):
    # 示例条件：目标值达到预设阈值
    return objective_value >= 40

# 构建ILP模型
solver = pywraplp.Solver.CreateSolver('SCIP')
if not solver:
    exit()

# 添加变量、约束与目标函数（示例）
x = solver.IntVar(0, 10, 'x')
y = solver.IntVar(0, 10, 'y')
solver.Add(2*x + y <= 15)
solver.Maximize(3*x + 4*y)

# 初始化回调并绑定到求解器
callback = TerminationCallback(check_is_success)
solver.SetCallback(callback)

# 启动求解
status = solver.Solve()

# 输出结果
if callback.interrupted_success:
    print("求解因找到满足条件的解提前终止")
    print(f"解：x={solver.Value(x)}, y={solver.Value(y)}，目标值={solver.Objective().Value()}")
elif status == pywraplp.Solver.OPTIMAL:
    print("找到全局最优解")
    print(f"解：x={solver.Value(x)}, y={solver.Value(y)}，目标值={solver.Objective().Value()}")
else:
    print("未找到可行解或求解异常中断")

核心要点 #

• 必须继承pywraplp.MPCallback基类，重写NewSolution方法——该方法会在求解器找到新的可行解时自动触发。
• 在回调方法中，通过self.solver()获取当前求解器实例，可提取变量值、目标值等信息。
• 调用solver.InterruptSolve()即可立即终止求解流程，无需额外的全局状态标记（示例中的interrupted_success仅用于后续判断终止原因）。
• SCIP求解器原生支持该回调机制，无需额外配置。

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