2

私は学生プロジェクト チーム ビルディング アプリケーションに取り組んでいます。最適化には精通していますが、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>");

プロジェクトのスキル要件ごとに行を追加し、そのスキルに対する各学生の強み/弱みの係数を設定し、そのプロジェクトのスキルの重みの下限を設定する方法を確認しました。ただし、これにより2つの問題が発生します。

  1. プロジェクトのスキル要件がすべて満たされるとは思えません。そのため、スキルの最小値を制約として設定するのではなく、意味するスキル要件の数を最大化するという目標を設定したいと考えています。チームが特定のスキルで 1 ポイント不足していたとしても、すべてのチームがそのスキルを弱点として挙げているよりはましです。
  2. プログラミングスキルの重みが 3のチームに 4 人の学生がいて、そのうち 3 人がプログラミングを強み (+1) としてリストし、もう 1 人の学生がプログラミングを弱点 (-1) としてリストしている場合、私のモデルは正しくありません。(1+1+1-1)<3 であるため、プログラミング要件が満たされていないことを示します。

誰にもアイデアはありますか？SimplexSolver はこの問題を解決する最善の方法ですか? Solution Foundation には、さまざまなソルバー/ツールが多数あるようです。私は Solution Foundation の Express バージョンを持っていますが、必要に応じて Academic Enterprise バージョンを手に入れることができるでしょう。

ありがとう - グレッグ

*最終的なアプリケーションでは、約 100 人の学生、20 ～ 30 のプロジェクト、および最大 30 の潜在的なスキル (プロジェクトごとに最大 5) のモデルを解決する必要があります。

4

1 に答える 1

1

はい、シンプレックスを使用してこれを解決できます。これは標準的な「割り当て問題」であり、好みやスキルの重みに関していくつかのバリエーションがあります。

「たるみ」を取るために1つ以上の「ダミー変数」を導入することにより、質問の問題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にペナルティを課します (最大化問題の負のコストを与えることによって)。したがって、シンプレックスは、他に代替手段がない場合にのみ、ゼロ以外の Dummy_pk を割り当てます。

さらに、1 つのスキル (プログラミング) の場合、プロジェクトの最小スキル ウェイトは 3 ですが、5 人の学生がプログラミングを持っている場合は、さらに優れています。これは、2 つ目のダミー変数 (Dummy2_pk) を導入することで実現できます。

Sum for all students (X_sp) > 0 + 3* Dummy_pk + 2 * Dummy_pk2各 p、各スキル k

目的関数で、Dummy_pk に高い負のコストを与え、Dummy2_pk に小さいが負のコストを与えます。モデルは最初に Dummy1_pk を 0 にしようとし、可能であれば Dummy2_pk を 0 にします。その結果、プログラミング スキルを持つ 5 人の学生がそのプロジェクトに割り当てられます。

問題 2 (負のスキルの重み) に対処するには: 1 と -1 を分離して、スキル ベクトルを 2 つのベクトルに分割します。

したがって、[1,0,0,1,-1,0,1] は [1,0,0,1,0,0,1] と [0,0,0,0,-1,0,0] になります。 . スキルの弱点で何をしたいかによって、プロジェクト p、スキル k ごとに 2 つの制約を記述し、弱点が別の学生のスキルを相殺する問題を回避できます。

于 2012-02-05T14:18:55.037 に答える