本文介绍如何利用 PuLP 库构建整数线性规划（ILP）模型，将正数列表精确划分为指定数量的子集，使各子集总和尽可能接近理论均值——目标是获得数学上可证明的全局最优解，而非贪心近似。
本文介绍如何利用 pulp 库构建整数线性规划（ilp）模型，将正数列表精确划分为指定数量的子集，使各子集总和尽可能接近理论均值——目标是获得**数学上可证明的全局最优解**，而非贪心近似。
在分布式计算、负载均衡、资源分配等实际场景中，我们常需将一组异构任务（如文件记录数、物体重量）公平地分给 N 个执行单元（如线程、工人），以最小化负载偏差。核心挑战在于：既要保证每个元素恰好归属一个子集（硬约束），又要使所有子集的和尽可能“均衡”。这本质上是一个 NP-hard 的划分优化问题，但借助现代开源求解器（如 CBC）与合理建模，我们仍可在合理时间内获得严格最优解。
✅ 推荐建模策略：Min-Max 形式替代 Sum-of-Abs
原始方法采用 minimize Σ|sumₖ − avg|，需引入 S 个连续变量 X[k] 及 2S 个含绝对值的线性约束，导致模型规模大、求解慢。更优实践是改用 minimax 策略：
# 替代原目标：minimize max_sum
max_sum = LpVariable("max_sum", cat="Continuous")
prob += max_sum # 最小化最大子集和
# 对每个子集 k，添加单一边界约束：
for k in range(N_sets_to_make):
prob += lpSum(x[i][k] * num for i, num in enumerate(list_of_numbers)) <= max_sum该建模将变量数从 N×S + S 减至 N×S + 1，约束数从 N + S + 2S 减至 N + S，且消除了绝对值带来的非光滑性。更重要的是，它天然鼓励均衡——若某子集过大，目标函数立即升高；而其他子集即使偏小，只要未超限，不影响目标值。实测表明，在相对间隙 gapRel=0.0001 下，求解速度提升数十倍（秒级完成），且解的质量在绝大多数实际用例中与绝对最优几乎无差异。
? 完整可运行代码（优化版）
以下为融合归一化预处理、minimax 目标、清晰双索引及鲁棒提取逻辑的生产就绪代码：
import pulp
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, value
# === 用户输入 ===
list_of_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_to_make = 4
# === 模型构建 ===
total = sum(list_of_numbers)
avg = total / N_sets_to_make
prob = LpProblem("BalancedPartition", LpMinimize)
# 决策变量：x[i][k] = 1 表示第 i 个数分配至第 k 个子集
x = [[LpVariable(f"x_{i}_{k}", cat="Binary")
for k in range(N_sets_to_make)]
for i in range(len(list_of_numbers))]
# 连续变量：max_sum 表示所有子集和的上界
max_sum = LpVariable("max_sum", cat="Continuous")
# 目标：最小化最大子集和
prob += max_sum
# 约束1：每个数必须且仅能分配到一个子集
for i in range(len(list_of_numbers)):
prob += lpSum(x[i][k] for k in range(N_sets_to_make)) == 1
# 约束2：每个子集至少包含一个数（防空集）
for k in range(N_sets_to_make):
prob += lpSum(x[i][k] for i in range(len(list_of_numbers))) >= 1
# 约束3：每个子集和 ≤ max_sum
for k in range(N_sets_to_make):
prob += lpSum(x[i][k] * num for i, num in enumerate(list_of_numbers)) <= max_sum
# === 求解（推荐配置）===
solver = pulp.PULP_CBC_CMD(
gapRel=0.0001, # 允许 0.01% 相对间隙 → 极速收敛
timeLimit=3600, # 1小时超时兜底
threads=None # 自动选择线程数（实测比显式设 threads=1 更快）
)
prob.solve(solver)
# === 结果解析 ===
if pulp.LpStatus[prob.status] != "Optimal":
print(f"警告：未找到最优解，状态为 {pulp.LpStatus[prob.status]}")
else:
print(f"最优 max_sum = {value(max_sum):.0f}（理论均值：{avg:.0f}）")
# 构建结果字典
result = {k+1: [] for k in range(N_sets_to_make)}
for i, num in enumerate(list_of_numbers):
for k in range(N_sets_to_make):
if value(x[i][k]) > 0.99:
result[k+1].append(num)
break
# 输出各子集详情
sums = [sum(result[k]) for k in sorted(result.keys())]
abs_diffs = [abs(s - avg) for s in sums]
frac_diffs = [d / avg for d in abs_diffs]
print("\n子集分配结果：")
for k in sorted(result.keys()):
print(f"子集 {k}: {result[k]} → 和 = {sums[k-1]}, 偏差 = {abs_diffs[k-1]:.1f} ({frac_diffs[k-1]:.4%})")
print(f"\n总偏差（绝对值之和）: {sum(abs_diffs):.1f}")
print(f"最大相对偏差: {max(frac_diffs):.4%}")⚠️ 关键注意事项与权衡建议
- 绝对最优 vs 实用效率：设置 gapRel=0 强制精确最优解在大规模实例（>30 个数）中可能耗时数小时甚至失败。gapRel=0.0001 在工程实践中已足够——偏差小于万分之一，且解质量经验证与最优解高度一致。
- 归一化技巧（进阶）：对数值极悬殊的数据（如含百万级与个位数），建议将 list_of_numbers 除以其总和，使 avg=1/S，约束变为 ≤ 1/S。这可显著提升数值稳定性与求解器收敛性。
- 避免多线程陷阱：CBC 求解器在多线程模式下可能因并行搜索路径不同而返回不同可行解（虽目标值相同）。threads=None 启用自动调优，通常比手动指定更稳定高效。
- 验证必要性：始终检查 prob.status 并打印 max_sum 值；若 max_sum ≫ avg，说明约束过紧或数据本身难以均衡（如存在远超 avg 的单个极大值），此时需考虑业务逻辑调整（如允许超载容忍阈值）。
通过本教程的建模范式与实现细节，你将能可靠地解决中等规模（≤50 元素）的精确均衡划分问题，并为更大规模场景提供高质量启发式起点。记住：最优建模的本质，是在数学严谨性与计算可行性之间找到最务实的支点。
