OR-Tools中用最小化偏差替代强制等式实现近似均匀分配

问题背景 #

给定包含不同颜色球的袋子配置如下：

需求是确定每个袋子取多少个，使得最终每种颜色的球数量相等。

精确解场景的实现代码 #

当存在精确解时，以下OR-Tools代码可返回有效权重：

from ortools.sat.python import cp_model
from itertools import flatten

bags = [
    [10,5,85,0],
    [25,50,25,0],
    [0,100,0,0],
    [90,5,5,0],
    [2,0,98,0],
    [0,0,0,100]
]

bags_n = len(bags)
color_n = len(bags[0])

print(f'Bags: {bags_n}')
print(f'Colors: {color_n}')

color_count = [0] * color_n
for c in range(color_n):
    for b in bags:
        color_count[c] += b[c]

print(color_count)
print(f'Initial total: {sum(color_count)}')
print(f'Initial equal share: {sum(color_count)//color_n}')

model = cp_model.CpModel()

weights = []
for r in range(bags_n):
    weights.append(model.NewIntVar(1, 1000, f'Weight of Bag: {r}'))

total = model.NewIntVar(0, 100000, 'total')
model.Add(
    sum(flatten(
        [[bags[r][c] * weights[r] for r in range(bags_n)] for c in range(color_n)]
    )) == total
)

equal = model.NewIntVar(0, 10000, 'equal share')
model.AddDivisionEquality(equal, total, color_n)

for c in range(color_n):
    # 修正差值范围：允许正负偏差
    diff_c = model.NewIntVar(-1000, 1000, f'diff_{str(c)}')
    model.Add(diff_c == sum([bags[r][c] * weights[r] for r in range(bags_n)]) - equal)
    model.AddAbsEquality(0, diff_c)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Objective value: {solver.ObjectiveValue()}\n')
    for v in weights:
        print(f'{solver.Value(v)}')
    print(f'total = {solver.Value(total)}')
    print(f'equal share = {solver.Value(equal)}')
else:
    print(f'Solver status: {status}')

注：原代码中diff_c的初始范围设为0,1000存在错误，差值可能为负，修正后才能正确求解精确解。

该代码返回的有效权重为：

82
2
70
78
5
79

无精确解的场景 #

当修改袋子配置为以下情况时，不存在满足所有颜色数量完全相等的权重，模型会变为不可行：

bags = [
    [50,40,10],
    [30,20,50],
    [30,30,40],
    [30,25,45],
]

修改方案：近似均匀分布求解 #

当没有精确解时，需将"强制所有颜色数量相等"的硬约束，改为最小化颜色数量与目标值的偏差，以下是两种常用优化方向：

方案1：最小化所有颜色偏差的绝对和 #

此目标追求整体偏差总和最小，适合希望总差异尽可能小的场景：

from ortools.sat.python import cp_model
from itertools import flatten

bags = [
    [50,40,10],
    [30,20,50],
    [30,30,40],
    [30,25,45],
]

bags_n = len(bags)
color_n = len(bags[0])

model = cp_model.CpModel()

# 定义每个袋子的权重（正整数）
weights = []
for r in range(bags_n):
    weights.append(model.NewIntVar(1, 1000, f'Weight of Bag: {r}'))

# 计算每种颜色的总数量
color_totals = []
for c in range(color_n):
    total_c = model.NewIntVar(0, 100000, f'Total color {c}')
    model.Add(total_c == sum([bags[r][c] * weights[r] for r in range(bags_n)]))
    color_totals.append(total_c)

# 计算所有颜色的总球数
total = model.NewIntVar(0, 300000, 'total')
model.Add(total == sum(color_totals))

# 定义目标均衡值
equal = model.NewIntVar(0, 100000, 'equal share')
model.AddDivisionEquality(equal, total, color_n)

# 计算每个颜色的偏差绝对值
abs_diffs = []
for c in range(color_n):
    diff = model.NewIntVar(-100000, 100000, f'diff_{c}')
    model.Add(diff == color_totals[c] - equal)
    abs_diff = model.NewIntVar(0, 100000, f'abs_diff_{c}')
    model.AddAbsEquality(abs_diff, diff)
    abs_diffs.append(abs_diff)

# 最小化所有偏差绝对值的和
model.Minimize(sum(abs_diffs))

# 求解
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("求解成功：")
    print(f"权重：{[solver.Value(w) for w in weights]}")
    print(f"各颜色数量：{[solver.Value(ct) for ct in color_totals]}")
    print(f"目标均衡值：{solver.Value(equal)}")
    print(f"总偏差绝对值和：{solver.ObjectiveValue()}")
else:
    print(f"求解状态：{status}")

方案2：最小化最大偏差（最小最大准则） #

此目标追求最不均衡的颜色与目标值的差异尽可能小，适合希望所有颜色数量尽可能接近的场景：

from ortools.sat.python import cp_model
from itertools import flatten

bags = [
    [50,40,10],
    [30,20,50],
    [30,30,40],
    [30,25,45],
]

bags_n = len(bags)
color_n = len(bags[0])

model = cp_model.CpModel()

weights = []
for r in range(bags_n):
    weights.append(model.NewIntVar(1, 1000, f'Weight of Bag: {r}'))

color_totals = []
for c in range(color_n):
    total_c = model.NewIntVar(0, 100000, f'Total color {c}')
    model.Add(total_c == sum([bags[r][c] * weights[r] for r in range(bags_n)]))
    color_totals.append(total_c)

total = model.NewIntVar(0, 300000, 'total')
model.Add(total == sum(color_totals))

equal = model.NewIntVar(0, 100000, 'equal share')
model.AddDivisionEquality(equal, total, color_n)

# 定义最大偏差绝对值变量
max_abs_diff = model.NewIntVar(0, 100000, 'max_abs_diff')

for c in range(color_n):
    diff = model.NewIntVar(-100000, 100000, f'diff_{c}')
    model.Add(diff == color_totals[c] - equal)
    abs_diff = model.NewIntVar(0, 100000, f'abs_diff_{c}')
    model.AddAbsEquality(abs_diff, diff)
    # 约束每个偏差不超过最大偏差值
    model.Add(abs_diff <= max_abs_diff)

# 最小化最大偏差绝对值
model.Minimize(max_abs_diff)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("求解成功：")
    print(f"权重：{[solver.Value(w) for w in weights]}")
    print(f"各颜色数量：{[solver.Value(ct) for ct in color_totals]}")
    print(f"目标均衡值：{solver.Value(equal)}")
    print(f"最大偏差绝对值：{solver.ObjectiveValue()}")
else:
    print(f"求解状态：{status}")

关键修改点说明 #

1. 移除了model.AddAbsEquality(0, diff_c)的硬约束，不再强制颜色数量完全等于目标值
2. 引入偏差变量并定义优化目标，将问题从可行性验证转为最小化优化问题
3. 保留了权重的整数约束，符合实际取袋数量为整数的需求

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