Speed of FET

[Ulrich Großmann]

Hi there,

I'm investigating FET at the moment and compare it to local search algorithms and wonder about the speed in terms of "steps".

Consider a "step" to be something like the following:
- evaluate, that activity A_1 can be put to timeslot T_1 and put it there.
- if no timeslot could be found and the activities B_1 to B_N have to be removed in order to place A_1, I consider this to be N steps.
- feel free to provide a better definition of an algorithm step.

I don't understand the algorithm good enough to know if there is even a meaningful definition of the term "step" for the FET algorithm. But as I don't need precise numbers but only a rough estimate, the definition doesn't need to be perfect.

Do you know any figures of how many steps FET performs per second roughly (say on an average environment)?

Furthermore: Do you know what is the slowest part of the algorithm during a step.
Parts may be:
- Evaluating if A_x in T_x breaks constraints.
- Looping inside the algorithm logic to decide the next step.

[Liviu Lalescu]

Hello,

Step is a try to put A_i. It will search for slots of the week in random order and if it finds a free good one, stops. Otherwise, we have a list of displaced activities for each slot and the algorithm chooses one slot and displaces B_1... B_n. The slots are then checked in a sorted order (prefer slots with fewer Bs first, but avoiding cycling). Hopefully, the algorithm will often stop with a good placement. Maximum depth of recursion is 14 and if we are at level>=5 we only try the first slot and return.

There is a limit on the number of total steps at level 0: 2*n_activities. After that, we place A_i and displace Bs at level 0.

I think the 2*n_activities tries at level 0 takes between 0.1 seconds to 10 seconds, depending on file (constraints, size) and computer.

Looping is easy/fast. Checking A_i for Bs is difficult/slow. We go through each constraint.

[Volker Dirr]

Ich sehe gerade ihre Freeware Software auf ihrer Homepage. Wenn die FET Dateien importieren können, dann könnten wir evtl. auch einen Link von hier bzw. Livius Homepage erstellen.
Achten Sie bitte darauf, dass FET der AGPL unterliegt. Da sie jetzt den FET Quelltext und Dokumentation lesen und dort ((evtl.) teilweise) Ideen und Techniken mehr oder weniger dirket übernehmen, müssten Sie ihre Software, die es verwendet, ebenfalls unter die AGPL stellen und die Urheber nennen. Am besten einmal die ganze AGPL prüfen. Aber sie kennen ja bestimmt die ähnlichen Probleme die Linux wine, ReactOS und anderen Projekten durch lesen von fremden Quelltext entstanden sind.

[Ulrich Großmann]

Hallo Herr Dirr,

vielen Dank für die Hinweise. Tatsächlich habe ich darüber nachgedacht und würde das gerne genauer mit Ihnen besprechen. Könnten Sie sich eventuell vorstellen, über meine E-Mail Kontakt mit mir aufzunehmen?

[Ulrich Großmann]

Hello Liviu,

thanks for the quick explanation. May I ask for better understanding more about the slow part?
- So as I understand it, it loops over all constraints so it has at least the complexity of O(n_constraints), right?
- Does evaluating one single constraint also involve looping (e.g. does evaluating constraint x involve looping over all activities / a subset of all activities, which will make evaluating x of the complexity O(n_activities))?
- Does evaluating some single constraints also involve nested loops?

[Volker Dirr]

Ich schreibe sie noch später per Email an. Ich komme gerade erst von der Arbeit zurück und muss mich erst mit Liviu kurzschließen.
Liviu antwortet immer extrem schnell und hätte Ihnen schon längst geantwortet. Er wartet noch auf meine Antwort. Ich werde das mit Liviu heute Nachmittag besprechen und mich danach bei ihnen melden. Sie können uns ihre Gedanken dazu auch gerne vorher mitteilen.