Wettbewerb / Vergleich von Blockungsprogrammen

Hier können alle Themen rund um die neuen zusätzlichen Blockungsprogramme diskutiert werden.

Moderator: wschrewe

Benutzeravatar
wschrewe
Fachberater*in
Beiträge: 1686
Registriert: Dienstag 25. September 2018, 17:36
Schulform: BK (Pensionär)
Kontaktdaten:

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von wschrewe »

Ich habe mal die Daten von Herrn Bartsch ergänzt und fehlerbereinigt. Mit den angehängten Textdateien kann eine funktionierende Blockung angelegt werden.

Ich habe mit dem neuen Algorithmus geblockt und nach 1 Min. 37 Sek. bei NV = 0 und KD = 4 abgebrochen. Die Vorgaben von Herrn Bartsch wurden dabei nicht ausgewertet.
Dateianhänge
Blockung_Komplett.zip
(10.92 KiB) 171-mal heruntergeladen
Mit freundlichen Grüßen
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von B. Bartsch »

... ich habe im ersten Beitrag die Datei "Wettbewerb.zip" hochgeladen. Diese werde ich in Zukunft mit den vorhandenen Testdaten ergänzen.

Die Datei enthält nun zusätzlich zum Ordner "EF_01" den Ordner "EF_02" (Blockung von Herrn Westphal) und den Ordner "EF_03" (Blockung von Herrn Friebe.

EF_01:
Ersetzt mit den korrigierten Daten von Herrn Schrewe. KD2 ist möglich bei NW0.

EF_02:
Mein Programm kommt in akzeptabler Zeit nur bis KD5. Vom Gefühl her müsste es viel besser gehen. Ggf. sind die Nebenbedingungen und die Schülerfixierungen aber nicht ganz ohne. (0 Nichtwähler)

EF_03:
Meiner Meinung nach ist das eine extrem schwere Blockung. Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
B. Bartsch
Benutzeravatar
wschrewe
Fachberater*in
Beiträge: 1686
Registriert: Dienstag 25. September 2018, 17:36
Schulform: BK (Pensionär)
Kontaktdaten:

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von wschrewe »

Bei EF_03 meldet mir Kurs, dass eine konfliktfreie Blockung nicht möglich ist, weil vier Schüler mehr als 12 Fächer gewählt haben:

Name23, Vorname23 (13 Fächer)
Name43, Vorname43 (13 Fächer)
Name47, Vorname47 (13 Fächer)
Name75, Vorname75 (13 Fächer)

??
Mit freundlichen Grüßen
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von B. Bartsch »

...es sollen ja auch 13 Schienen sein (s. A_VORGABEN.txt).
B. Bartsch
Volker_Dirr
Beiträge: 94
Registriert: Sonntag 2. Dezember 2018, 19:55
Schulform: Realschule

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von Volker_Dirr »

B. Bartsch hat geschrieben: Freitag 12. Juni 2020, 23:15 EF_03:
Meiner Meinung nach ist das eine extrem schwere Blockung. Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
Danke.
Solche Datensätze können extrem hilfreich sein, insbesondere wenn man die Grund für so ein Verhalten versteht.

Daher wollte ich auch synthetische Tests machen, bei denen ich gezielt versuche bestimmte Besonderheiten einzubauen um auszumessen ob bzw. wie groß die Auswirkungen sind. Es hätte den Vorteil, dass man sofort den Grund weiß und besser abschätzen kann wie viel Einfluss die Besonderheit hat.

Aus dem Bereich Stundenplanung habe ich auch Datensätze, die extrem schwierig sind. Dort habe ich schon Datensätze mehrfach über 4 Wochen laufen lassen und keine Lösung gefunden. Interessanterweise habe ich denselben Datensatz in 1 von 1000 Fällen mit meiner CPU innerhalb von ~10 Minuten lösen können. Sprich: Es ist (zumindest bei meinem Algorithmus) effektiver nur kurz zu suchen.
Natürlich besteht die Gefahr, dass man bei zu kurzer Suchzeit nie eine Lösung finden wird, obwohl es Lösungen gibt. Daher kann ich nicht sagen genau sagen wie lange man mindestens bzw. höchstens suchen sollte. Das muss man etwas ausprobieren. Ich habe als Limit bei mir erstmal vorsichtige 15 Minuten vorgegeben. Wahrscheinlich muss/kann/sollte ich den Wert reduzieren.

Ich kann nicht in die Algorithmen von Kurs42, Kurs42_To_CNF, Untis, ... gucken (möchte ich auch nicht), aber ich habe anhand der grafischen Ausgabe dein Eindruck als wenn sie sogar deutlich schneller "neu starten". Oder täuscht das nur, weil ihre Algorithmen gelerntes Wissen mit in den Neustart nehmen?
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von B. Bartsch »

Ich kann nicht in die Algorithmen von Kurs42, Kurs42_To_CNF, Untis, ... gucken (möchte ich auch nicht), aber ich habe anhand der grafischen Ausgabe dein Eindruck als wenn sie sogar deutlich schneller "neu starten". Oder täuscht das nur, weil ihre Algorithmen gelerntes Wissen mit in den Neustart nehmen?
Der neue Algorithmus von Kurs42 startet oft neu, sieht man auch an der Prozentanzeige (für jeden Durchlauf).

Kurs42_To_CNF kann beides. Ich berechne ohne Neustart zunächst KDs - ja nach Blockung - von 20 bis 10 (mit einem Thread). Danach wechsle ich zum Auto-Modus mit 8 Threads, diese starten nur dann neu, wenn ein UNSAT* (nicht lösbar) gefunden wurde, oder ein SAT (gelöst), dann mit der Vorgabe weniger KD zu versuchen.

*UNSAT heißt in meinem Auto-Modus nicht, dass das globale Problem unlösbar ist, denn im Auto-Modus fixiere ich zufällig entweder Kurse in Schienen oder Schüler in Kursen.
B. Bartsch
Volker_Dirr
Beiträge: 94
Registriert: Sonntag 2. Dezember 2018, 19:55
Schulform: Realschule

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von Volker_Dirr »

Ja, die Idee mit dem Übernehmen von Wissen in andere Threads hatte ich schon verstanden. Der Ansatz hat schon etwas. Probiere ich aus sobald ich auch mehrere Threads machen kann. Kann ich leider noch nicht effektiv selbst. Ich kann es nur "simulieren", indem ich das Programm einfach mehrfach öffne und parrallel laufen lassen. Das ist dann natülich ohne Übernahme von Wissen. Trotzdem empfehlenswert. (zumindest bei schweren Daten; bei (sehr) leichten Daten ist es unnötig.

Ich meinte die Frage bezogen auf einen einzigen Thread. Wenn man in Kurs42_To_CNF auf nur einem Thread rechnet, dann habe ich den Eindruck als wenn dort auch mehrfach neu gestartet wird. Ist das ein für den Algorithmus ein kompletter Neustart und der versucht das noch einmal von vorne oder nimmt der Wissen mit in den zweiten Durchgang? Oder verstehe ich die Anzeige falsch und es ist nur ein "Zwischenbericht" und der Algorithmus macht an genau der Stelle weiter wo er gerade ist, oder er geht nur X Schritte zurück (behält also Wissen).
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von B. Bartsch »

Es wird ja im Hintergrund der SAT Solver aufgerufen, dieser startet extrem oft die Berechnungen neu.
B. Bartsch
Volker_Dirr
Beiträge: 94
Registriert: Sonntag 2. Dezember 2018, 19:55
Schulform: Realschule

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von Volker_Dirr »

B. Bartsch hat geschrieben: Freitag 12. Juni 2020, 23:15 EF_03:
[...] Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
Kann ich bestätigen. Ist bei mir ähnlich.
Ich habe es 10 mal mit KD9 gelöst und da scheint irgendetwas besonderes zu sein.
Mein schnellstes war in 8 Sekunden. Das langsamste in 532 Sekunden. Im Schnitt 165 Sekunden.
Das hängt dort ab und zu ganz deutlich.
Das ist intressant. Gucke ich mir in den Ferien in Ruhe an.

Ich vermute die fixierten Kurse mit den Extravorgaben für minimale und maximale Kursgrößen sind die Koop Kurse, oder?
Wäre es nicht sinnvoll, wenn man da wirklich die Koopschüler fixiert, damit die Kursdifferenzen über alle Kurse gleichmäßiger verteilt werden können?
Oder ist das Absicht und als Ausgleich für die Lehrer gedacht, weil die an zwei Konferenzen anwesend sein müssen?
B. Bartsch
Fachberater*in
Beiträge: 321
Registriert: Dienstag 4. Dezember 2018, 14:14
Schulform: Gymnasium

Re: Wettbewerb / Vergleich von Blockungsprogrammen

Beitrag von B. Bartsch »

Ich vermute die fixierten Kurse mit den Extravorgaben für minimale und maximale Kursgrößen sind die Koop Kurse, oder?
ja
Wäre es nicht sinnvoll, wenn man da wirklich die Koopschüler fixiert, damit die Kursdifferenzen über alle Kurse gleichmäßiger verteilt werden können?
Man könnte Dummy Schüler in die Kurse einfügen UND fixieren, dann würde man max. SuS für den Kurs nicht benötigen.
Oder ist das Absicht und als Ausgleich für die Lehrer gedacht, weil die an zwei Konferenzen anwesend sein müssen?
Das verstehe ich nicht.
B. Bartsch
Antworten

Zurück zu „Externe Blockungsprogramme“