在具有有限组选择的 PULP 中实现 MILP

Question

我正在尝试在 PULP 中实现以下问题：

https://math.stackexchange.com/questions/4232797/optimising-class-assignment-based-on-test-score-and-class-choice/4233234#4233234

这是我到目前为止的尝试。我不确定如何将字典“student_allocations”构建到我的限制中以阻止学生被分配到他们没有选择的组。感谢任何帮助。

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

# student ID number
student_id = np.arange(1,31)

# Test Scores
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]

# Test scores mapped to student ID to make parameter s_i
s_i= dict(zip(student_id, scores))

# Groups
GROUPS = ['A','B','C','D','E','F'] 

# Student ID mapped to Group choices
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']}


# setting the problem variable
prob = LpProblem("Timetabling", LpMinimize)

# define decision variable
x_ic = LpVariable.dicts("InClass", [(i,c) for i in student_id
                                          for c in GROUPS],
                       0,1,LpBinary)             

# define dummy min, max variables
l_c = LpVariable.dicts("lowest group score",GROUPS,0)      
h_c = LpVariable.dicts("highest group score",GROUPS,0)    

# define the objective function 
prob += lpSum(h_c[c] - l_c[c] for c in GROUPS) 

# setting the constraints
# constraint 1      
for i in student_id:
    prob += lpSum(x_ic[(i,c)] for c in GROUPS) == 1 
       
# constraint 2
N = 10  # maximum class size
for c in GROUPS:
    prob += lpSum(x_ic[(i,c)] for i in student_id) <= N
    
# constraint 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)])   

# constraint 4
for i in student_id:
    for c in GROUPS:
        prob += h_c[c] >= s_i[i] * x_ic[(i,c)]

# solve the problem
prob.solve()
print("Status: ", LpStatus[prob.status])

# output allocations
TOL = 0.000001 
for i in student_id:
    for c in GROUPS:
        if x_ic[(i,c)].varValue > TOL:
            print(i, c)

编辑：下面给出了完整的解决方案，方法 3 已纳入决策变量、约束和输出。

# setting the problem variable
prob = LpProblem("Timetabling", LpMinimize)

# define decision variable
x_ic = LpVariable.dicts("InClass", [(i,c) for i in student_id
                                          for c in student_allocations[i]
                                          ],
                       0,1,LpBinary)              

# define dummy min, max variables
l_c = LpVariable.dicts("lowest group score",GROUPS,0)      
h_c = LpVariable.dicts("highest group score",GROUPS,0)   


# define the objective function 
prob += lpSum(h_c[c] - l_c[c] for c in GROUPS) 

# setting the constraints
            
# constraint 1      
for i in student_id:
    prob += lpSum(x_ic[(i,c)] for c in GROUPS if c in student_allocations[i]) == 1 
       
# constraint 2
N = 10 # maximum class size
for c in GROUPS:
        prob += lpSum(x_ic[(i,c)] for i in student_id if c in student_allocations[i]) <= N
    
# constraint 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)])   

# constraint 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)]

# solve the problem
prob.solve()
print("Status: ", LpStatus[prob.status])

# output allocations
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(i,c)

Answer 1

有很多方法可以做到这一点，有些很明显，有些则需要更多工作。

方法一：添加约束条件

添加禁止分配给不允许的组的约束：

for i in student_id:
    for c in GROUPS:
        if not (c in student_allocations[i]):
            prob += x_ic[(i,c)] == 0

这很明显，我想你应该已经能够弄明白了。

方法二：添加边界

稍微复杂一点的方法是设置上限。

for i in student_id:
    for c in GROUPS:
        if not (c in student_allocations[i]):
             x_ic[(i,c)].upBound = 0

这样效率更高一些，因为没有生成约束，而是生成了简单的上限。求解器通常会将单一约束转换为边界，但这可以节省一些生成约束的工作。

方法三：稀疏变量

这是最有效的方法。只生成允许的变量。将变量更改为：

# define decision variable
x_ic = LpVariable.dicts("InClass", [(i,c) for i in student_id
                                          for c in GROUPS
                                          if c in student_allocations[i]],
                       0,1,LpBinary)

或更短：

# define decision variable
x_ic = LpVariable.dicts("InClass", [(i,c) for i in student_id
                                          for c in student_allocations[i]],
                       0,1,LpBinary)

你也需要保护相应的约束条件。对于大型模型，这是最好的方法。对于生产模型，我总是使用这种方法。

在具有有限组选择的 PULP 中实现 MILP

Implementing MILP in PULP with restricted choices of group

python

linear-programming

pulp

integer-programming

方法一：添加约束条件

方法二：添加边界

方法三：稀疏变量