如何用PuLP实现带数量约束的多分组变量目标和优化分配？

我有多个带整数值的变量，需要把它们分成三组，每组的变量数量是预先定义好的，同时要让每组的数值总和尽可能接近预设的目标值（可高可低），所有变量必须被使用且仅能用一次。

示例数据 #

分组要求 #

也就是组X要包含6个变量，总和尽可能接近200，且需要同时对所有组进行优化。我已经能用PuLP实现单分组优化，但不知道怎么实现多分组划分并基于每组目标和做分配优化，求可行的实现方法。

现有单分组代码 #

from pulp import LpMaximize, LpMinimize, LpProblem, lpSum, LpVariable, PULP_CBC_CMD, value, LpStatus

keys = ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "A10"]
data = [98,20,30,50,20,34,43,21,32,54]

problem_name = 'repex'

prob = LpProblem(problem_name, LpMaximize)

optiSum = 200 # Optimize towards this sum
variableCount = 6 # Number of variables that should be in the group

# Create decision variables
decision_variables = []
for i,n in enumerate(data):
    variable = i
    variable = LpVariable(str(variable), lowBound = 0, upBound = 1, cat= 'Binary')
    decision_variables.append(variable)


# Add constraints
sumConstraint = "" # Constraint on sum of data elements
for i, n in enumerate(decision_variables):
    formula = data[i]*n
    sumConstraint += formula

countConstraint = "" # Constrain on number of elements used
for i, n in enumerate(decision_variables):
        formula = n
        countConstraint += formula

prob += (sumConstraint <= optiSum)
prob += (countConstraint == variableCount)
prob += sumConstraint

# Solve
optimization_result = prob.solve(PULP_CBC_CMD(msg=0))
prob.writeLP(problem_name + ".lp" )
print("Status:", LpStatus[prob.status])
print("Optimal Solution to the problem: ", value(prob.objective))
print ("Individual decision_variables: ")
for v in prob.variables():
    print(v.name, "=", v.varValue)

现有代码输出 #

Status: Optimal
Optimal Solution to the problem:  200.0
Individual decision_variables:
0 = 0.0
1 = 1.0
2 = 0.0
3 = 1.0
4 = 0.0
5 = 1.0
6 = 1.0
7 = 1.0
8 = 1.0
9 = 0.0

解决方案 #

要实现多分组的同时优化，核心是调整决策变量和目标函数，具体实现如下：

核心思路

1. 决策变量：用二维二进制变量x[i][g]表示第i个变量是否分配到第g组
2. 约束条件：
   • 每个变量必须且只能分配到一个组
   • 每组的变量数量严格符合预设值
3. 目标函数：最小化所有组实际总和与目标值的绝对偏差之和，确保多组同时接近各自目标

完整实现代码

from pulp import LpProblem, LpMinimize, lpSum, LpVariable, PULP_CBC_CMD, value, LpStatus

# 变量数据
keys = ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "A10"]
data = [98, 20, 30, 50, 18, 34, 43, 21, 32, 54]
var_count = len(data)

# 分组配置：(组名, 变量数量, 目标总和)
groups = [
    ("X", 6, 200),
    ("Y", 2, 100),
    ("Z", 2, 100)
]
group_names = [g[0] for g in groups]
group_sizes = {g[0]: g[1] for g in groups}
group_targets = {g[0]: g[2] for g in groups}

# 创建问题：最小化总和与目标的偏差
prob = LpProblem("MultiGroupOptimization", LpMinimize)

# 决策变量：x[i][g] = 1 表示第i个变量分配到组g
x = LpVariable.dicts("assign", [(i, g) for i in range(var_count) for g in group_names], cat="Binary")

# 约束1：每个变量只能分配到一个组
for i in range(var_count):
    prob += lpSum([x[(i, g)] for g in group_names]) == 1, f"AssignVar_{i}"

# 约束2：每组的变量数量符合要求
for g in group_names:
    prob += lpSum([x[(i, g)] for i in range(var_count)]) == group_sizes[g], f"GroupSize_{g}"

# 计算每组的实际总和
group_sums = {}
for g in group_names:
    group_sums[g] = lpSum([data[i] * x[(i, g)] for i in range(var_count)])

# 目标函数：最小化所有组的绝对偏差之和
# 引入辅助变量处理绝对值（线性规划不直接支持绝对值）
deviations = LpVariable.dicts("deviation", group_names, lowBound=0)
for g in group_names:
    prob += group_sums[g] - group_targets[g] <= deviations[g], f"DeviationUpper_{g}"
    prob += group_targets[g] - group_sums[g] <= deviations[g], f"DeviationLower_{g}"

prob += lpSum([deviations[g] for g in group_names]), "TotalDeviation"

# 求解
prob.solve(PULP_CBC_CMD(msg=0))

# 输出结果
print(f"求解状态: {LpStatus[prob.status]}")
print(f"总偏差值: {value(prob.objective)}")
print("\n分组结果:")
for g in group_names:
    assigned_vars = [keys[i] for i in range(var_count) if value(x[(i, g)]) == 1]
    assigned_values = [data[i] for i in range(var_count) if value(x[(i, g)]) == 1]
    actual_sum = sum(assigned_values)
    print(f"组{g}:")
    print(f"  变量: {', '.join(assigned_vars)}")
    print(f"  数量: {len(assigned_vars)}")
    print(f"  实际总和: {actual_sum}, 目标总和: {group_targets[g]}, 偏差: {abs(actual_sum - group_targets[g])}")

代码说明

• 用二维决策变量精准跟踪每个变量的分组归属
• 通过辅助变量将绝对值偏差转化为线性约束，适配PuLP的线性规划求解能力
• 同时满足变量唯一分配和组大小要求，确保所有变量被充分利用
• 以总偏差最小化为目标，实现多组同时向各自目标值靠拢的优化效果

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