本文详解如何用 pulp 构建整数线性规划（ilp）模型，将正数列表精确划分为指定数量的子集，使各子集和尽可能接近理论均值；重点对比“最小化绝对偏差和”与“最小化最大子集和”两类建模策略，提供稳定、高效且可复现的工业级实现方案。
本文详解如何用 pulp 构建整数线性规划（ilp）模型，将正数列表精确划分为指定数量的子集，使各子集和尽可能接近理论均值；重点对比“最小化绝对偏差和”与“最小化最大子集和”两类建模策略，提供稳定、高效且可复现的工业级实现方案。
在负载均衡、资源分配、并行任务调度等实际场景中（如将不同大小的文件分发至 N 个计算线程、或为 N 名工人分配不同重量的货物），核心挑战是：给定一个正整数列表，将其严格划分为 N 个互斥非空子集，使得各子集元素之和的差异最小化。该问题本质是经典的 Number Partitioning 的多集推广（N-way partitioning），属于 NP-hard 组合优化问题。虽然贪心或启发式算法（如 longest-processing-time first）速度快，但无法保证全局最优；而本文聚焦于可证明最优的数学规划解法——尤其适配中小规模（≤100 项）、高精度要求（如金融、科学计算）的应用场景。
核心建模思路：两种目标函数的权衡
原始方案采用 最小化绝对偏差之和（minimize Σ|sumₖ − avg|），通过引入辅助连续变量 X[k] 和成对约束线性化绝对值：
prob += sum(x[i][k] * num[i] for i in range(N)) - X[k] = avg prob += lpSum(X) # 最小化总偏差
此模型逻辑严谨，但存在显著缺陷：
- 变量与约束数量随 N_sets × len(numbers) 线性增长，且每个绝对值需 2 条约束；
- CBC 求解器在多线程模式下因分支定界搜索路径随机性，导致结果不可复现（同一输入多次运行输出不同划分）；
- 强制 gapRel=0（零相对间隙）虽保证理论最优，但求解时间可能呈指数级上升（实测超 1 小时未收敛）。
更优实践是采用 最小化最大子集和（minimax formulation）：
max_sum = LpVariable("max_sum", cat="Continuous")
for k in range(N_sets):
prob += lpSum(x[i][k] * num[i] for i in range(len(num))) <p>该策略将目标维度从 N 降至 1，约束数量减少约一半，且消除了所有 X[k] 变量。其物理意义明确：<strong>优先压制最重负载，自然促使整体均衡</strong>。大量实测表明，在相对间隙 gapRel=0.0001（即 0.01%）下，CBC 可在秒级内返回高质量解（如原例 28 个数分 4 组仅耗时 ~10 秒），且 threads=None（自动线程管理）比显式指定线程数更稳定高效。</p><h3>工业级实现：规范化、健壮性与可读性</h3><p>以下为重构后的生产就绪代码，融合了归一化预处理、清晰索引与最佳实践：</p><pre class="brush:php;toolbar:false;">import pulp
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, value
# === 用户配置 ===
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]
n_sets = 4
# === 模型构建 ===
total = sum(numbers)
avg = total / n_sets
# 创建问题实例
prob = LpProblem("BalancedPartition", LpMinimize)
# 决策变量：x[i][k] = 1 表示第 i 个数分配至第 k 组
x = [[LpVariable(f"x_{i}_{k}", cat="Binary")
for k in range(n_sets)] for i in range(len(numbers))]
# 辅助变量：所有子集和的上界
max_sum = LpVariable("max_sum", lowBound=avg, cat="Continuous")
# 目标函数：最小化最大子集和
prob += max_sum
# 约束1：每个数必须且仅能分配到一个组
for i in range(len(numbers)):
prob += lpSum(x[i][k] for k in range(n_sets)) == 1
# 约束2：每组至少包含一个数（防空集）
for k in range(n_sets):
prob += lpSum(x[i][k] for i in range(len(numbers))) >= 1
# 约束3：每组和不超过上界
for k in range(n_sets):
prob += lpSum(x[i][k] * numbers[i] for i in range(len(numbers))) 0.99: # 避免浮点误差
groups[k].append(num)
break
# 输出统计
print("=== 分组结果 ===")
for k in range(n_sets):
s = sum(groups[k])
diff_abs = abs(s - avg)
diff_frac = diff_abs / avg
print(f"组 {k+1}: {groups[k]} → 和={s}, 绝对偏差={diff_abs:.1f}, 相对偏差={diff_frac:.6f}")
print(f"\n理论均值: {avg:.1f}")
print(f"最大子集和: {value(max_sum):.1f} (偏差={value(max_sum)-avg:.1f})")
关键注意事项与进阶建议
- 归一化提升数值稳定性：当数值量级差异大（如含百万级与个位数），建议预处理：fracs = [n / total for n in numbers]，并将约束中的 max_sum 替换为 max_frac（目标设为 1/n_sets）。这避免了 CBC 因浮点精度导致的约束松弛失效。
- 强制最优性的代价：若业务场景严格要求 gapRel=0，请预留充足时间（>1 小时）并监控内存；对于 len(numbers) > 40，建议切换至商业求解器（如 Gurobi）或启用割平面（cuts=True）。
- 验证解的有效性：始终检查 prob.status 并手动验证分组互斥性与完整性（sum(len(v) for v in groups.values()) == len(numbers)）。
- 替代方案参考：对超大规模问题（>100 项），可先用 K-Means 聚类初始化，再以 ILP 微调；或采用动态规划近似（仅适用于 sum(numbers) 较小的情形）。
综上，最小化最大子集和 + 归一化 + 合理相对间隙 是兼顾最优性、鲁棒性与效率的黄金组合。它不牺牲数学严谨性，却将求解时间从“不可接受”压缩至“生产可用”，是工程实践中值得首选的平衡解。
