ORTools CP-SAT 依赖动态x的通道约束与自定义非线性约束实现
OR-Tools CP-SAT 适配动态依赖自定义计算函数的实现方案
核心问题本质
- CP-SAT在建模阶段处理的是
IntVar、BoolVar这类符号化决策变量,无法直接接收需要实值numpy数组输入的自定义计算函数 - 自定义函数
g()依赖np.where(x == 1)这类逐值判断逻辑运行,必须拿到变量的实际0/1取值才能输出有效结果,而变量取值是在求解器搜索迭代过程中才动态生成的,无法在建模阶段一次性确定 - 之前实现失效的根本原因:
- 建模阶段直接把CP-SAT变量列表传给需要numpy数组输入的函数,触发类型不匹配报错
- 建模阶段用Python原生
if判断读取BoolVar的值(比如if open_elements[i] == True),拿到的是变量对象本身的内存地址,永远为真,完全没有动态语义 - 把自定义函数的输出硬编码成固定值,没有和决策变量的实际取值路径绑定,求解器识别不到依赖关系
正确实现逻辑
1. 去除冗余变量映射
不需要重复定义和x并行的open_elements、closed_elements变量,直接做等价绑定即可:
x = [model.NewIntVar(0, 1, f"x[{i}]") for i in range(66)] open_elements = [model.NewBoolVar(f"open_elements[{i}]") for i in range(66)] closed_elements = [model.NewBoolVar(f"closed_elements[{i}]") for i in range(66)] # 等价绑定,保证三者取值完全一致 for i in range(66): model.Add(x[i] == 1).OnlyEnforceIf(open_elements[i]) model.Add(x[i] == 0).OnlyEnforceIf(open_elements[i].Not()) model.Add(x[i] == 0).OnlyEnforceIf(closed_elements[i]) model.Add(x[i] == 1).OnlyEnforceIf(closed_elements[i].Not())
2. 按自定义函数的计算逻辑分场景适配
场景A:函数输出和决策变量取值无关,只是固定系数
如果arr_a、arr_b、arr_c的数值不随x的取值变化,只是建模时静态依赖外部输入计算得到,直接预计算常量值即可:
# 预计算固定系数,不传入x变量 arr_a, arr_b, arr_c = g(df1, df2, df3) # 此时g的输入只依赖df,不依赖x # 构建max(arr_a * x) <=50的约束 max_val = model.NewIntVar(0, arr_a.max(), "max_arr_a") model.AddMaxEquality(max_val, [int(arr_a[i]) * x[i] for i in range(len(x))]) model.Add(max_val <= 50) # 目标函数直接用线性表达式构建,不需要在目标函数内部调用g(x) obj = sum(3 * int(arr_b[i]) * x[i] + 2 * int(arr_c[i]) * x[i] for i in range(len(x))) model.Minimize(obj)
场景B:函数输出高度非线性,无法拆成CP-SAT内置线性/逻辑表达式
放弃在建模阶段把函数嵌入约束的思路,改用求解器解回调机制:在求解器每迭代得到一个可行解时,再拿到x的实际0/1取值,传入numpy数组调用自定义函数做校验,不满足约束就直接剪枝:
class DynamicConstraintCallback(cp_model.CpSolverSolutionCallback): def __init__(self, x_vars, check_func, n_closed_limit=10): super().__init__() self.x_vars = x_vars self.check_func = check_func self.n_closed_limit = n_closed_limit def on_solution_callback(self): # 把当前解的x值转成自定义函数需要的numpy数组格式 current_x = np.array([self.value(v) for v in self.x_vars], dtype=np.int32) # 调用自定义函数拿到动态计算结果 n_closed = self.check_func(np.where(current_x == 0)[0]) # 校验约束,不满足就停止当前分支搜索 if n_closed >= self.n_closed_limit: self.StopSearch()
求解器运行时传入回调即可:
solver = cp_model.CpSolver() callback = DynamicConstraintCallback(x, self_defined_function, n_closed_limit=10) status = solver.Solve(model, callback)
3. 简易测试约束的正确写法
之前测试的n_closed <10约束不需要调用自定义函数,直接用线性求和实现即可:
total_closed = sum(1 - x[i] for i in range(len(x))) model.Add(total_closed < 10)
如果需要扩展更复杂的自定义逻辑校验,直接复用上面的回调机制,不要在建模阶段硬编码无动态语义的固定值。
内容的提问来源于stack exchange,提问作者Branko Mo
相关产品推荐
相关产品推荐

