Оптимизация тимбилдинга с использованием Microsoft Solver Foundation 3.0 - PullRequest
Новая
       30

Оптимизация тимбилдинга с использованием Microsoft Solver Foundation 3.0

2 голосов
/ 08 октября 2011

Я работаю над приложением для создания команды студенческого проекта.Я знаком с оптимизацией, но раньше не пользовался Microsoft Solver Foundation.У меня проработаны ограничения, но я не могу определить свои цели с помощью синтаксиса Солвера.Вот основные сведения о приложении:

Профессора оценивают определенные навыки для каждого проекта.Студенты перечисляют, какие навыки являются их сильными и слабыми сторонами, и они оценивают проекты, которые они хотели бы сделать.В проекте должно быть от 3 до 5 студентов.Каждому студенту должен быть назначен проект.

  • Основная цель - максимизировать количество удовлетворенных требований к навыкам
  • Вторичная цель - максимизировать предпочтения студента

Я играю с SimplexSolver Class на основе этого учебного пособия по смешанным целым числам и могу без проблем максимизировать предпочтения учеников. 

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. </li>

У кого-нибудь есть какие-нибудь идеи?SimplexSolver - лучший способ решить эту проблему?Похоже, что Solution Foundation имеет много различных решателей / инструментов.У меня есть Express Solution Solution Foundation, но, возможно, я смогу получить версию Academic Enterprise, если нужно.

Спасибо, - Грег

* В окончательном приложении нужно будет решить модели с примерно 100 студентами20-30 проектов и ~ 30 потенциальных навыков (~ 5 на проект).

1 Ответ

1 голос
/ 05 февраля 2012

Да, вы можете решить эту проблему с помощью Simplex.Это стандартная «Проблема назначения» с несколькими вариациями в плане предпочтений и веса навыка.

Вы можете обратиться к Проблема 1 в своем вопросе, введя один или несколько "манекенов.переменные " для принятия 'slack'

Вместо записи ограничения навыка в виде:

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 учеников есть программирование, это даже лучше.Вы можете достичь этого, введя вторую переменную Dummy (Dummy2_pk).

Sum for all students (X_sp) > 0 + 3* Dummy_pk + 2 * Dummy_pk2 для каждого p, для каждого навыка k

В целевой функции придайте Dummy_pk высокую отрицательную стоимость именьшая, но отрицательная стоимость для Dummy2_pk. Сначала модель попытается получить 0 Dummy1_pk, и, если возможно, если Dummy2_pk будет равняться нулю.Результатом будет 5 студентов с навыками программирования, которые будут назначены на этот проект.

Для решения проблемы 2 (отрицательные веса навыков): Разделите вектор навыков на два вектора, разделив 1 и-1's.

Так [1,0,0,1, -1,0,1] становится [1,0,0,1,0,0,1] и [0,0,0,0, -1,0,0].В зависимости от того, что вы хотите сделать со слабостью навыка, вы можете написать ДВА ограничения для каждого проекта p, навыка k и избежать проблемы слабости, отменившей навык другого ученика.

...