Optimale Berechnungsmethode

[noddy11]

Was ist zur Berechnung eigentlich besser?
FET ganz lange rechnen lassen oder mehrere Pläne mit nur begrenzter Zeit rechnen lassen?  So dass oft neu mit der Berechnung begonnen wird.
Auf eine Antwort bin ich gespannt.

[Volker Dirr]

Die Frage ist schwer zu beantworten. Ich gebe mal zuerst eine mehr theoretische Antwort und anschließend eine praktische Antwort:

FET startet (i.d.R.) zufällig mit einem möglichen Lösungsweg (Startwert). Es gibt nur eine begrenzte (aber sehr große!) Anzahl an Startwerten und zu jedem Startwert kann praktisch und reproduzierbar nachvollzogen werden wie lange es dauert eine Lösung zu finden. Dies ist allerdings nicht vorhersagbar und aufgrund der großen Anzahl wird es wohl nie jemand für alle Startwerte ausprobieren.

Nehmen wir einmal an, es würde nur 4 mögliche Startwerte geben. Dann könnte ein Datensatz z.B. folgende Zeiten brauchen:

Beispiel 1:
Lösungen werden nach folgenden Zeiten gefunden:
10 min, 11 min, 9 min und 13 min.

Da der Startwert zufällig gewählt wird, dauert es ohne Neustart mindestens 9 Minuten und höchstens 13 Minuten. Im Schnitt unter 11 Minuten.

Ein Neustart nach 8 Minuten (oder früher) ist fatal. Wir würden nie eine Lösung finden.

Wenn man nach 9 Minuten neu startet, dann würden wir mit 25% Wahrscheinlichkeit eine Lösung nach 9 Minuten finden. Andernfalls würde es im besten Fall 18 Minuten dauern. Es könnte aber auch 27 oder 36 Minuten dauern. Im Schnitt also deutlich mehr als die durchschnittlich 11 Minuten ohne Neustart (siehe oben).

In diesem Fall würde sich somit ein Neustart nicht lohnen. Sogar im Gegenteil: Es ist schlechter.

Stellt man die Neustartzeit höher (im Extremfall auf 13 Minuten), dann würde es überhaupt keinen Unterschied machen zu dem Berechnen ohne Neustart.

Bei Beispiel 1 macht es also i.d.R. keinen Sinn einen Neustart einzustellen.


Beispiel 2:
Lösungen werden nach folgenden Zeiten gefunden:
2 min, 10 min, 20 min und 16 min.

Ohne Neustart würden wir im schlimmsten Fall 20 min warten müssen; im besten Fall nur 2 Minuten.

Stellen wir den Neustart auf 1 Minute, dann würden wir keine Lösung finden. Ein Neustart wäre also wieder fatal.

Stellen wir den Neustart auf 2 Minuten, dann müssten wir im schlimmsten Fall 8 Minuten warten. Ein Neustart würde ich also auf jeden Fall lohnen.

Stellen wir den Neustart zum Beispiel auf 15 Minuten, dann müssten wir im schlimmsten Fall aber 15+15+10=40 Minuten warten. Ich überlasse es mal jeden selbst nachzurechnen wie viele schlimmsten Fälle es gibt und wie viele bessere Fälle es gibt.


Stellen wir also bisher fest:
- Wenn man einen Datensatz mit hohen Streuungen hat, dann lohnt es sich eher neu zu starten. Sind die Streuungen gering, dann lohnt es sich nicht neu zu starten.
- Sind die Neustartzeiten zu gering, dann finden wir im schlimmsten Fall nie eine Lösung. Sind sie etwas ,,zu groß", dann muss man länger warten als bei einer Berechnung ohne Neustart. Sind sie (viel) zu groß, dann unterschiedet es sich nicht von der Berechnung ohne Neustart.

Dummerweise kann man sowohl Streuung also auch ,,richtige" Neustartzeit nicht vorhersagen, dass muss jeder selbst mit seinem Datensatz und seiner CPU ausprobieren.
Wenn man etwas genauer überlegt, dann kommt es nicht nur darauf an, ob es einen/wenige kurze Lösungszeiten gibt. Wenn es davon nämlich zu wenige gibt, dann könnte ein neu Starten wiederrum schlecht sein. Es sollten schon "viele" sein. (Wenn man ein Startlimit von 15 Minuten setzt, dann hat man bei einem Rechenkern unter 100 Lösungsversuche pro Tag. Sprich: Die Anzahl an kurzen Lösungszeiten sollte schon bei etwa 1% (oder höher) liegen, da es sonst in der praxis zu unwahrscheinlich ist diese zu erwischen).


Kommen wir jetzt zur praktischen Antwort:
Solange ich noch an der UV arbeite und nach grundsätzlichen Fehlern suche, deaktiviere ich mindestens die Einschränkung der max Anzahl an Freistunden für Lehrer. Dies schalte ich erst (kurz) vor der finalen Rechnung ein. Dadurch erhalte ich schon mal ,,Lösungen" grundsätzlich schneller.

Solange mein finaler Plan ,,leicht" ist und aufgrund meiner Erfahrungen in wenigen Stunden lösbar ist, schalte ich keinen Neustart an. Natürlich könnte man Pech haben und zufälligerweise Tage für eine Lösung warten müssen. Um dieses Risiko zu minimieren, starte ich FET genau so oft, wie meine CPU Rechnenkerne hat.
Mit dieser Technik hatte ich an meiner alten Schule sehr gut arbeiten können. I.d.R. hatte ich dann für den finalen Lauf den Rechner über Nacht ohne Neustart auf mehreren Kernen Rechnen lassen und am nächsten Morgen hatte ich viele Lösungen.


Der Datensatz an meiner neuen Schule ist leider wesentlich schwerer, den habe ich in den Ferien schon ein paar mal auf 4 Rechnenkernen ohne Zeitbegrenzung rechnen lassen. Nach 14 Tagen ohne eine Lösung zu erhalten.
Daraufhin habe ich die Neustartvariante gewählt. Mit einem 30 Minuten Zeitlimit hatte ich nach einen Tag zumindest ein paar Lösungen.
Hier lohnt sich also ein Neustart.
Bei meinem Datensatz habe ich beobachtet, dass ich i.d.R. in unter 5 Minuten mehr als 98% aller Aktivitäten setze. Anhand der oberen Versuchsreihe konnte ich auch sehen, dass ich eine Lösung in unter 2 Minuten gefunden hatte. Eine andere nach fast 30 Minuten. (Und nicht vergessen: 4 Rechner ohne Neustart haben selbst nach 2 Wochen keine Lösung gefunden!).
In den letzten Jahren habe ich gemerkt, dass bei mir Neustartzeiten zwischen 20 und 30 Minuten sinnvoll sind. Dabei lasse ich auf mehreren Rechnern (i.d.R. knapp 16 Rechenkerne) rechnen. Nach etwa 10 Stunden (also über NAcht) finde ich dann i.d.R. eine Lösung.
Wirklich empfehlen kann ich diese Taktik aber nicht. In den Sommerfeiren ist das ok. Aber jetzt, bei dem Plan fürs 2. Halbjahr ist das doch "ungünstig". Ich habe zwar damit bisher immer eine Lösung erhalten, aber man schläft doch recht unruhig, da dass Risiko keine Lösung zu finden nicht klein ist. Wenn man dann am Ende doch noch einen Fehler sieht und nochmal rechnen muss, der gerät schon mel schnell in Zeitnot. Wer da zu nervös ist sollte dann doch lieber ein paar Einschränkungen herausnehmen und ohne Zeitlimit auf mehreren Kernen rechnen lassen.
Wer das Risiko eingehen möchte, dem würde ich empfehlen mal grob darauf achten wie lange es etwa dauert mindestens 98% aller Aktivitäten zu setzen. Diesen Wert würde ich (mindestens) vier bis sechs mal so groß machen und als Zeitlimit setzen. Wer es etwas genauer wissen möchte, der macht mit seinem Datensatz einfach einen kleine Testreihe:
Einmal 24 Stunden lang suchen lassen mit 10 Minuten Zeitlimit.
Einmal 24 Stunden lang suchen lassen mit 20 Minuten Zeitlimit.
Einmal 24 Stunden lang suchen lassen mit 30 Minuten Zeitlimit.
...

oder noch besser: mal ~1000 Pläne mit ~10? Stunden Zeitlimit rechenen lassen und mal eine Statistik über die benötigten Lösungszeiten erstellen.
Ich werde das mal evtl. für 1 oder 2 Pläne machen. Wird aber etwas dauern und wird leider nicht allgemein auf andere Datensätze übertragbar sein.

[noddy11]

Hallo Herr Dirr!

Vielen Dank für die sehr ausführliche Beschreibung.
Bei mir sind 98% nach ca. 4 Minuten berechnet. Also werde ich es jetzt mal mit einem Zeitlimit von 20 Minuten über die nächsten 24 Stunden ausprobieren.
Ich bin sehr gespannt und werde vom Ergebnis berichten. Noch bin ich nicht in Panik, da ich noch zwei Wochen Zeit für den neuen Halbjahresplan habe.

Vielen Dank nochmal.

[noddy11]

Ich kann jetzt schon ein kurzes Feedback geben.
Auf dem einen Prozess wird bereits seit 10 Stunden gerechnet. Nach 1h39Min war bis auf eine Aktivität alles gesetzt.
Der zweite Prozess wurde mit 72facher Wiederholung gestartet und mit einem Limit von 20 Minuten.
Nach 2,5 Stunden hatte ich bereits 2 erfolgreich berechnete Pläne.

Ein sehr guter Tipp Herr Dirr.

[noddy11]

Hier das Ergebnis nach der 24 Stundenrechnung:
Die Einzelplanberechnung wurde nach 10,5 Std. erfolgreich beendet.
Beim Multiplan wurden 9 von 72 Plänen berechnet.
Dabei wurde ein Plan schon nach 2 Minuten und 29 Sekunden generiert.
Die längste Berechnung im Limit von 20 Minuten lag bei 18 Minuten und 15 Sekunden.
4 der 9 Pläne wurden unter 10 Minuten berechnet.

Auf jeden Fall hat mir der Tipp von Herrn Dirr sehr geholfen.
Vielen Dank dafür.

[Volker Dirr]

Eine gute Quote.
Interessant ist, dass bei ihnen es noch in gute 10% der Fälle leicht zu lösen ist. Da lohnt sich auf jeden Fall die Neustart-Variante.
Dann können sie sich ja evtl. sogar noch trauen ihren Plan noch etwas "schwerer" zu machen / zu optimieren.

Mein Plan hat da eine wesentlich schlechtere Quote. Interessant zu wissen wäre es jetzt, ob diese Quote nur "langsam" immer schlechter wird, bzw. wann sie abrupt auf 0% fällt (wie in meiner theoretischen Antwort vom Anfang). Ich habe bei mir auch schon Quoten deutlich unter 0,1% gehabt. Das ist dann der Moment, wo man doch etwas unruhig wird/werden kann wenn die Zeit knapp ist.
Ich befürchte, dass wir die Antwort darauf nie erhalten werden. Ich versuche trotzdem in den nächsten Tagen mal ein genaueres "Streumuster" zu erstellen. Die leichten Variante habe ich schon fertig, aber die interessanten/schweren fehlen noch. Das werde ich aber wohl erst nach den Zeugnissen fertig bekommen und dann hier im Forum berichten.