如何在OR-Tools CP模型中添加X[i] ≤ max(X[:i])+1约束？

核心思路 #

通过维护前缀最大值变量序列，递推定义每个位置的前缀最大值，再基于该序列实现目标约束。这种方式既避免冗余变量，又能保证剪枝效果，完全兼容现有目标函数。

具体实现步骤 #

1. 定义前缀最大值变量
   创建与X长度相同的变量序列prefix_max，其中prefix_max[i]表示X[0]到X[i]的最大值：

   • 第一个元素：prefix_max[0]直接等于X[0]，用AddEquality约束绑定
   • 后续元素：对每个i≥1，用OR-Tools内置的AddMaxEquality方法，将prefix_max[i]定义为max(prefix_max[i-1], X[i])

2. 添加目标约束
   对每个i≥1，添加约束X[i] <= prefix_max[i-1] + 1——因为prefix_max[i-1]恰好是X[:i]（前i个元素）的最大值。

完整代码示例 #

from ortools.sat.python import cp_model

# 初始化模型
model = cp_model.CpModel()

# 假设X的长度为n，元素取值范围是[lb, ub]
n = 6
lb = 0
ub = 3

# 创建X变量序列
X = [model.NewIntVar(lb, ub, f'X[{i}]') for i in range(n)]

# 创建前缀最大值变量序列
prefix_max = [model.NewIntVar(lb, ub, f'prefix_max[{i}]') for i in range(n)]

# 绑定第一个前缀最大值
model.AddEquality(prefix_max[0], X[0])

# 递推定义后续前缀最大值，并添加目标约束
for i in range(1, n):
    # 定义prefix_max[i] = max(prefix_max[i-1], X[i])
    model.AddMaxEquality(prefix_max[i], [prefix_max[i-1], X[i]])
    # 添加约束X[i] <= prefix_max[i-1] + 1
    model.Add(X[i] <= prefix_max[i-1] + 1)

# 假设已有目标函数min(z)（这里z可以是全局最大值，比如prefix_max[-1]）
z = prefix_max[-1]
model.Minimize(z)

# 求解器部分（可选）
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print("最优解：")
    print([solver.Value(x) for x in X])

方案优势 #

• 无冗余变量：仅创建与X等长的前缀最大值变量，数量可控
• 有效剪枝：每个prefix_max变量被严格约束为对应前缀的真实最大值，不会出现上界松弛导致的搜索空间浪费
• 兼容现有目标：无需修改已有的min(z)目标（z可以直接用最后一个前缀最大值，即全局最大值）

示例验证 #

• 合法解[0, 1, 2, 0, 2, 3]：每个X[i]都满足X[i] <= max(X[:i])+1，约束会放行该解
• 非法解[0, 1, 1, 2, 4]：X[4]=4，而max(X[:4])=2，4>2+1，约束会直接排除该解

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