Or-Tools CP求解器：如何高效最小化2的数组元素指数和？

错误原因 #

Or-Tools CP-SAT求解器无法直接处理2^cost[i]这类包含变量指数的表达式。因为cost[i]是无明确上限的整数变量，求解器会判定这会生成无限多的可能取值，从而抛出evaluation error: comprehension iterates over an infinite set错误。

解决方案 #

方案一：利用2的幂指数增长特性，按优先级优化（等价精确解） #

由于2的幂增长速度远快于所有更小幂次的和，最小化sum(2^cost[i])等价于按以下优先级优化：

1. 优先最小化最大的指数值max(cost)
2. 在最大指数值相同的情况下，最小化等于该最大值的元素个数
3. 若仍有多个解，继续最小化次大的指数值，依此类推

可以通过加权求和实现，只要权重足够大以保证优先级顺序：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# 示例参数，可根据实际情况修改
SIZE = range(3)
bound = [1, 2, 3]
# 给cost设置合理上限，避免无限范围
max_cost_upper = max(bound) + 5
cost = [model.NewIntVar(bound[i]+1, max_cost_upper, f"cost_{i}") for i in SIZE]

# 定义最大指数变量
max_cost = model.NewIntVar(min(bound)+1, max_cost_upper, "max_cost")
model.AddMaxEquality(max_cost, cost)

# 统计最大指数的出现次数
count_max = model.NewIntVar(0, len(SIZE), "count_max")
model.Add(count_max == sum(1 for i in SIZE if cost[i] == max_cost))

# 加权最小化，确保优先级：max_cost权重远大于count_max
model.Minimize(max_cost * 100 + count_max)

# 求解并输出结果
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    print("最优cost值:", [solver.Value(c) for c in cost])
    print("2^cost的和:", sum(2**solver.Value(c) for c in cost))

该方案无需处理大整数，求解效率高，且结果与精确最小化幂次和完全一致。

方案二：精确计算幂次和，用整数变量关联指数与幂值 #

如果需要直接精确计算并最小化幂次和，可以为每个cost[i]对应的2^cost[i]创建整数变量，通过约束关联两者：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# 示例参数
SIZE = range(3)
bound = [1, 2, 3]
max_cost_upper = max(bound) + 5
cost = [model.NewIntVar(bound[i]+1, max_cost_upper, f"cost_{i}") for i in SIZE]

# 为每个cost创建对应的2^cost变量，并添加约束
pow2_vars = []
for i in SIZE:
    min_pow = 2 ** (bound[i]+1)
    max_pow = 2 ** max_cost_upper
    pow_var = model.NewIntVar(min_pow, max_pow, f"pow2_{i}")
    pow2_vars.append(pow_var)
    # 枚举所有可能的cost值，关联对应的幂值
    for c_val in range(bound[i]+1, max_cost_upper+1):
        model.Add(pow_var == 2**c_val).OnlyEnforceIf(cost[i] == c_val)

# 定义总幂次和变量并最小化
total_sum = model.NewIntVar(
    sum(2**(b+1) for b in bound),
    sum(2**max_cost_upper for _ in SIZE),
    "total_sum"
)
model.Add(total_sum == sum(pow2_vars))
model.Minimize(total_sum)

# 求解输出
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    print("最优cost值:", [solver.Value(c) for c in cost])
    print("2^cost的和:", solver.Value(total_sum))

此方案可精确获取幂次和，但需合理设置cost的上限，避免变量范围过大导致求解速度下降。

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