使用 Microsoft Solver Foundation 3.0 进行团队建设优化

Question

我正在开发一个学生项目团队建设应用程序。我熟悉优化，但之前没有使用过 Microsoft Solver Foundation。我已经解决了约束条件，但无法使用求解器语法确定我的目标。以下是该应用程序的基本摘要：

教授们会为每个项目衡量某些技能。学生列出哪些 技能是他们的优势和劣势，他们对项目进行排名 想做。一个项目必须分配 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 是解决这个问题的最佳方法吗？看起来 Solution Foundation 有很多不同的求解器/工具。我有 Solution Foundation 的 Express 版本，但如果需要，也可以获取学术企业版本。

谢谢， - Greg

*最终应用程序需要解决大约 100 名学生、20-30 个项目和约 30 项潜在技能（每个项目约 5 项）的模型。

Answer 1

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

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

而不是编写技能约束为：

每个项目 p、每个技能 k 的所有学生的总和 (X_sp) >= NumMin_pk。

您

为所有学生编写 sum (X_sp) > 0 + NumMin_pk * Dummy1_pk 对于每个 p，对于每个技能 k

并且在目标函数中，您惩罚 Dummy_pk（通过为其最大化问题赋予负成本。）因此，Simplex 将仅当没有其他选择时才分配非零 Dummy_pk。

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

所有学生的总和 (X_sp) > 0 + 3* Dummy_pk + 2 * Dummy_pk2 对于每个 p，对于每个技能 k

在目标函数中，给 Dummy_pk 一个高的负成本，给 Dummy2_pk 一个较小但负的成本。模型将首先尝试使 get Dummy1_pk 0，如果可能的话，将驱动Dummy2_pk 0。结果将是 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 编写两个约束，并避免弱点抵消其他学生技能的问题。