<p>我想你已经接近了。这是一个相当标准的整数线性规划(ILP)分配问题。这会有点慢,因为问题的结构</p>
<p>你没有在你的帖子中说设置的故障是什么&;解决时间很短。我看到你在读一个文件并使用熊猫。我认为熊猫在优化问题上会很快变得笨重,但这只是个人喜好</p>
<p>我使用<code>cbc</code>解算器在<code>pyomo</code>中对您的问题进行了编码,我很确定这与<code>pulp</code>用于比较的解算器相同。(见下文)。我认为你有两个约束和一个双索引二进制决策变量</p>
<p>如果我把它减少到10万名学生(没有松弛…只是一对一配对),它会在14秒内解决,以便进行比较。我的设置是一个5年的iMac,带有大量ram</p>
<p>与池中的10万名学生一起运行,在调用解算器之前,它将在大约25分钟内以10秒的“设置”时间解算。所以我不确定为什么你的编码要花2小时。如果你能分解你的求解时间,那会有帮助。其余的应该是微不足道的。我没有在输出中做太多的改动,但OBJ函数值980K似乎是合理的</p>
<h3>其他想法:</h3>
<p>如果您可以正确配置解算器选项,并将mip间距设置为0.05左右,那么如果您可以接受稍微非最佳的解决方案,应该可以加快速度。我只在像古罗比这样的付费解算器的解算器选项上有过不错的运气。我没有太多的运气与使用免费解决方案,YMMV</p>
<pre><code>import pyomo.environ as pyo
from random import randint
from time import time
# start setup clock
tic = time()
# exam types
subjects = ['Math', 'English', 'Computers', 'History', 'Physics']
# make set of students...
num_students = 100_000
students = [f'student_{s}' for s in range(num_students)]
# make 100K fake scores in "flat" format
student_scores = { (student, subj) : randint(0,100)
for student in students
for subj in subjects}
assignments = { 'Math': 4000, 'English': 3000, 'Computers': 2000, 'History': 750, 'Physics': 250}
weights = {'Math': 1.9, 'English': 1.7, 'Computers': 1.5, 'History': 1.3, 'Physics': 1.1}
# Set up model
m = pyo.ConcreteModel('exam assignments')
# Sets
m.subjects = pyo.Set(initialize=subjects)
m.students = pyo.Set(initialize=students)
# Parameters
m.assignments = pyo.Param(m.subjects, initialize=assignments)
m.weights = pyo.Param(m.subjects, initialize=weights)
m.scores = pyo.Param(m.students, m.subjects, initialize=student_scores)
# Variables
m.x = pyo.Var(m.students, m.subjects, within=pyo.Binary) # binary selection of pairing student to test
# Objective
m.OBJ = pyo.Objective(expr=sum(m.scores[student, subject] * m.x[student, subject]
for student in m.students
for subject in m.subjects), sense=pyo.maximize)
### Constraints ###
# fill all assignments
def fill_assignments(m, subject):
return sum(m.x[student, subject] for student in m.students) == assignments[subject]
m.C1 = pyo.Constraint(m.subjects, rule=fill_assignments)
# use each student at most 1 time
def limit_student(m, student):
return sum(m.x[student, subject] for subject in m.subjects) <= 1
m.C2 = pyo.Constraint(m.students, rule=limit_student)
toc = time()
print (f'setup time: {toc-tic:0.3f}')
tic = toc
# solve it..
solver = pyo.SolverFactory('cbc')
solution = solver.solve(m)
print(solution)
toc = time()
print (f'solve time: {toc-tic:0.3f}')
</code></pre>
<h2>输出</h2>
<pre><code>setup time: 10.835
Problem:
- Name: unknown
Lower bound: -989790.0
Upper bound: -989790.0
Number of objectives: 1
Number of constraints: 100005
Number of variables: 500000
Number of binary variables: 500000
Number of integer variables: 500000
Number of nonzeros: 495094
Sense: maximize
Solver:
- Status: ok
User time: -1.0
System time: 1521.55
Wallclock time: 1533.36
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics:
Branch and bound:
Number of bounded subproblems: 0
Number of created subproblems: 0
Black box:
Number of iterations: 0
Error rc: 0
Time: 1533.8383190631866
Solution:
- number of solutions: 0
number of solutions displayed: 0
solve time: 1550.528
</code></pre>