基于均值优化的数据集子集划分：混合整数规划与启发式方法

from statistics import mean
import pulp

def solve_subset_partitioning(superset_elements, subset_sizes):
    """
    使用 PuLP 解决基于均值优化的数据集子集划分问题。

    Args:
        superset_elements (list): 超集中的所有元素列表。
        subset_sizes (list): N个子集各自的目标大小列表。

    Returns:
        tuple: (list of lists, list of floats) 分割后的子集元素列表和每个子集的均值。
    """

    N = len(subset_sizes)
    M = len(superset_elements)

    # 验证输入
    if sum(subset_sizes) != M:
        raise ValueError("所有子集大小之和必须等于超集元素总数。")

    # 计算超集均值
    superset_mean = mean(superset_elements)

    # 创建 PuLP 问题实例
    set_partitioning_model = pulp.LpProblem("Set_Partitioning_Model", pulp.LpMinimize)

    # 决策变量：x_s_i = 1 如果超集中的第 i 个元素被分配到第 s 个子集中
    # covering[s] 是一个列表，其中包含子集 s 的 M 个二元变量
    covering = {}
    for s in range(N):
        vals = []
        for i, v in enumerate(superset_elements):
            vals.append(
                pulp.LpVariable(
                    f"x_set_{s}_element_idx_{i:>02}_val_{v}",
                    lowBound=0,  # 0
                    upBound=1,   # 1
                    cat=pulp.LpBinary, # 二进制变量
                )
            )
        covering[s] = vals

    # 辅助变量：用于处理绝对误差
    abs_sum_errs = []
    for s_i in range(N):
        abs_sum_errs.append(pulp.LpVariable(f"set_{s_i}_sum_error_abs", lowBound=0))

    # 目标函数：最小化所有子集绝对误差之和
    set_partitioning_model += pulp.lpSum(abs_sum_errs), "Minimize_Absolute_Sum_Errors"

    # 添加约束
    for s_i, st_vars in covering.items():
        # 计算每个子集的实际总和
        current_set_sum = pulp.lpSum([p * superset_elements[i] for i, p in enumerate(st_vars)])

        # 计算每个子集的目标总和 (子集大小 * 超集均值)
        target_set_sum = subset_sizes[s_i] * superset_mean

        # 定义子集总和误差变量
        set_sum_err = pulp.LpVariable(f"set_{s_i}_sum_error")
        set_partitioning_model += set_sum_err == current_set_sum - target_set_sum, f"Set_{s_i}_Sum_Error_Definition"

        # 绝对值线性化约束
        set_partitioning_model += abs_sum_errs[s_i] >= set_sum_err, f"Abs_Error_Upper_Bound_Pos_{s_i}"
        set_partitioning_model += abs_sum_errs[s_i] >= -set_sum_err, f"Abs_Error_Upper_Bound_Neg_{s_i}"

    # 约束1: 每个子集的大小必须符合预设
    for s_i, st_vars in enumerate(covering.values()):
        set_partitioning_model += pulp.lpSum(st_vars) == subset_sizes[s_i], f"Set_{s_i}_Size_Constraint"

    # 约束2: 超集中的每个元素只能被使用一次
    # zip(*covering.values()) 将所有子集的变量列表转置，以便按元素索引迭代
    for i, element_vars in enumerate(zip(*covering.values())):
        set_partitioning_model += (
            pulp.lpSum(element_vars) == 1,
            f"Element_{i}_Used_Once_Constraint",
        )

    # 求解模型
    set_partitioning_model.solve(pulp.PULP_CBC_CMD(msg=False)) # 使用默认的CBC求解器，静默模式

    # 提取结果
    if pulp.LpStatus[set_partitioning_model.status] == "Optimal":
        result_subsets = []
        result_means = []
        for s_i, st_vars in covering.items():
            current_subset_elements = [
                superset_elements[i] for i, var in enumerate(st_vars) if var.value() == 1
            ]
            result_subsets.append(current_subset_elements)
            result_means.append(mean(current_subset_elements))
        return result_subsets, result_means
    else:
        print(f"未能找到最优解。状态: {pulp.LpStatus[set_partitioning_model.status]}")
        return [], []

# 示例 1：完美分配
print("--- 示例 1：完美分配 ---")
superset1 = [100]*5 + [101]*10 + [102]*5
subset_sizes1 = [2, 4, 14]
subsets1, means1 = solve_subset_partitioning(superset1, subset_sizes1)

print(f"超集均值: {mean(superset1)}")
for i, (subset, mean_val) in enumerate(zip(subsets1, means1)):
    print(f"子集 {chr(65+i)} ({len(subset)} 元素): {subset}, 均值: {mean_val}")
# 预期输出：所有子集均值均为 101

# 示例 2：最佳拟合
print("\n--- 示例 2：最佳拟合 ---")
superset2 = [100]*5 + [103]*10 + [104]*5
subset_sizes2 = [2, 4, 14]
subsets2, means2 = solve_subset_partitioning(superset2, subset_sizes2)

print(f"超集均值: {mean(superset2)}")
for i, (subset, mean_val) in enumerate(zip(subsets2, means2)):
    print(f"子集 {chr(65+i)} ({len(subset)} 元素): {subset}, 均值: {mean_val}")
# 预期输出：子集均值尽可能接近 102.5

from statistics import mean
from numberpartitioning import karmarkar_karp

# 示例 2 的超集数据
superset = [100, 100, 100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104, 104, 104]

print("\n--- 启发式方法：Karmarkar-Karp ---")
print("超集均值:", mean(superset))

# 使用 Karmarkar-Karp 划分成 3 个部分
# 注意：此方法不接受预设的子集大小
for p in karmarkar_karp(superset, num_parts=3).partition:
    print(f"子集 ({len(p)} 元素): {p}, 均值: {mean(p)}")