Optimale Einteilung einer Menge in disjunkte Untermengen

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Ich habe das Thema bereits im Matheboad gestellt, aber - wie so oft - bekommt man da keine Antwort.

Das Thema beschäftigt meine Frau praktisch und mich theoretisch.

Gegeben sei eine Schulklasse (Menge U), Vorlieben und Abneigungen der Schüler untereinander (ganzzahlige Gewichte a_st; s,t indiziert die Schüler) sowie eine Einteilung der Schulklasse in verschiedene Gruppen (paarweise disjunkte Teilmengen U_n).

Die Schüler werden nummeriert:

Man kann jeder Untermenge U_n ein S-Tupel zuordnen

wobei die u_n^s 1 sind, wenn der s-te Schüler Element der Gruppe n-ten Gruppe ist, 0 sonst.

Gesucht ist die optimale Einteilung, so dass folgendes G maximal wird:

Die Anzahl N in n = 1..N für die Anzahl der Teilmengen U_n sowie die Gewichte a_st seien fest vorgegeben. Die Paare <s,t>_n sind so definiert, dass nur Paare in die Summation einbezogen werden, für die s,t zur selben Teilmenge n gehören.

Ich kann dies auf ein Pseudo-Skalarprodukt abbilden:

Die U_n definieren S-Tupel bzw. Vektoren in einem S-dim. Vektorraum. Die Anzahl der insgs. möglichen Konstellationen beträgt

Dabei kann der erste Schüler in einer aus N Gruppen sein, der zweite Schüler ebenfalls etc. Bei z.B. S=30 Schülern und N=6 Gruppen ergibt sich Z(6,30) = 6^30 = 2.2 * 10^23. In der Praxis wird man natürlich eine Minimal- und eine Maximalgröße der Gruppen festlegen, z.B. genau 5 oder 4 bis 6, so dass diese Zahl deutlich reduziert wird (jedoch immer noch zu groß ist, um alle Konstellationen durchzuprobieren).

Meine Idee wäre, dieses Problem mittels Monte-Carlo-Simulation / importance sampling und simulated Annealing zu lösen, indem ich die Zugehörigkeit der Schüler s zu den Untergruppen U_n "würfle" und so das Maximum g über alle G suche

Fragen:
1) unter welchem Sichwort finde ich denn etwas zu diesem Optimierungsproblem? das hat in der Fachliteratur bestimmt einen Namen
2) ist mein Ansatz sinnvoll?
3) welche weiteren Lösungsmethoden kommen in Frage?

Die erste Frage ist mir am wichtigsten.

jh8979 · Moderator Anmeldungsdatum: 10.07.2012 Beiträge: 8583

Nice

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Danke!

Hab' die Frage mal dort gestellt:

Discrete optimization - optimized assignment of members to subsets / partitioning of a set to subsets

Ich · Anmeldungsdatum: 11.05.2006 Beiträge: 913 Wohnort: Mintraching

Das ist Cluster Analysis. Das einzig Ungewöhnliche an deiner Aufgabenstellung ist die "Abstandsfunktion", die du statt einer "Positionsangabe" der Elemente zur Verfügung hast. Ich könnte mir vorstellen, dass ein solcher Positionsraum u. U. viele Dimensionen bräuchte und die Algorithmen dann schlecht funktionieren. Kenne mich aber nicht aus damit, vielleicht ist alles kein Problem.

Entdecker22 · Anmeldungsdatum: 11.08.2016 Beiträge: 2

Was für ein praktisches Problem deiner Frau liegt denn dahinter?
Bin neugierig

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Ich · Anmeldungsdatum: 11.05.2006 Beiträge: 913 Wohnort: Mintraching

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Ich · Anmeldungsdatum: 11.05.2006 Beiträge: 913 Wohnort: Mintraching

Nö, wie gesagt kenne ich mich da nicht so aus. Aber nachdem es nur darum geht, dass die Funktion "Abstand" eine Zahl zurückgibt, sehe ich da kein Problem. Wenn's zu "hochdimensional" ist oder unterbestimmt, weil du nur ein paar Binärwerte hast, dann muss man vermutlich tricksen, könnte ich mir vorstellen.
In der englischen Wikipedia findest du aber genügend Beispiele, die man adaptieren könnte. Ob's dann funktioniert ist eine andere Frage, aber das ist schon die Klasse, in die dein Problem fällt.

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Vom Gefühl her bleibe ich bei diskreter Optimierung / 0-1-Programmierung und meinen o.g. Vorschlägen (die hab' ich schon mal implementiert und die funktioniert prinziell).

Trotzdem danke für die Idee.

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Noch eine Idee? Bei stackexchange rührt sich niemand.

Ich schwenke gerade auf threshold acceptance oder evtl. Sintflut um, da performanter. Kennt sich da jemand aus?

MI · Anmeldungsdatum: 03.11.2004 Beiträge: 828 Wohnort: München

Wenn ich das richtig sehe, dann kann man das Problem doch so umformulieren:

Jeder Schüler bildet einen Vertex eines Graphen, jede Präferenz ein Edge mit Gewichtung (positiv/negativ). Die Aufgabe ist eine Partitionierung in

möglichst gleichgroße Teile zu finden, die das Gesamtgewicht aller Graphen der Partitionierung maximiert.

Da das gesamte Gewicht des Graphen feststeht (das ist einfach die Summe der Matrix A), ist die Maximierung des Gesamtgewichtes der Partitionierung äquivalent zur Minimierung des Gewichtes der Edges, die durchgestrichen werden (also von Schülern, die nicht in derselben Gruppe arbeiten).

Wenn ich das richtig sehe, laufen solche Probleme unter dem Namen Graph partition. Um mal ein Beispiel eines Papers zu finden, was so etwas macht (die Gruppengröße ist dabei nur "ungefähr gleich", ich weiß nicht, was das genau in der Praxis heißt, ich habe nur den Abstract gelesen) zum Beispiel dieses hier: http://www.math.cmu.edu/~kandreev/kpart.pdf

Ich muss gestehen, dass ich genau Null Ahnung von Graphentheorie habe und ich könnte da was übersehen, aber vielleicht hilft ja zumindest die Umformulierung + der Name weiter!

Viele Grüße
MI

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Super, das ist ein völlig neuer Ansatz.

Ist bei mir etwas komplizierter, da mein A keine (0,1)-Matrix ist, sondern eine (-M,...,+M)-Matrix, d.h. dass i.A. ein gewichteter Graph mit Gewichten a_st vorliegt; dafür finde ich vergleichsweise wenig Literatur, aber ich gab' da keinen Stress.

Jedenfalls danke nochmal.

MI · Anmeldungsdatum: 03.11.2004 Beiträge: 828 Wohnort: München

In dem von mir verlinkten Artikel steht in der Conclusion, dass der Algorithmus sich ganz einfach auf gewichtete Graphen verallgemeiner lassen würde. Leider kenne ich mich da wirklich nicht aus.

Es wäre aber mal interessant das anzuwenden und vielleicht damit zu vergleichen was passiert, wenn man die Schüler selbst aussuchen lässt. Ich vermute, dass die schon ziemlich nahe am Optimum liegen würden. Man kann dann natürlich auch mal die Vorzeichen umkehren und Leute zusammenarbeiten lassen, die sich eben gerade nicht mögen Big Laugh

.

Gruß
MI

franz · Anmeldungsdatum: 04.04.2009 Beiträge: 11583

Darf ich das statische Mögen / Nichtmögen vorsichtig in Zweifel ziehen durch Themenabhängigkeit beispielsweise oder, bißchen nichtlinear, weil mache Schöler eine Gruppeneinteilung ablehnen - wegen des einteilenden Lehrers?

Eine anspruchsvolle mathematische Spielerei sicher, die mich etwas an die Berücksichtigung der Gebetswünsche von Mohammedanern oder Stillzeiten junger Mütter in der Kriegsplanung der Bundeswehr erinnert.

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18092

Es geht voran.

Ich habe noch eine Frage zur Abschätzung der Kombinatorik bzw. der Komplexität. Gesucht ist die Anzahl der Möglichkeiten, S unterscheidbare Schüler auf N unterscheidbare Klassen zu verteilen. Für jeden Schüler stehen N Klassen zur Verfügung. Das liefert also zunächst

Diese Abschätzung ist jedoch praxisfern; man müsste eine zusätzliche Bedingung angeben, z.B. die minimale und die maximale Klassengröße.

Also: gesucht ist die Anzahl der Möglichkeiten, S unterscheidbare Schüler auf N unterscheidbare Klassen zu verteilen, wobei jede Klasse mindestens a und höchstens b Schüleranzahl haben muss.

Wie rechnet man das?

bassiks · Anmeldungsdatum: 11.08.2010 Beiträge: 194

Mal so als "Brute-Force" Variante, hätte ich das mal so formuliert:

Z' = Z - Summe unterschrtitten - summe überschritten + summe beides

Der letzte Summand muss leider sein weil sonst Kombinationen zweimal gezählt werden. Ohne dass ich es kontrolliert habe (nicht mal geplottet oder ähnliches, einfach mal aufgeschrieben) komme ich auf was in der Form:

Zur Erläuterung: Bei den ersten beiden Teilen summiere ich einfach über alles was a unterschreitet oder b überschreitet.
m steht dabei für die Anzahl der Klassen welche a unterschreiten. Das heißt ich habe in diesen Klassen bereits mindestens m Schüler, aber maximal m*a Schüler. Das heißt ich summiere dann über die möglichen Kombinationen S-l Schüler auf N-m Klassen zu verteilen. Jeder Summand wird multipliziert mit den Möglichkeiten l Schüler auf m Klassen zu verteilen, da dies wiederrum unterscheidbare Konfigurationen abgeben würde.
Beim zweiten Summanden steht m für die Anzahl der Klassen welche b überschreiten. Ich habe also mindestens b*m Schüler, aber maximal S-N+m, denn ich will in den anderen N-m Klassen ja noch mindestens einen Schüler haben. Summiert wird über die möglichen Kombinationen S-l Schüler auf N-m Klassen zu verteilen, wiederrum mit dem Faktor der Möglichkeiten l Schüler auf die anderen m Klassen zu verteilen.
Der letzte Teil ist...naja...^^.
Hier war der Gedankengang, dass ich mindestens 2 Klassen mit über- oder unterschrittener Schülerzahl habe. m summiert über die unterschrittenen, dann bleiben noch k-m überschrittene Schüler. Das heißt ich habe mindestens m+(k-m)*b Schüler auf die anderen Klassen zu verteilen, maximal aber m*a+S-l-N+k, denn ich darf in m Klassen a nicht überschreiten, und will aber für meine N-k Klassen auch noch genug Schüler haben um mindestens einen darin sitzen zu haben. Summiert wird über die Möglichkeit S-k-j Schüler auf die übrig gebliebenen N-k Klassen zu verteilen, mit den Faktoren durch jeweils verschiedene Möglichkeiten j Schüler auf N-k+m Klassen und l Schüler auf m Klassen zu verteilen.

Ich hab hier nichts durchgerechnet oder vereinfacht. Zum vereinfachen bietet sich evt. eine Möglichkeit mittels Chu-Vandermonde an (https://en.wikipedia.org/wiki/Vandermonde%27s_identity).
Ich habe das auch nicht nochmal durchgedacht, ist also sicher irgendwo ein Fehler, aber evt. liefert es dir einen Ansatz.