The stopping codditions of the used algorithm

[xing]

Hi Liviu,

Thanks for providing such an awesome open source timetabling software. It's very interesting and inspiring. If you have time, would you please help me out of the following questions that puzzle me.
1. Does the algorithm stops once it finds a feasible timetable? So how are other soft constraints, those constraints with less 100% weights, optimized?
2. If I want to try other algorithms, like Simulated Annealing, which parts should I modify?
3. And, at last, a small question,how long it takes you to develop the FET?

Thanks a lot.

Xingxing

[Volker Dirr]

1. see https://www.timetabling.de/manual/FET-manual.en.html#id_35
2. generate_pre.cpp and generate.cpp
3. Depending on what exactly you mean:
the whole software as it is now with all it's constraints, bugfixes, features ...? a few years

[Liviu Lalescu]

Hello, Xingxing,

Thank you for the appreciation!

In addition to what Volker said:

1. Yes, it stops. I place the activities in order. Each activity is placed in an empty slot or displaces other activities. Say it is placed. Then it must respect the constraints with 100%. If there is a constraint with say 95%, in 95% of cases it must respect it, or in 5% of cases it can break the constraint and still be placed correctly.

2. In generate.cpp there is the current main part of the algorithm. We have in FET 4.2.8 (latest FET-4) a genetic algorithm, highly NOTrecommendable, and very old (year 2007). I can tell you that the genetic algorithm is very weak, and probably also simulated annealing.

3. I think I found (rediscovered, I think) the good method of placing the activities, the main algorithm, and implemented the main part, in a few days (after trying in vain for 5 years). But correcting and implementing all the constraints and having all discussions and so on took many years of work. The important work is in the "engine" directory, and the really important part in generate.cpp.

[xing]

1. see https://www.timetabling.de/manual/FET-manual.en.html#id_35
2. generate_pre.cpp and generate.cpp
3. Depending on what exactly you mean:
the whole software as it is now with all it's constraints, bugfixes, features ...? a few years

Thank you Volker.  it's really an awesome work!

[xing]

Hello, Xingxing,

Thank you for the appreciation!

In addition to what Volker said:

1. Yes, it stops. I place the activities in order. Each activity is placed in an empty slot or displaces other activities. Say it is placed. Then it must respect the constraints with 100%. If there is a constraint with say 95%, in 95% of cases it must respect it, or in 5% of cases it can break the constraint and still be placed correctly.

2. In generate.cpp there is the current main part of the algorithm. We have in FET 4.2.8 (latest FET-4) a genetic algorithm, highly NOTrecommendable, and very old (year 2007). I can tell you that the genetic algorithm is very weak, and probably also simulated annealing.

3. I think I found (rediscovered, I think) the good method of placing the activities, the main algorithm, and implemented the main part, in a few days (after trying in vain for 5 years). But correcting and implementing all the constraints and having all discussions and so on took many years of work. The important work is in the "engine" directory, and the really important part in generate.cpp.

Thank you Liviu for the detailed explanation! I will try my best to understand the generate.cpp. Also, thank your advice for the algorithms.
I understand that the constant with 100% means it is a hard constraint and it must be satisfied or the timetable is infeasible. But, as you said "If there is a constraint with say 95%, in 95% of cases it must respect it, or in 5% of cases it can break the constraint and still be placed correctly." I still didn't get the idea how to measure that a constraint with 95% is respected in 95% of cases. Does it mean the violation number of this constraint is 95% of the total violation number?

[Liviu Lalescu]

I still didn't get the idea how to measure that a constraint with 95% is respected in 95% of cases. Does it mean the violation number of this constraint is 95% of the total violation number?

A constraint with 95% weight is skipped with a 5% probability. See the function skipRandom in generate.cpp, its implementation and its use, further down in the code.

[xing]

I still didn't get the idea how to measure that a constraint with 95% is respected in 95% of cases. Does it mean the violation number of this constraint is 95% of the total violation number?

A constraint with 95% weight is skipped with a 5% probability. See the function skipRandom in generate.cpp, its implementation and its use, further down in the code.

Many thanks for your replay!

[xing]

I found there could be hundreds of constraints in the data files provided in the examples folder, such as, every teacher can have the ConstraintTeacherNotAvailibleTimes constaint, so the number of this time constraint will be as same as the number of teachers, also there could be a large number of ConstraintTeacherIntervalMaxDaysPerWeek constaint.
So does all the time constraints been stored in timeConstraintsList (declared in rule.h) and then during the evaluation of the fitness of a timetable, all of these constaint objects are called one by one to calculate its own fitness?

[Liviu Lalescu]

Does all the time constraints been stored in timeConstraintsList (declared in rule.h) and then during the evaluation of the fitness of a timetable, all the all these constaint objects are called one by one to calculate its own fitness?

Yes, indeed. But this is not part of the algorithm, it is only to report the conflicts to the user and check that the timetable is correct in regard to 100% constraints.

Historically, it was part of the algorithm when the algorithm was genetic.

[xing]

Yes, indeed. But this is not part of the algorithm, it is only to report the conflicts to the user and check that the timetable is correct in regard to 100% constraints.

Historically, it was part of the algorithm when the algorithm was genetic.

So the information the current algorithm only needs is just an ordered permutation of all activities? There is no need to calculate the violation of constraints during the construction of timetable?

[Liviu Lalescu]

Yes, indeed. But this is not part of the algorithm, it is only to report the conflicts to the user and check that the timetable is correct in regard to 100% constraints.

Historically, it was part of the algorithm when the algorithm was genetic.

So the information the current algorithm only needs is just an ordered permutation of all activities? There is no need to calculate the violation of constraints during the construction of timetable?

The solution is an array times[0..n_activities-1] and another array rooms[0..n_activities-1]. Each value in times is a number representing a day and an hour, and in rooms is a number representing the room of that activity.

generate.cpp constructs these two arrays in order, starting with the most difficult activities (not starting from 0, but starting from the most difficult activity), and at each addition of a new activity it verifies that the constraints are respected (or skipped, those with <100%).

[xing]

generate.cpp constructs these two arrays in order, starting with the most difficult activities (not starting from 0, but starting from the most difficult activity), and at each addition of a new activity it verifies that the constraints are respected (or skipped, those with <100%).

Thank you very much for the quick replay!
But how to verify that the constraints are respected or not? Which function specifically does it use?
I found the function generate() and randomSwap() in generate.cpp are may be the longest, thus I guess they are the crucial parts in generating the timetable. The generate() I guess is to generate the timetable, according to its name. Would you please explain a little bit more about randomSwap(). Thank you in advance.

[Liviu Lalescu]

But how to verify that the constraints are respected or not? Which function specifically does it use?
I found the function generate() and randomSwap() in generate.cpp are may be the longest, thus I guess they are the crucial parts in generating the timetable. The generate() I guess is to generate the timetable, according to its name. Would you please explain a little bit more about randomSwap(). Thank you in advance.

How the constraints are respected: It is in randomSwap(ai, level). This function tries to place activity ai. If the level is 0, it is trying to place activity ai in a time slot. If all time slots have conflict, FET will see which time slot has lowest conflicts and place there ai and then do randomSwap(a_2, level+1), ... randomSwap(a_n, level+1), where a2..a_n are conflicting with ai at this time slot.

generate(...) is the first called function, it prepares the way for randomSwap.

I will answer more, if you need. Let me know.

[xing]

How the constraints are respected: It is in randomSwap(ai, level). This function tries to place activity ai. If the level is 0, it is trying to place activity ai in a time slot. If all time slots have conflict, FET will see which time slot has lowest conflicts and place there ai and then do randomSwap(a_2, level+1), ... randomSwap(a_n, level+1), where a2..a_n are conflicting with ai at this time slot.

generate(...) is the first called function, it prepares the way for randomSwap.

I will answer more, if you need. Let me know.

What are the criteria in sorting activities? Can you please briefly talk about how the timeslots of those consecutive or same starting time or grouped activities are scheduled? These activities are linked with each other, which means much more situations should be taken into consideration comparing with scheduling a single activity.

[Liviu Lalescu]

What are the criteria in sorting activities?

Activities with few available slots, with long duration, which conflict with many others because of shared students/teachers - please see the function sortActivities(...) in file generate_pre.cpp.

Can you please briefly talk about how the timeslots of those consecutive or same starting time or grouped activities are scheduled? These activities are linked with each other, which means much more situations should be taken into consideration comparing with scheduling a single activity.

These activities are scheduled one after the other in the initial order, in generate_pre.cpp sortActivities(...), and then when placed, the constraints are checking, in generate.cpp (search for instance the text "oksamestartingtime" in all the places it appears).