基于or-tools实现约束空间无偏随机化的可扩展方案咨询

我使用or-tools编写了一段简单代码，目标是随机生成3个变量，满足三者之和为定值。我通过添加随机hint的方式期望求解器每次返回不同结果，但统计取值频率后发现，仅第一个变量无偏符合均匀分布，其余变量均偏向0，分布存在偏差。

代码如下：

from ortools.sat.python import cp_model
import numpy as np
import matplotlib.pyplot as plt

model = cp_model.CpModel()

mx = 500
x = model.NewIntVar(0, mx, 'x')
y = model.NewIntVar(0, mx, 'y')
z = model.NewIntVar(0, mx, 'z')

freqX = [0] * (mx + 1)
freqY = [0] * (mx + 1)
freqZ = [0] * (mx + 1)

model.Add(x + y + z == mx)
solver = cp_model.CpSolver()
solver.parameters.cp_model_presolve = False

for i in range(10000):
    model.ClearAssumptions()
    model.ClearHints()
    model.AddHint(x, np.random.randint(0, mx))
    model.AddHint(y, np.random.randint(0, mx))
    model.AddHint(z, np.random.randint(0, mx))
    
    status = solver.Solve(model)
    
    freqX[solver.Value(x)] += 1
    freqY[solver.Value(y)] += 1
    freqZ[solver.Value(z)] += 1

plt.subplot(311)
plt.bar(range(mx+1), freqX, width=1.0)
plt.subplot(312)
plt.bar(range(mx+1), freqY, width=1.0)
plt.subplot(313)
plt.bar(range(mx+1), freqZ, width=1.0)
plt.savefig('foo.svg')

输出分布如下图：

我已尝试评论区建议的无效hint方案，得到的分布如下图：

请问有什么可扩展性最高的方法，可以让约束下的所有变量都服从无偏均匀分布？

偏差原因 #

当前方案出现偏差的核心原因是：CP-SAT求解器的AddHint仅作为搜索优先级的参考，而非强制约束，求解器默认的变量分支顺序与变量定义顺序绑定，会优先满足先定义变量的hint要求，剩余变量的取值空间被大幅压缩，最终出现后定义变量偏向0的偏态分布。

可扩展性最高的通用方案 #

如果需要适配任意复杂约束场景（不止是三变量和为定值的简单场景），随机线性目标采样法的可扩展性最高，不需要针对约束类型做定制修改，直接适配所有CP-SAT支持的约束规则，数学上可以保证解的无偏均匀性：

• 每次采样前，为所有变量分配随机权重，将最大化（或最小化）该随机权重的线性组合作为临时优化目标
• 搭配随机分支策略和动态随机种子，避免求解器搜索逻辑的确定性偏差

修改后代码示例 #

from ortools.sat.python import cp_model
import numpy as np
import matplotlib.pyplot as plt

model = cp_model.CpModel()
mx = 500
x = model.NewIntVar(0, mx, 'x')
y = model.NewIntVar(0, mx, 'y')
z = model.NewIntVar(0, mx, 'z')
model.Add(x + y + z == mx)

freqX = [0] * (mx + 1)
freqY = [0] * (mx + 1)
freqZ = [0] * (mx + 1)

solver = cp_model.CpSolver()
solver.parameters.cp_model_presolve = False
# 开启随机分支策略
solver.parameters.search_branching = cp_model.CpSolverParameters.RANDOM_BRANCHING

for i in range(10000):
    # 清空上一轮的目标函数
    model.ClearObjective()
    # 生成随机权重，构造随机线性目标
    w_x, w_y, w_z = np.random.rand(3)
    model.Maximize(w_x * x + w_y * y + w_z * z)
    # 每次使用不同的随机种子
    solver.parameters.random_seed = i
    
    status = solver.Solve(model)
    
    freqX[solver.Value(x)] += 1
    freqY[solver.Value(y)] += 1
    freqZ[solver.Value(z)] += 1

# 绘图部分不变
plt.subplot(311)
plt.bar(range(mx+1), freqX, width=1.0)
plt.subplot(312)
plt.bar(range(mx+1), freqY, width=1.0)
plt.subplot(313)
plt.bar(range(mx+1), freqZ, width=1.0)
plt.savefig('foo.svg')

特定场景的高效方案 #

如果你的场景固定为「N个非负整数和为定值」的约束，不需要适配其他约束，直接用断点插分法即可，不需要调用求解器，效率是最高的，且数学上严格均匀：

import numpy as np
mx = 500
for _ in range(10000):
    # 生成2个不重复的随机断点
    p1, p2 = np.random.choice(range(1, mx), size=2, replace=False)
    if p1 > p2:
        p1, p2 = p2, p1
    x, y, z = p1, p2 - p1, mx - p2
    # 统计频率即可

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