本文介绍如何利用整数线性规划（ilp）将一组正数精确划分为指定数量的子集，使各子集总和尽可能接近平均值，兼顾最优性、可复现性与计算效率。重点对比“最小化绝对偏差和”与“最小化最大子集和”两类建模策略，并提供稳定、可扩展的pyomo/pulp实现方案。
本文介绍如何利用整数线性规划（ilp）将一组正数精确划分为指定数量的子集，使各子集总和尽可能接近平均值，兼顾最优性、可复现性与计算效率。重点对比“最小化绝对偏差和”与“最小化最大子集和”两类建模策略，并提供稳定、可扩展的pyomo/pulp实现方案。
在分布式任务调度、负载均衡、资源分配等实际场景中，常需将一组具有权重（如文件记录数、物体质量、计算开销）的元素划分为 $ N $ 个组，目标并非简单均分数量，而是最小化各组总权重的不均衡程度。该问题本质是经典的 Partition into $ k $ Subsets with Balanced Sum 问题，属于 NP-hard 组合优化问题。虽然贪心或启发式算法（如 LPT、Karmarkar-Karp）速度快，但无法保证全局最优；而本文聚焦于可验证的精确解法——基于整数线性规划（ILP）的建模与高效求解。
核心建模思路：两种目标函数的权衡
原始方法采用“最小化各子集与目标均值的绝对偏差之和”： $$ \min \sum{m=1}^{S} | \sum{i=1}^{N} ai x{im} - \mu | $$ 其中 $ x_{im} \in {0,1} $ 表示第 $ i $ 个数是否分配至第 $ m $ 个子集，$ \mu = \frac{1}{S}\sum a_i $。为线性化绝对值，需引入辅助连续变量 $ X_m \geq 0 $ 及约束：
prob += lpSum([a[i] * x[i*S + m] for i in range(N)]) - X[m] <= mu prob += lpSum([a[i] * x[i*S + m] for i in range(N)]) + X[m] >= mu
该模型变量数为 $ N \times S + S $，约束数约为 $ N + 2S $，结构清晰但规模较大，且对求解器（如 CBC）的并行稳定性敏感（threads > 1 时结果不一致）。
更优实践是采用 Mini-Max 建模：直接最小化所有子集和的最大值： $$ \min\ \text{max_sum} \quad \text{s.t.} \quad \sum_{i} ai x{im} \leq \text{max_sum},\ \forall m $$ 此方式仅需 1 个连续变量 max_sum 和 $ S $ 条上界约束，变量总数降至 $ N \times S + 1 $，约束更稀疏，显著提升求解鲁棒性与速度。实测表明，在相对间隙 gapRel=0.0001 下，28 个数划分为 4 组的问题可在 1 秒内收敛，且多线程下结果完全可复现。
推荐实现：规范化 + Mini-Max + 稳健求解配置
为消除数值尺度影响并加速收敛，建议对输入做行归一化（即令总和为 1），并将目标设为最小化最大归一化子集和：
import pulp
from pulp import LpProblem, LpMinimize, LpVariable, lpSum
# 用户输入
numbers = [21614, 22716, 1344708, 8948, 136944, 819, 7109,
255182, 556354, 1898763, 1239808, 925193, 173237, 64301,
147896, 824564, 16028, 1021326, 108042, 72221, 368270,
17467, 2953, 52942, 1855, 739627, 460833, 30955]
k = 4
# 归一化：避免大数导致数值不稳定
total = sum(numbers)
norm_numbers = [n / total for n in numbers]
target_frac = 1 / k # 每组理想占比
# 构建 ILP 模型
prob = LpProblem("BalancedPartition", LpMinimize)
x = [[LpVariable(f"x_{i}_{m}", cat="Binary")
for m in range(k)] for i in range(len(numbers))]
max_frac = LpVariable("max_frac", lowBound=0)
# 目标：最小化最大归一化子集和
prob += max_frac
# 约束1：每个数恰好属于一个子集
for i in range(len(numbers)):
prob += lpSum(x[i][m] for m in range(k)) == 1
# 约束2：每组非空（可选，若允许空组可移除）
for m in range(k):
prob += lpSum(x[i][m] for i in range(len(numbers))) >= 1
# 约束3：每组归一化和 ≤ max_frac
for m in range(k):
prob += lpSum(norm_numbers[i] * x[i][m] for i in range(len(numbers))) <= max_frac
# 求解（推荐 threads=None 或 threads=1，gapRel=1e-4）
solver = pulp.PULP_CBC_CMD(gapRel=1e-4, timeLimit=60, threads=1)
prob.solve(solver)
# 解析结果
assignment = [-1] * len(numbers)
for i in range(len(numbers)):
for m in range(k):
if pulp.value(x[i][m]) > 0.5:
assignment[i] = m
break
# 按组聚合
groups = {m: [] for m in range(k)}
for i, m in enumerate(assignment):
groups[m].append(numbers[i])
# 输出统计
group_sums = [sum(groups[m]) for m in range(k)]
print("分组结果:", groups)
print("各组总和:", group_sums)
print("与均值偏差:", [abs(s - total/k) for s in group_sums])
print("最大偏差占比:", max(abs(s - total/k) for s in group_sums) / (total/k))关键注意事项与最佳实践
- ✅ 数值稳定性优先：务必对输入做归一化（或缩放），避免 CBC 求解器因大系数矩阵出现数值误差或求解失败；
- ✅ 求解器配置：设置 threads=1 或 threads=None 可确保结果可复现；gapRel=1e-4 在绝大多数场景下已足够（偏差 < 0.01%），且求解时间从小时级降至秒级；
- ⚠️ 最优性权衡：严格要求 gapRel=0（即 100% 最优）在大规模实例（>50 元素）中可能超时；Mini-Max 模型虽不直接最小化偏差和，但实证显示其解在各组均衡性上与绝对偏差和模型高度一致，且更鲁棒；
- ? 验证解质量：始终检查 prob.status == pulp.LpStatusOptimal，并输出 max_frac 值（理想为 1/k），偏差越小说明均衡性越好；
- ? 可扩展性提示：若元素数 > 100，建议先用聚类或分层采样预降维，或切换至专用求解器（如 Gurobi/CPLEX）以启用高级切割平面与启发式。
综上，通过规范化输入、采用 Mini-Max 目标函数、合理设置求解参数，我们能在保持数学严谨性的同时，获得高效、稳定、可复现的最优划分方案——这正是工业级负载均衡与资源调度所需的坚实基础。
