2

我正在开发一个学生项目团队建设应用程序。我熟悉优化,但以前没有使用过 Microsoft Solver Foundation。我已经解决了我的限制,但是在使用 Solver 语法识别我的目标时遇到了麻烦。这是应用程序的基本摘要:

教授对每个项目的某些技能进行加权。学生列出哪些技能是他们的优势和劣势,并对他们想做的项目进行排名。一个项目必须有 3-5 名学生分配给它。必须为每个学生分配一个项目。

  • 主要目标是最大化满足的技能要求数量
  • 次要目标是最大化学生的偏好

我一直在玩基于这个混合整数问题教程的SimplexSolver 类,并且能够毫无问题地最大化学生的偏好。

using Microsoft.SolverFoundation.Solvers;

//This example has 2 projects and 6 students
SimplexSolver solver = new SimplexSolver();
//Student A wants to be in project 1, Student B is indifferent to project 1, Student C does not want to be in project 1, etc...
double[] studentprojectpref = new double[] { 1, 0, -1, 0, -1, 0, 0, 1, 0, 1, 0, 1 };
int[] choosestudentprojectPS = new int[12];

//GOAL - maximize student preferences
int sumpreferences;
solver.AddRow("sumpreferences", out sumpreferences);
solver.AddGoal(sumpreferences, 1, false);

//add a varaible (column) for each possible student/project pair
for (int i = 0; i < choosestudentprojectPS.GetUpperBound(0)+1; i++)
{
    solver.AddVariable(projectstudent[i], out choosestudentprojectPS[i]);
    solver.SetBounds(choosestudentprojectPS[i], 0, 1);
    solver.SetIntegrality(choosestudentprojectPS[i], true);
    solver.SetCoefficient(sumpreferences, choosestudentprojectPS[i], studentprojectpref[i]);
}

solver.Solve(new SimplexSolverParams());

Response.Write(solver.MipResult + "<br>");
Response.Write("<br>Project 1<br>");
for (int i = 0; i < 6; i++)
{
    if (solver.GetValue(choosestudentprojectPS[i]) == 1) Response.Write(projectstudent[i] + "<br>");
}
Response.Write("<br>Project 2<br>");
for (int i = 6; i < 12; i++)
{
    if (solver.GetValue(choosestudentprojectPS[i]) == 1) Response.Write(projectstudent[i] + "<br>");
}
    Response.Write("<br>The total sumpreferences is: " + solver.GetValue(sumpreferences) + "<br>");

我了解如何为每个项目技能要求添加行,并为每个学生在该技能上的优势/劣势设置系数,并为该项目的技能权重设置下限。不过,这给了我两个问题。

  1. 我不相信所有项目技能要求都会得到满足。这就是为什么我想设定一个目标,以最大限度地提高技能要求的数量,而不是将技能权重最小值设置为约束。即使一支球队在某项技能上落后 1 分,它仍然比所有将这项技能列为弱点的球队要好。
  2. 如果团队中有 4 名学生的编程技能权重为 3,其中 3 人的编程被列为优势 (+1) 而另一个学生的编程被列为劣势 (-1),那么我的模型将不正确表明没有满足编程要求,因为 (1+1+1-1)<3。

有人有什么想法吗?SimplexSolver 是解决此问题的最佳方法吗?看起来解决方案基金会有很多不同的求解器/工具。我有解决方案基础的 Express 版本,但如果需要,可能会获得 Academic Enterprise 版本。

谢谢, - 格雷格

*最终申请将需要解决具有大约 100 名学生、20-30 个项目和约 30 个潜在技能(每个项目约 5 个)的模型。

4

1 回答 1

1

是的,您可以使用 Simplex 解决此问题。这是一个标准的“分配问题”,在偏好和技能权重方面有一些变化。

您可以通过引入一个或多个“虚拟变量”来解决问题中的问题 1以弥补“松弛”

而不是将技能约束写为:

Sum for all students (X_sp) >= NumMin_pk对于每个项目 p,对于每个技能 k。

你写

sum for all students (X_sp) > 0 + NumMin_pk * Dummy1_pk对于每个 p,对于每个技能 k

在目标函数中,你惩罚Dummy_pk (通过给它一个最大化问题的负成本。)所以,只有当它没有其他选择时,Simplex 才会分配一个非零的 Dummy_pk。

此外,假设对于一项技能(编程),该项目的最小技能权重为 3,但如果有 5 名学生有编程,那就更好了。您可以通过引入第二个虚拟变量 (Dummy2_pk) 来实现这一点。

Sum for all students (X_sp) > 0 + 3* Dummy_pk + 2 * Dummy_pk2对于每个 p,对于每个技能 k

在目标函数中,给 Dummy_pk 一个 High 的负成本,给 Dummy2_pk 一个较小但负的成本。模型将首先尝试使 Dummy1_pk 为 0,如果可能的话,将驱动 Dummy2_pk 为零。结果将是 5 名具有编程技能的学生被分配到该项目。

解决问题 2(负技能权重): 通过分隔 1 和 -1 将技能向量分成两个向量。

所以 [1,0,0,1,-1,0,1] 变成 [1,0,0,1,0,0,1] 和 [0,0,0,0,-1,0,0] . 根据您想对技能弱点做什么,您可以为每个项目 p、技能 k 编写两个约束,并避免弱点抵消另一个学生的技能的问题。

于 2012-02-05T14:18:55.037 回答