如何找到最佳的学生分班方案？

Question

如何找到最佳的学生分班方案？

algorithmdynamic-programmingcombinatoricsmathematical-optimizationlinear-programming

8

需要将来自A级别的23名学生，B级别的24名学生和C级别的30名学生分配到三个班级中。

这些班级需要几乎完全相同的大小。

不同级别的学生可以混合在一个班级中，但最好避免。无论如何，在一个班级中应该有来自某个级别的0个学生或超过6个学生。

你能帮我解决这个组合优化问题吗？以下是一个示例输入和输出。如果您可以向我展示如何解决一般性问题，则会获得额外积分！

输入：

pupils = { "A" : 23, "B" : 24, "C": 30 }

示例输出（不太好！）

Class #1 : {'A': 9,  'B': 6, 'C': 10},
Class #2 : {'A': 10, 'B': 9, 'C': 7},
Class #3 : {'A': 11, 'B': 9, 'C': 6}

编辑：这里是我非常粗略、完全没有文档记录、半蛮力破解的代码。它很丑，但能用！我想学习如何编写更优雅的解决方案。

- static_rtti

你说这个示例输出“不太好”。它有什么问题？为什么其他的25-26-26分割会更好呢？ - James Waldby - jwpat7

@jwpat7：正如描述中所解释的那样，这并不是很好，因为所有三个班级都有三个级别，这对老师来说更加困难，最好避免。尽管如此，班级应该具有相同规模的限制比这个更强。 - static_rtti

你现在是如何解决它的？比如，你是否使用了优化求解器？如果是这样，你的约束条件和目标是什么？ - user327301

@raoulcousins：由于不知道更好的方法，我开始编写了一个半暴力算法（我尽可能快地消除错误的选项）。这可能会有效，但我想知道是否有更好或更优雅的选项。 - static_rtti

@raoulcousins：谢谢！我大多数时候使用Python，但在Linux上可用的任何东西都可以。0相当明显，因为你不能有负的学生。6是任意的，它只是意味着你不想在一个班级里有太少水平的学生，因为你会浪费很多时间在他们身上而没有好的理由。但它应该是一个参数，而不是固定的。 - static_rtti

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user327301 · Accepted Answer

这里的根本问题在于你似乎有一个多目标优化问题。你有三个你感兴趣的事情，你可以将它们视为目标或“软约束条件”:

让班级人数相似
最小化每个班级的级别数
如果班级中有任何学生，则需要有足够的来自该级别的学生。

请注意，我已经在AMPL中编写了优化模型。由于你正在使用Python，像PuLP和pyomo这样的Python类似的优化建模语言也可以使用。该模型不应太难翻译。

这是一个整数规划模型和数据文件，突出了第1个目标，同时保持问题（整数）线性。通过这个目标，优化问题找到了与你在示例中给出的相同的解决方案。希望你可以在此基础上添加其他限制和/或目标项，并获得更好的解决方案。

目标是最小化最大班级人数。感兴趣的变量是y[i,j]。对于i在LEVEL，j在CLASS，y[i,j]是分配到班级j的来自级别i的学生数量。它假设你有输入每个班级中来自每个级别的最小学生人数（如果有）。

目标函数可能不是你想要的，但它是尝试平衡班级大小的一种线性方式。我也不能保证这是解决问题最有效的方法。可能有更好的定制算法适用于此问题，但我只需要表达约束和目标，而不编写算法。对于你的使用来说，它可能已经足够好了。

在neos-server.org上使用Gurobi求解器（你可以使用lpsolve或另一个开源优化求解器），我得到了解决方案

模型:

set LEVEL ordered;
set CLASS;

param maxClassSize {CLASS};
param minLevelNumberInClass {LEVEL, CLASS};
param numInLevel {LEVEL};

var z >= 0;
var y{LEVEL, CLASS} integer, >= 0;
var x{LEVEL, CLASS} binary;

#minimize maximum class size
minimize obj: 
  z;

subject to allStudentsAssigned {i in LEVEL}:
  sum {j in CLASS} y[i,j] = numInLevel[i];

#z is the largest of all classes sizes
subject to minMaxZ {j in CLASS}:
  z >= sum {i in LEVEL} y[i,j];

subject to maxClassSizeCon {j in CLASS}:
  sum {i in LEVEL} y[i,j] <= maxClassSize[j];

#xij = 1 if any students from level i are in class j
subject to defineX {i in LEVEL, j in CLASS}:
  y[i,j] <= min(numInLevel[i], maxClassSize[j]) * x[i,j];

#if any students from level i are assigned to class j, then there is a minimum
#if x[i,j] = 1,  y[i,j] >= minLevelNumberInClass[i,j]
subject to minLevel {i in LEVEL, j in CLASS}:
  minLevelNumberInClass[i,j] * x[i,j] <= y[i,j];

您例子中所需的数据文件：

set LEVEL := 1 2 3;
set CLASS := 1 2 3;

param minLevelNumberInClass:  
  1 2 3 :=
1 6 6 6
2 6 6 6
3 6 6 6
;

param maxClassSize :=
1 77
2 77
3 77
;

param numInLevel :=
1 23
2 24
3 30
;