在具有有限组选择的 PULP 中实现 MILP
Implementing MILP in PULP with restricted choices of group
我正在尝试在 PULP 中实现以下问题:
这是我到目前为止的尝试。我不确定如何将字典“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)
有很多方法可以做到这一点,有些很明显,有些则需要更多工作。
方法一:添加约束条件
添加禁止分配给不允许的组的约束:
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 中实现以下问题:
这是我到目前为止的尝试。我不确定如何将字典“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)
有很多方法可以做到这一点,有些很明显,有些则需要更多工作。
方法一:添加约束条件
添加禁止分配给不允许的组的约束:
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)
你也需要保护相应的约束条件。对于大型模型,这是最好的方法。对于生产模型,我总是使用这种方法。