在PULP中实现带组别选择约束的MILP（混合整数线性规划）

我正在PULP中实现基于考试分数和学生志愿的班级分配优化问题，现有代码无法将student_allocations字典融入约束，避免学生被分配到未选择的组别，初始实现代码如下：

import pandas as pd
import numpy as np
from pulp import * 

# 学生ID
student_id = np.arange(1,31)

# 考试分数
scores = [15, 29, 18, 74, 66, 89, 3, 77, 78, 70, 68, 47, 71, 37, 96, 27, 76, 25, 95, 16, 32, 11, 81, 82, 21, 57, 8, 5, 55, 31]

# 学生ID映射分数，生成参数s_i
s_i= dict(zip(student_id, scores))

# 可选组别
GROUPS = ['A','B','C','D','E','F'] 

# 学生ID映射可选志愿组别
student_allocations = {1: ['F', 'D'], 2: ['F', 'E', 'D', 'A', 'B', 'C'], 3: ['E', 'D'], 4: ['D', 'E', 'C', 'B', 'A'], 5: ['F', 'C', 'D'], 6: ['E', 'D', 'C', 'A'], 7: ['A'], 8: ['C', 'A', 'D', 'E', 'F'], 9: ['F', 'B'], 10: ['D', 'E'], 11: ['A', 'E', 'C', 'B', 'D'], 12: ['D', 'E', 'A', 'F'], 13: ['E'], 14: ['C', 'F', 'D'], 15: ['E', 'A', 'F', 'C', 'D'], 16: ['C', 'D', 'F', 'A', 'E'], 17: ['E', 'F'], 18: ['B'], 19: ['C', 'E', 'B', 'D'], 20: ['F', 'E'], 21: ['E', 'A', 'B', 'D', 'F', 'C'], 22: ['D', 'B', 'F', 'E', 'C', 'A'], 23: ['D', 'A', 'F', 'B', 'C'], 24: ['E', 'F', 'B', 'D', 'A'], 25: ['C'], 26: ['F', 'E', 'B'], 27: ['A', 'D', 'B'], 28: ['E', 'B', 'C', 'D'], 29: ['A', 'B', 'F', 'C', 'E', 'D'], 30: ['A', 'F', 'B', 'D']}


# 初始化问题
prob = LpProblem("Timetabling", LpMinimize)

# 定义决策变量
x_ic = LpVariable.dicts("InClass", [(i,c) for i in student_id
                                          for c in GROUPS],
                       0,1,LpBinary)             

# 定义辅助变量：组内最低分、最高分
l_c = LpVariable.dicts("lowest group score",GROUPS,0)      
h_c = LpVariable.dicts("highest group score",GROUPS,0)    

# 定义目标函数：最小化所有组的分差总和
prob += lpSum(h_c[c] - l_c[c] for c in GROUPS) 

# 定义约束
# 约束1：每个学生必须分到一个组
for i in student_id:
    prob += lpSum(x_ic[(i,c)] for c in GROUPS) == 1 
       
# 约束2：每个组人数不超过上限
N = 10  # 最大班级容量
for c in GROUPS:
    prob += lpSum(x_ic[(i,c)] for i in student_id) <= N
    
# 约束3：组内最低分不超过组内所有学生的分数
for i in student_id:
    for c in GROUPS:
        prob += (l_c[c] - s_i[i]) <= (1-s_i[i]) * (1-x_ic[(i,c)])   

# 约束4：组内最高分不低于组内所有学生的分数
for i in student_id:
    for c in GROUPS:
        prob += h_c[c] >= s_i[i] * x_ic[(i,c)]

# 求解问题
prob.solve()
print("求解状态: ", LpStatus[prob.status])

# 输出分配结果
TOL = 0.000001 
for i in student_id:
    for c in GROUPS:
        if x_ic[(i,c)].varValue > TOL:
            print(f"学生{i} 分配到组别{c}")

修正后完整实现方案 #

通过限定决策变量生成范围、约束遍历范围两个维度实现志愿校验，确保学生仅会被分配到自己选择的组别中，完整代码如下：

# 初始化问题
prob = LpProblem("Timetabling", LpMinimize)

# 定义决策变量：仅生成学生可选志愿对应的变量
x_ic = LpVariable.dicts("InClass", [(i,c) for i in student_id
                                          for c in student_allocations[i]
                                          ],
                       0,1,LpBinary)              

# 定义辅助变量：组内最低分、最高分
l_c = LpVariable.dicts("lowest group score",GROUPS,0)      
h_c = LpVariable.dicts("highest group score",GROUPS,0)   


# 定义目标函数：最小化所有组的分差总和
prob += lpSum(h_c[c] - l_c[c] for c in GROUPS) 

# 定义约束
            
# 约束1：每个学生必须分到自己志愿内的一个组
for i in student_id:
    prob += lpSum(x_ic[(i,c)] for c in GROUPS if c in student_allocations[i]) == 1 
       
# 约束2：每个组人数不超过上限
N = 10 # 最大班级容量
for c in GROUPS:
        prob += lpSum(x_ic[(i,c)] for i in student_id if c in student_allocations[i]) <= N
    
# 约束3：组内最低分不超过组内所有学生的分数
for i in student_id:
    for c in GROUPS:
        if c in student_allocations[i]:
            prob += (l_c[c] - s_i[i]) <= (1-s_i[i]) * (1-x_ic[(i,c)])   

# 约束4：组内最高分不低于组内所有学生的分数
for i in student_id:
    for c in GROUPS:
        if c in student_allocations[i]:
            prob += h_c[c] >= s_i[i] * x_ic[(i,c)]

# 求解问题
prob.solve()
print("求解状态: ", LpStatus[prob.status])

# 输出分配结果
TOL = 0.000001 
for i in student_id:
    for c in GROUPS:
        if c in student_allocations[i]:
            if x_ic[(i,c)].varValue > TOL:
                print(f"学生{i} 分配到组别{c}")

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