等和子集划分线性规划实现的优化与稳定性问题咨询

需求背景 #

该需求用于将正数列表划分为N个子集，使各子集总和尽可能均衡，典型应用场景包括：

• 将不同记录数的文件分配给N条并行处理线，保证每条线处理的总记录数尽可能均等
• 将不同重量的物品分配给N人搬运，使每人负重尽可能一致
  要求实现绝对最优解（非贪心算法）。

现有线性规划实现及问题 #

以下是基于线性规划（最小化绝对差之和）的实现代码：

# Take a list of numbers and partition them into a desired number of sets,
# ensuring that the sum within each set is as close as possible
# to the sum of all numbers divided by the number of sets.

# USER SETTINGS
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

import numpy as np
import pulp
from pulp import *

# Calculate the desired size of each set
S = N_sets_to_make
average_size = sum(list_of_numbers) / S
sizes = [average_size] * S

# Create the coefficient matrix
N = len(list_of_numbers)
A = np.array(list_of_numbers, ndmin = 2)

# Create the pulp model
prob = LpProblem("Partitioning", LpMinimize)

# Create the pulp variables
# x_names : binary variables encoding the presence of each initial number in each final set
x_names = ['x_'+str(i) for i in range(N * S)]
x = [LpVariable(x_names[i], lowBound = 0, upBound = 1, cat = 'Integer') for i in range(N * S)]
# X_names : continuous positive variables encoding the absolute difference between each final set sum and the desired size
X_names = ['X_'+str(i) for i in range(S)]
X = [LpVariable(X_names[i], lowBound = 0, cat = 'Continuous') for i in range(S)]

# Add the objective to the model (mimimal sum of X_i)
prob += LpAffineExpression([(X[i], 1) for i in range(S) ])

# Add the constraints to the model

# Constraints forcing each initial number to be in one and only one final set
for c in range(N):
    prob += LpAffineExpression([(x[c+m*N],+1) for m in range(S)]) == 1

# Constraints forcing each final set to be non-empty
for m in range(S):
    prob += LpAffineExpression([(x[i],+1) for i in range(m,(m+1)*N)]) >= 1

# Constraints encoding the absolute values
for m in range(S):    
        cs = [c for c in range(N) if A[0,c] != 0]
        prob += LpAffineExpression([(x[c+m*N],A[0,c]) for c in cs]) - X[m] <= sizes[m]
        prob += LpAffineExpression([(x[c+m*N],A[0,c]) for c in cs]) + X[m] >= sizes[m]

# Solve the model
prob.solve(PULP_CBC_CMD(gapRel = 0, timeLimit = 3600, threads = 1))

# Extract the solution
values_of_x_i = [value(x[i]) for i in range(N * S)]
selected_ind_initial_numbers = [(list(range(N)) * S)[i] for i,l in enumerate(values_of_x_i) if l == 1]
selected_ind_final_sets = [(list((1 + np.repeat(range(S), N)).astype('int64')))[i] for i,l in enumerate(values_of_x_i) if l == 1]
ind_final_set_for_each_initial_number = [x for _, x in sorted(zip(selected_ind_initial_numbers, selected_ind_final_sets))]

# Find the numbers that ended up in each final set
d = dict()
for m, n in sorted(zip(ind_final_set_for_each_initial_number, list_of_numbers)) :
    if m in d :
        d[m].append(n)
    else :
        d[m] = [n]
print(d)

# And their sums
s = [sum(l) for i, l in enumerate(d.values())]
print(s)

# And the absolute differences of their sums from the desired sum
absdiffs = [np.abs(s[i] - sizes[i]) for i in range(len(s))]
print(absdiffs)

# And the absolute fractional differences
print([absdiffs[i]/sizes[i]/S for i in range(len(absdiffs))])

运行中遇到两难问题：

• 设置threads>1时，多次运行结果不一致
• 单线程运行时求解速度过慢

已尝试的优化及验证 #

编辑1：归一化优化提升求解速度 #

通过归一化系数矩阵和目标比例，提升求解速度并使问题独立于总数值之和，同时发现设置threads=None时速度远快于指定线程数。修改点如下：
在sizes = [average_size] * S后添加：

fracs = [1 / S] * S

在A = np.array(list_of_numbers, ndmin = 2)后添加：

An = A / np.sum(A, axis = 1, keepdims = True)

将绝对值约束替换为：

prob += LpAffineExpression([(x[c+m*N],An[0,c]) for c in cs]) - X[m] <= fracs[m]
prob += LpAffineExpression([(x[c+m*N],An[0,c]) for c in cs]) + X[m] >= fracs[m]

求解语句改为：

prob.solve(PULP_CBC_CMD(gapRel = 0, timeLimit = 3600, threads = None))

编辑2：max_sum方案的局限性 #

测试了移除X变量、以最小化最大子集和为目标的方案，结合归一化后求解速度极快，但即使运行至最优解，子集和差异总和仍高于原方法，无法达到期望的绝对最优性。

补充测试验证 #

使用测试用例list_of_numbers = [10000] + [100, 200, 300, 400, 500] * 5、N_sets_to_make = 3验证：

• 基于max_sum的方案无法实现绝对最优
• 原方法（最小化绝对差之和）可达到更优结果

寻求解决方案 #

迫切需要能提供绝对最优解的代码改进建议或替代实现方案。

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