Teilenehmer in Projekte einteilen - Algorithmus
Hi @ All.
Nachdem ich lange nicht mehr im Forum aktiv war, habe ich mal wieder eine Frage an die Community.
Folgende Problemstellung:
Ich habe eine Liste von Kursen mit Bedingungen (Maximale / Minimale Anzahl an Teilnehmern) und eine Liste von Teilnehmern, die jeweils eine Erstwahl, Zweitwahl und eine Drittwahl angeben können.
Jetzt möchte ich jeden der Teilnehmer in genau einen Kurs einteilen, bestenfalls natürlich in seine Erstwahl. Ebenso sollen bestenfalls alle Kurse stattfinden (d.h. jeder Kurs soll mindestens seine Minimale Anzahl an Teilnehmern haben).
Meine Vorgehensweise bisher:
Ich weise zunächst jedem Teilnehmer seine Erstwahl zu und schaue dann, was ich ändern muss. Hierbei suche ich mir Kurse, die mit der Erstwahl überbelegt sind und werfe (zufällig) Personen raus, bis der Kurs eine gültige Teilnehmerzahl hat. Die rausgeworfenen Personen bekommen nun ihre Zweitwahl zugeteilt und der Spaß beginnt von vorne. Problem hierbei: Die Zweitwahl kann wieder dafür sorgen, dass (andere) Kurse zu voll sind. Dafür gibt es zum Glück die Drittwahl. Was mache ich aber, wenn die Kursbelegung auch nach der Drittwahl immer noch nicht stimmt?
Meine Frage: Gibt es für solche Probleme schon bestehende Schemata / Algorithmen (bestimmt), wenn ja, nach was muss ich suchen?
Wenn nein, kann mir jemand einen Tipp geben, wie ich das besser handhaben kann?
Mit freundlichen Grüßen,
Christian.
Hi TheBrainiac,
ja, du hast Recht, das Problem ist schonmal gelöst worden. Jede Software zum Erstellen von Dienst-, Fahr-, Einsatz-, Flug- oder Stundenplänen verfügt über eine solche Funktion. Evtl. kann man also überlegen, eine fertige Software dafür zu verwenden.
Wenn du es selbst programmieren willst oder mußt, dann solltest du dir mal Optimierungs-Verfahren anschauen, und entsprechende Bibliotheken wie AForge.NET. Evtl. kommt für deinen Anwendungsfall ein Genetischer Algorithmus in Frage.
Christian
Weeks of programming can save you hours of planning
Kannst Dir ja mal die Beispiele unter: http://www.optaplanner.org/ reinziehen. Das ist eine Open Source Optimierungssoftware. Trifft sehr genau das was Du machen möchtest, ist aber leider in Java. Könntest Du also entweder als Kommandozeilentool oder mit IKVM verwenden.
Hallo Braniac,
der Zweig der Mathmatik/Informatik diesbezüglich heißt "Kombinatorische Optimierung".
Dafür modelliert man sein Problem oftmals mittels Ganzzahlig Linearer Programmierung (Integer Linear Programming).
Im Grunde stellst du dein Problem einfach durch ein paar Ungleichungen dar und eine Zielfunktion - alles linear.
Vorteil ist, dass es zum Lösen dieser Probleme schon extrem weit entwickelte Verfahren gibt!
Wie jaensen erwähnt hat, ist ein bekannter Solver der optaplanner. Andere sind IBM's ILOG CPLEX, Gurobi's Optimizer oder Open source Varianten wie das GNU Linear Programming Kit, lp_solve, coin-or CBC, Google's or-tools, ...
Die kommerziellen Tools kosten zumeist einige Tausend Euros, sind dafür aber noch flotter, Aber dir reicht sicherlich eine freie Variante. Es gibt auch noch die Microsoft Solver Foundation, habe aber gelesen, dass es wohl nicht mehr weiterentwickelt wird. Aber auch lp_solve hat C#-Wrapper und Google's or-tools bringen auch C# Schnittstellen zu GLPK und CBC mit.
Kommen wir nun mal zum Inhaltlichen, anhand eines Beispiels mit 4 Kursen, 20 Leuten, Erst- und Zweitwünschen.
Wir definieren hierfür 80 (20*4) binäre Variablen bA,Xdie jeweils mit 0/1 dafür stehen, ob nun Person A dem Kurs X zugewiesen wurde.
Wenn also "Klaus" dem Kurs "Optimierung" zugewiesen würde, wäre
[TT]b[SUB][Klaus],[Optimierung][/SUB]=1
b[SUB][Klaus],[Grundlagen] [/SUB]=0
b[SUB][Klaus],[Algorithmen][/SUB]=0
...[/TT]
Aber zurück zur Problem-Modellierung. Alle Randbedingungen müssen wir nun als lineare (Un-)Gleichungen beschreiben.
1.Jede Person wird genau einem Kurs (Optimierung, Grundlagen, Algorithmen, C#) zugewiesen:
[TT]b[SUB][Klaus],[Optimierung][/SUB] + b[SUB][Klaus],[Grundlagen][/SUB] + b[SUB][Klaus],[Algorithmen][/SUB] + b[SUB][Klaus],[C#][/SUB] = 1
b[SUB][Alice],[Optimierung][/SUB] + b[SUB][Alice],[Grundlagen][/SUB] + b[SUB][Alice],[Algorithmen][/SUB] + b[SUB][Alice],[C#][/SUB] = 1
...[/TT]
1.Die Kurse haben Kapazitäten (mindestens 3, maximal 9)
[TT]b[SUB][Klaus],[Optimierung][/SUB] + b[SUB][Alice],[Optimierung][/SUB] + b[SUB][Bernd],[Optimierung][/SUB] + ... > 2
b[SUB][Klaus],[Optimierung][/SUB] + b[SUB][Alice],[Optimierung][/SUB] + b[SUB][Bernd],[Optimierung][/SUB] + ... < 10
b[SUB][Klaus],[Grundlagen][/SUB] + b[SUB][Alice],[Grundlagen][/SUB] + b[SUB][Bernd],[Grundlagen][/SUB] + ... > 2
b[SUB][Klaus],[Grundlagen][/SUB] + b[SUB][Alice],[Grundlagen][/SUB] + b[SUB][Bernd],[Grundlagen][/SUB] + ... < 10
...[/TT]
Und als Zielfunktion definieren wir eine lineare Größe, die es zu minimieren gilt. Und zwar so, dass es umso kleiner wird, je öfter der Erstwunsch oder Zweitwunsch zugewiesen wird. Wir vergeben also "Strafpunkte". Für einen erfüllten Erstwunsch gibt es einen Strafpunkt, für einen erfüllten Zweitwunsch gibt es 10 Strafpunkte und wenn etwas anderes zugewiesen werden muss, gibt es 100 Strafpunkte.
Im Beispiel hat Klaus als Erst- und Zweitwunsch (Optimierung, Grundlagen), Alice hat (C#, Optimierung), Bernd hat (Algorithmen, Grundlagen).
Das ergibt nun folgende Zielfunktion, die alle 80 Variablen umfasst:
[TT]
Minimize:
001 * b[SUB][Klaus],[Optimierung][/SUB] + 010 * b[SUB][Klaus],[Grundlagen][/SUB] + 100 * b[SUB][Klaus],[Algorithmen][/SUB] + 100 * b[SUB][Klaus],[C#][/SUB] +
010 * b[SUB][Alice],[Optimierung][/SUB] + 100 * b[SUB][Alice],[Grundlagen][/SUB] + 100 * b[SUB][Alice],[Algorithmen][/SUB] + 001 * b[SUB][Alice],[C#][/SUB] +
100 * b[SUB][Bernd],[Optimierung][/SUB] + 010 * b[SUB][Bernd],[Grundlagen][/SUB] + 001 * b[SUB][Bernd],[Algorithmen][/SUB] + 100 * b[SUB][Bernd],[C#][/SUB] +
...[/TT]
Insgesamt hast du also 80 Variablen, eine Zielfunktion und 28 (Un-)Gleichungen. Das steckst du in einen Solver und heraus kommt eine Belegung deiner Variablen, bei der das Ziel möglichst minimal ist.
Natürlich kannst du noch weitere Bedingungen einbauen, die Strafpunkte anders bemessen, Dritt- und Viertwünschen einführen, etc... Das Modell ist wunderbar erweiterbar.
Das Prinzip konnte ich aber hoffentlich rüberbringen.
Das schöne an ILP (Integer Linear Programming), wenn man einmal das Grundlegende Konzept verstanden hat, kann man irrsinnig viele Optimierungs-Probleme mit geringem Aufwand so darstellen und vor allem Lösen lassen!
Als Schnittstelle zu den Solvern bietet sich an:*Das Problem als Datei generieren in einem der Formate LP, AMPL, ... und den Solver als Unterprozess starten. *Das Problem über einen Wrapper direkt an den Solver als Komponente übergeben.
Vielleicht sieht das jetzt kompliziert aus, aber glaub mir, es ist eigentlich total einfach 😃
beste Grüße
zommi
Hey,
ich habe mal ein echtes, funktionsfähiges Beispiel formuliert.
Ich habe 25 Studenten, 5 Kurse und Erst- sowie Zweitwünsche mit Strafpunkten (1, 10, 100).
Die Datei course.lp beschreibt das Problem nach oben erklärter Weise im LP-Format.
Hat man nun beispielsweise GLPK installiert, kann man wie folgt das Problem lösen lassen:
[pre]glpsol --lp course.lp -o course.sol[/pre]
Heraus kommt dann die course.sol, in der man die Belegung der Variablen, also die Zuweisung der Studenten zu den Kursen, ablesen kann. Beispielsweise sieht man, dass es keine Lösung gibt, die alle Studenten zufrieden stellt, zwei bekommen nur ihren Zweitwunsch.
Um zu zeigen, dass man auch programmatisch mit den Solvern sprechen kann, habe ich noch ein Programm geschreiben, was selbes Problem löst. Da ich das noch nie mit C# versucht habe, anbei nur ein Python-Programm, welches das PuLP-Framework als Frontend zu den Solvern nutzt: course.py.
Bestenfalls sollte sich etwas Vergleichbares mit C# genauso umsetzen lassen.
beste Grüße
zommi
Hi, Zommi.
Erstmal: WOW...
Habe das ganze jetzt nur überflogen, da ich schon von der Arbeit zuhause bin, aber ich werde mich morgen dann mal da rein fuchsen.
Schon mal im voraus TAUSEND DANK für dein Bemühen!
Liebe Grüße,
Christian.
Hi @ All.
Habe mal eine Klasse geschrieben, die genau dieses Problem mit Hilfe des GNU Linear Programming Kit löst.
using System;
using System.Text;
using System.IO;
using System.Windows.Forms;
using System.Diagnostics;
using System.Threading;
using System.Text.RegularExpressions;
using System.Collections.Generic;
namespace WPUProWo.Logic
{
public class GLPKSolver
{
private ICourse[] m_Courses = null;
private IStudent[] m_Students = null;
private Dictionary <string, ICourse> m_CoursesDict = new Dictionary<string, ICourse> ();
private Dictionary <uint, IStudent> m_StudentsDict = new Dictionary<uint, IStudent> ();
public GLPKSolver (ICourse[] courses, IStudent[] students)
{
m_Courses = courses;
m_Students = students;
foreach (var course in courses) {
m_CoursesDict.Add (TextHelpers.ValidLettersOnly (course.ID).ToUpper (), course);
}
foreach (var student in students) {
m_StudentsDict.Add (student.ID, student);
}
}
public ISolution Solve ()
{
var lpFileName = Path.Combine (Application.StartupPath, "min.lp");
if (File.Exists (lpFileName)) {
File.Delete (lpFileName);
}
var lp = GenerateLP ();
File.WriteAllText (lpFileName, lp, Encoding.ASCII);
var psi = new ProcessStartInfo {
FileName = "glpsol",
Arguments = "--lp min.lp -o min.sol",
WorkingDirectory = Path.GetDirectoryName(lpFileName)
};
var p = Process.Start (psi);
while (!p.HasExited) {
Thread.Sleep (10);
}
if (p.ExitCode != 0) {
return null;
}
var sol = File.ReadAllText (Path.Combine (Path.GetDirectoryName (lpFileName), "min.sol"), Encoding.ASCII);
return ParseSolution (sol);
}
private string GenerateLP ()
{
var sb = new StringBuilder ();
GenerateMinimizePart (sb);
sb.AppendLine ();
sb.AppendLine ();
GenerateSubjectToPart (sb);
sb.AppendLine ();
sb.AppendLine ();
GenerateGeneralPart (sb);
sb.AppendLine ();
sb.AppendLine ();
GenerateBinariesPart (sb);
sb.AppendLine ();
sb.AppendLine ();
sb.AppendLine ("END");
return sb.ToString ();
}
private void GenerateMinimizePart (StringBuilder sb)
{
sb.AppendLine ("Minimize");
sb.AppendLine ("\t\\Sum of each student's penalty value");
sb.Append ("\t");
foreach (var student in m_Students) {
sb.AppendFormat ("P_{0} + ", student.ID.ToString ().PadLeft (3, '0'));
}
sb.Remove (sb.Length - 3, 3);
}
private void GenerateSubjectToPart (StringBuilder sb)
{
sb.AppendLine ("Subject To");
sb.AppendLine ("\t\\Each student is assigned to exactly one course");
foreach (var student in m_Students) {
sb.Append ("\t");
foreach (var course in m_Courses) {
sb.AppendFormat ("{0}_{1} + ", TextHelpers.ValidLettersOnly (course.ID).ToLower (), student.ID.ToString ().PadLeft (3, '0'));
}
sb.Remove (sb.Length - 3, 3);
sb.AppendLine (" = 1");
}
sb.AppendLine ();
sb.AppendLine ("\t\\ Define the number of students in each course");
foreach (var course in m_Courses) {
sb.Append ("\t");
foreach (var student in m_Students) {
sb.AppendFormat ("{0}_{1} + ", TextHelpers.ValidLettersOnly (course.ID).ToLower (), student.ID.ToString ().PadLeft (3, '0'));
}
sb.Remove (sb.Length - 3, 3);
sb.AppendFormat (" - {0}", TextHelpers.ValidLettersOnly (course.ID).ToUpper ());
sb.AppendLine (" = 0");
}
sb.AppendLine ();
sb.AppendLine ("\t\\ Limit the number of students in each course (min, max)");
foreach (var course in m_Courses) {
sb.AppendFormat ("\t{0} >= {1}", TextHelpers.ValidLettersOnly (course.ID).ToUpper (), course.MinAttendants);
sb.AppendLine ();
sb.AppendFormat ("\t{0} <= {1}", TextHelpers.ValidLettersOnly (course.ID).ToUpper (), course.MaxAttendants);
sb.AppendLine ();
}
sb.AppendLine ();
sb.AppendLine ("\t\\Define the penalty of each student based in his wished");
foreach (var student in m_Students) {
sb.Append ("\t");
foreach (var course in m_Courses) {
var penalty = 1000;
if (course.ID == student.ThirdChoice) {
penalty = 100;
} else if (course.ID == student.SecondChoice) {
penalty = 10;
} else if (course.ID == student.FirstChoice) {
penalty = 1;
}
sb.AppendFormat ("{2} {0}_{1} + ", TextHelpers.ValidLettersOnly (course.ID).ToLower (), student.ID.ToString ().PadLeft (3, '0'), penalty);
}
sb.Remove (sb.Length - 3, 3);
sb.AppendFormat (" - P_{0}", student.ID.ToString ().PadLeft (3, '0'));
sb.AppendLine (" = 0");
}
}
private void GenerateGeneralPart (StringBuilder sb)
{
sb.AppendLine ("General");
foreach (var student in m_Students) {
sb.AppendFormat ("\tP_{0}", student.ID.ToString ().PadLeft (3, '0'));
sb.AppendLine ();
}
foreach (var course in m_Courses) {
sb.AppendFormat ("\t{0}", TextHelpers.ValidLettersOnly (course.ID).ToUpper ());
sb.AppendLine ();
}
}
private void GenerateBinariesPart (StringBuilder sb)
{
sb.AppendLine ("Binaries");
foreach (var course in m_Courses) {
foreach (var student in m_Students) {
sb.AppendFormat ("\t{0}_{1}", TextHelpers.ValidLettersOnly (course.ID).ToLower (), student.ID.ToString ().PadLeft (3, '0'));
sb.AppendLine ();
}
}
}
private ISolution ParseSolution (string text)
{
var lines = GetLines (text);
var penalties = new Dictionary<uint, Line> ();
var choices = new Dictionary<uint, List<Line>> ();
var courses = new Dictionary<string, Line> ();
var penaltyRegex = new Regex (@"^P_(?<ID>\d+)$", RegexOptions.Compiled);
var choiceRegex = new Regex (@"^\w+_(?<ID>\d+)$", RegexOptions.Compiled);
var courseRegex = new Regex (@"^\w+$", RegexOptions.Compiled);
foreach (var line in lines) {
var penaltyMatch = penaltyRegex.Match (line.RowName);
var choiceMatch = choiceRegex.Match (line.RowName);
if (penaltyMatch.Success) {
var studentID = Convert.ToUInt32(penaltyMatch.Groups ["ID"].Value);
penalties.Add (studentID, line);
} else if (choiceMatch.Success) {
var studentID = Convert.ToUInt32(choiceMatch.Groups ["ID"].Value);
if (!choices.ContainsKey (studentID)) {
choices.Add(studentID, new List<Line>());
}
choices[studentID].Add (line);
} else if (courseRegex.IsMatch (line.RowName)) {
courses.Add (line.RowName, line);
}
}
foreach (var pair in penalties) {
m_StudentsDict [pair.Key].Penalty = pair.Value.Activity;
}
foreach (var pair in choices) {
var course = "";
foreach (var line in pair.Value) {
if (line.Activity == 1) {
course = line.RowName;
break;
}
}
course = course.Substring (0, course.IndexOf ("_")).ToUpper();
m_StudentsDict [pair.Key].Assigned = m_CoursesDict [course].ID;
}
foreach (var pair in courses) {
m_CoursesDict [pair.Key.ToUpper()].RealAttendants = pair.Value.Activity;
}
return new Solution {
Courses = m_Courses,
Students = m_Students
};
}
private Line[] GetLines (string text)
{
var lines = text.Replace ("\r\n", "\n").Replace ("\r", "\n").Split ('\n');
var list = new List<Line> ();
var headersFound = 0;
var headersRegex = new Regex (@"^(-|\s)+$", RegexOptions.Compiled);
foreach (var line in lines) {
if (headersRegex.IsMatch (line)) {
headersFound++;
continue;
}
if (headersFound == 2 && line.Trim () != "") {
var parsed = ParseLine(line);
if (parsed != null) {
list.Add(parsed);
}
} else if (headersFound == 2 && line.Trim () == "") {
headersFound++;
}
}
return list.ToArray ();
}
private Line ParseLine (string text)
{
var lineRegex = new Regex (@"^\s*(?<Number>\d+)\s*(?<RowName>\w+(_\d+)?)\s*\*\s*(?<Activity>\d+)\s*(?<LowerBound>\d+)\s*(?<UpperBound>\d*).*?$", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Singleline);
var match = lineRegex.Match (text);
if (match.Success) {
return new Line {
Number = Convert.ToInt32(match.Groups ["Number"].Value),
RowName = match.Groups ["RowName"].Value,
Activity = Convert.ToInt32(match.Groups ["Activity"].Value)
};
}
return null;
}
private class Line
{
public int Number { get; set; }
public string RowName { get; set; }
public int Activity { get; set; }
}
private class Solution : ISolution
{
public IStudent[] Students { get; set; }
public ICourse[] Courses { get; set; }
}
}
public interface IStudent {
uint ID { get; }
string FirstChoice { get; }
string SecondChoice { get; }
string ThirdChoice { get; }
string Assigned { set; }
int Penalty { set; }
}
public interface ISolution {
IStudent[] Students { get; }
ICourse[] Courses { get; }
}
public interface ICourse {
string ID { get; }
int MinAttendants { get; }
int MaxAttendants { get; }
int RealAttendants { set; }
}
public static class TextHelpers
{
public static string ValidLettersOnly(string text) {
var normalized = text.Normalize(NormalizationForm.FormKD);
var sb = new StringBuilder();
foreach (var chr in normalized) {
var info = CharUnicodeInfo.GetUnicodeCategory (chr);
if (info == UnicodeCategory.LowercaseLetter || info == UnicodeCategory.UppercaseLetter) {
sb.Append(chr);
}
}
return sb.ToString();
}
}
}
@zommi:
Nochmal VIELEN DANK! Ich hätte das alleine nie hinbekommen bzw. wäre nie auf die Idee gekommen, GLPK zu verwenden...
Gruß,
Christian.
Nur so als kleiner Tipp der mir in deiner Klasse gerade aufgefallen ist. Verwende doch die WaitForExit()-Methode, um auf deinen gestarteten Prozess zu warten. Das erzeugt genau den selben Effekt, den du dir da mit dieser etwas unschönen while-schleifen-sleep Kombination gebaut hast 😉
Hi TheBraniac,
freut mich, dass du eine Lösung hast implementieren können.
Dennoch mein Tipp: Schau dir nochmal die Google or-tools an.
Damit wird dein Code viel viel viel viel eleganter 😉
Denn der C#-Wrapper spricht nicht nur unterschiedliche Solver-Backends an (darunter GLPK), sondern bietet gleichzeitig auch eine schöne "Natural API".
Hier mal der Link zu deren Beispiel-Code: csintegerprogramming.cs.
beste Grüße
zommi