Cannot recompute schedule when locking time/space

[math]

Hi!
I have a weird problem here with FET that is reproducable with the currentmost version (6.7.2) of FET. I configured a relatively small timetable with only 23 activities which succeeds to compute after some minutes of compute time.
Then I selected "Timetable -> Advanced lock/unlock -> Lock all activities of current timetable" for locking all assignments of starting time and rooms to the activities.
Now the weird part is happening. I expected that the schedule now can be recomputed in an instant, since all time/space assignments are locked (at least this is my experience). But instead FET is displaying an error message saying that the current timetable cannot be computed.
If I remove the time/space locks of all activities, the schedule becomes computable again (after some minutes of runtime).

In my eyes this behavior is a little bit surprising. Shouldn't a schedule be computable if all activities are locked directly after a successful generation?

Best, Matthias

[Liviu Lalescu]

Hello, Matthias!

Thank you for the report!

I think I know where it comes from and I was hoping this will not show in the real life. Unfortunately it might be a feature and not a bug and remain like this in the future.

First of all, please send me both your input .fet files (here, archived, or to fet4 att lalescu.ro).

I think you have 2 impossible constraints with 99.9999%. Let me explain: in the fixed timetable, FET tries to put an affected activity in the fixed slot 400,000 times (this is a FET constant, chosen by compromise), each time trying to break the constraint. It will break the constraint in 0.0001% of cases on average. So again on average FET needs to try at level 0 a number of 1/0.000001=1,000,000 times. So, in some more cases it will fail and in some few cases it will succeed (you can try to generate multiple and check that indeed in some cases it will succeed).

I really don't know what to do for sure. I think keeping the current behavior is the best. Increasing that 400,000 1000 times (to care even for weights like 99.999999%, which is the maximum precision in FET) would be not good, because the program will seem to freeze for some really impossible timetables. Increasing this value maybe 10 times, so that it will solve your file, might not be too beneficial also.

The temporary solution is to decrease the weight from 99.9999% to 99.99%. This is also a very strong constraint. Or on the locked file you can disable these two impossible constraints.

Please send me both your files (unlocked and locked), I am very interested. And I'll think about it. Maybe it would be good to add your bug report in the TODO, what do you think?

More precise calculations: since FET needs to break a 99.9999% constraint and is trying 400,000 times, the probability to fail the generation is 0.999999^400,000~=0.67. So the probability to succeed the generation (breaking the constraint in at most 400,000 tries) is ~=0.33, or 33%.

[math]

Hi Liviu!
Thanks for replying to my posting. I just mailed the fet input file to the specified email address. In this file all activities are locked so that the schedule cannot be computed. If you unlock all activities and wait for some minutes, the schedule will be generated successfully.
You guessed correctly: I have some constraints with 99.9999% significance. I will change them to 99.99% and check if the problem still occurs.
Regarding the underlying problem:
If time and space is locked for all activities of a schedule, this means that the user wants to have the schedule in exactly this way. This means that there is nothing to compute for FET, but just to check the schedule against the specified constraints.
But since all activities have been locked for space and time, this is just a validation and not a computation. So can't all constraints with less than 100% significance simply be left out of consideration in this situation?
Best, Matthias

[Liviu Lalescu]

Dear Matthias,

Thank you for your file! Yes, exactly as I imagined. If you try more times on your original locked file, it will generate, in the end. And if you go to 99.99% for all constraints, the time to generate the unlocked file will be much shorter and the results will be the same (those pesky two impossible constraints barrier - but not always the same two constraints or two activities).

You are right. A locked file/timetable should not be checked, theoretically. Unfortunately, when Volker came with the idea of locked activities, we used constraints activity preferred starting time constraints activity preferred room. We don't have a global parameter "This timetable is fixed and constraints with weight strictly <100% should be ignored".

Maybe such a global parameter would be a solution? But there are many problems with it, such as users locking partially generated timetables, or adding activities after locking a timetable, or... .

I'll think about it and add this problem in the TODO.

[math]

Hi Liviu!
From my point of view it was a great idea to add the concept of time/space locking. In fact I always lock all activities at the end of the planning process to make the generated schedule reproducable. Again thanks a lot for developing such a planning power pack.

But isn't it fairly easy to dynamically check wether a schedule has been locked? In my naive unterstanding you just have to use the routine that is invoked when "Timetable -> Advanced Lock/Unlock" is selected. There you check all the activities and add/remove locks where required.
If this check indicates that no locks have to be added, this means that all activities are locked in time and space. And in such a situation all weighted contraints may be ignored.

Surely this does not help in the case of partially locked timetables and I have no idea how to solve the problem there. But at least it would help in the case of entirely locked timetables...

Best, Matthias

[Liviu Lalescu]

Hello, Matthias,

I am thinking of this problem and I think I know how to solve it: increase the checking count to 2e9 (2 billions). Unfortunately, I found a locking bug when you generate multiple on your file and I am working very hard on it for the last couple of days without success. I will let you know.

It is not nice to mark a file as "locked timetable", since the user might lock all days in turn - it is not a FET-style approach.

[Liviu Lalescu]

Dear Matthias,

I released a new version. Thank you for the bugs reported! I reached a compromise solution, and your locked files are solvable (not instantly, unfortunately).

[math]

Hi Liviu!
Thanks for your great support!
Best, Matthias