I have a very difficult file. A one similar to this one took me over 1000 runs to got just ONE full solution. Then we discovered a mistake in that file, so I have to make some changes. I no longer have access to our school computer lab (I had it running on 20 i5 labtops at 8 threads each for days), I can use some help from the FET community. Please try the attached file and let me know if you managed to get a solution. I have it running on my M2 MacBook for 90 minutes each. It generally get stuck after 20 minutes or so at 9xx/1138. In my previous version that I had one solution, a handful of them got close to 1100. But that's a handful out of 1000s of runs.
Many, many thanks!
EDIT: Please see later post for an updated version of the file
Hello, Yush,
Please let us know: the ONE solution - in how much time was it found? What was the time limit?
I will see your file, but I cannot help you too much, I have a laptop with a not so great processor or cooling solution (it is Ryzen 8 cores). I will see your file, maybe it can be optimized (though I doubt, knowing your FET knowledge).
I will also think of possible algorithm improvements for your file.
Did you find possible things which don't "feel right" with the algorithm?
Why is the file so difficult? How would you do it without FET? (not bragging, just asking, sorry.)
You've just reminded me about the not "feel right" part. I have a few activities max occupy slots constraint in there. My guess is that FET don't place them close to each other in the init order. As a result, they might got difficult toward to end, am I correct. If it is the case, I need to use the manual ordering advance feature on those.
Also, I do find that the max/min day between activities might be too straight. I should change some of the 100% to a lower percentage. In fact, I know for a fact that it could get more placement, or even a solution, faster if turn some of the constraints to 10% (which I do have a bunch of 20.1%.
As for the one that worked, I forgot how long it took. However, it must have finished within 2 hours, because that's the time limit I set on each of the runs. Again, I was running them on some Intel i5 laptop, not the fastest. But with my file, I think it's better to be lucky than fast. It's an one in thousands kind of lucky. However, with faster computers, you can set the time limit to a shorter time and therefore be able to get more runs, and more luck.
This is the one run that made it. This file is completed. You can unlock the time and room to give it a try. This should be an interesting case. As far as I know, it has only one known solution out of over 1000 runs. I was able to get a few runs that got stuck at 90+% completion and manually unlock all the activities that has tag "Yr=1". That's all the activities for year 9 students (we call the year 1,2,3,4 for simplicity). In a couple of cases, I was also able to get it to completion.
It might lend some insight for a more efficient algorithm. In summary of what happen:
- I have about 1145 activities in the file
- Somewhere around 110x covers all the activities except remaining ones for Yr=1
- Only a handful out of 1000s got close (with one that went all the way)
- For those handful, I was able to take the highest result, unlock all the Yr=1 and regenerate
- A couple of them go to the end with this manual unlocking and regenerate method
Another time, I had it all the way to just 2 more activities from Yr=2 and the remaining Yr=1 (again, that's when it is around 110x/1145. I unlock all the Yr=2, let it regenerate. It managed to clear those 2 Yr=2 activities, now I only have the remaining Yr=1. Unlock all Yr=1, regenerate -> solution.
Implication: may be there is a better way to unplace activities that is already placed during generation.
Something like:
- when really stuck
- look for activities that has a certain activity tag matching those that are not placed (my Yr=1)
- unlock/unplace those activities and keep generate
This will require intelligent on the creator to have activity tag to signify connection beyond what the algorithm can calculate. Or may be there is someway to calculate those connection somehow.
You forgot the attachment in your previous reply, #4.
I will think of your points in your reply #4.
In your first post file, you have a "group activities in the initial order" item. Is this on purpose, or you forgot about it?
Indeed, activities occupy max/min time slots from selection constraints do not influence the initial order. You might want to influence that with "group activities in the initial order" items. I will think of this, but my opinion until now was that these constraints should not influence/change the initial order.
Updated FET file
Quote from: Liviu Lalescu on June 21, 2025, 06:45:11 PMYou forgot the attachment in your previous reply, #4.
I will think of your points in your reply #4.
In your first post file, you have a "group activities in the initial order" item. Is this on purpose, or you forgot about it?
Indeed, activities occupy max/min time slots from selection constraints do not influence the initial order. You might want to influence that with "group activities in the initial order" items. I will think of this, but my opinion until now was that these constraints should not influence/change the initial order.
Sorry, forgot to attach the file. The "group activities in the initial order" item is on purpose.
*** See later post for updated file Regis***+SR.Wed***.fet
Hello, Yush,
I tried some changes of the initial order, but unsuccessfully (I modified the FET code and recompiled, to put first the years 4,3,2,1,0; after that, 0,4,3,2,1. For 4,3,2,1,0 I got to 1123 / 1137, but the last 15 activities were probably very difficult and the program got stuck in two runs on 8 cores). I will think in the next interval of your problem and maybe try some other things.
I don't believe or like the idea of luck... I prefer to organize things better.
I noticed these aspects in your file; they may not be important for the feasibility of the solution:
- The space constraints have 100%. Maybe you could lower them; your data_and_timetable.fet solution has many broken space constraints.
- You did not remove redundant constraints (probably not important, but might help).
I think you are doing something too constrained - FET should be able to solve the file. Maybe you are using too constrained workarounds. I saw the teachers have a max 1 hour in the afternoon, but students have not available for the same purpose. Also, the same starting time and day, are they all really needed?
Are you working on the -engfix file? You are already getting much closer than I am. If you can get to 1123, you are giving me hope. The "0" is mixed year, so, they are very difficult. In other word, doing them last would make it seems too easy in the beginning. May be a 0,4,3,2,1 would be a better order.
The 100% room constraints are for the fact that we only have so many rooms in the school. I don't think I can do any less as far as room constraints go.
Oh, I just realized that I uploaded the wrong file again. The one I uploaded is modifided with many extra contraint. The one here is the true one that has barebone constraints and managed to complete a full solution.
I have solution for the +SR.Wed_ file already. I need the -Engfix now.
Yush, I obtained 1132/1137, but I think this is not useful. The remaining 5 activities are ids 441, 442, 479, 480, and 481. I think these are very difficult activities with Yr=0.
If you can compile FET and have a basic C++ knowledge, I could attach the C++ code and tell you how to choose the order of the students years.
I tried moving these 5 activities to the front, and I get only ~844 max placed, with an exception of 848.
If you have spare time and can explain constraints which you used and which might be too strong, I could try to think of alternatives. Your file as it is seems hopeless...
I am trying on the correct file, I hope (eng fix).
The the +Engfix file, one other change is I have made the active max days between activities constraint 100%. It was at a much lower percentage on the one that worked. You can try lowering all the max days constraints, I am trying 50.1 now. (the .1 to make filtering easier to bulk change) I think the working version has 20.1%.
But that's not the only changes. The main change I have to made is the "fix the english classes" for Y10, hence the name -Engfix. I used the wrong number of splits. I had it at 3+3+3+3+3+3, it is supposed to be 3+3+4+4+4. You can find them with tag:Blk=EN.Y10.G1 & EN.Y10.G2
You know what... I probably made to much alteration from the one that worked to the one that I am trying now. I will go back and keep everything 100% the same except for the english classes and try again.
Attached here is the new file: Almost identical to the one that worked except for the change of splits for activities with activity tag "Blk=EN.Y10.G1" and "Blk=EN.Y10.G2"
***EDIT: sorry again. I found another fix that I must add to the original file. See later post for the updated version for the FET
I think I will be at the computer in the next ~4 hours. However, 1 success in 2-3 days on 20 8-core laptops is also difficult...
Please consider that if you increase the duration of these EN activities, you need to assure the affected constraints are correct - like preferred times, occupy min/max, not available.
Also, you have 1 'group activities in initial order' item in your latest file - is it correct?
Quote from: Liviu Lalescu on June 22, 2025, 04:27:26 PMPlease consider that if you increase the duration of these EN activities, you need to assure the affected constraints are correct - like preferred times, occupy min/max, not available.
Yes. The only affected time constraints are activities with the same time, which G1 and G2 are two groups. I've made sure to change all of them the same way. Also is min days between. I've also thought about this one. So, it should be OK.
See the attached photo for my "FET farm". This might be the most number of simultaneous FET runs you have ever seen!
Quote from: Liviu Lalescu on June 22, 2025, 04:40:57 PMAlso, you have 1 'group activities in initial order' item in your latest file - is it correct?
Yes. It is an activity that need to be at the same time as another group. It is two activities of 4+4 to coincide with another group of 4+4+4+4, so I don't want to fix it using the same start time constraint. I ended up using group of activities having max timeslot to achieve the overlap that I want. Thus, I want to put them together in the initial order.
Oh, wow! :)
I was wondering how much computing I was doing comparing to mining bitcoin! ;D
Quote from: yush on June 22, 2025, 04:45:42 PMQuote from: Liviu Lalescu on June 22, 2025, 04:40:57 PMAlso, you have 1 'group activities in initial order' item in your latest file - is it correct?
Yes. It is an activity that need to be at the same time as another group. It is two activities of 4+4 to coincide with another group of 4+4+4+4, so I don't want to fix it using the same start time constraint. I ended up using group of activities having max timeslot to achieve the overlap that I want. Thus, I want to put them together in the initial order.
I think in this case the 'group activities' might be too strong. But it cannot hurt too much.
The most updated FET file to run.
OK, I will see it.
I think it is useless from me to try your file blindly. I will try to understand it and learn something from this situation. I should also try some other approaches.
So, for the start, I might try to put all the activities of year 1 at the end.
I think FET's default ordering is doing a great job. I am sure if you put all Yr=1 to the end, it will get too difficult. Somehow, letting it run as default. Once it up to 1100+ with just yr=1 left, it often get stuck. Stop it, unlock all yr=1, it might get a result in matters of minutes.
I don't know how FET decide to "back track" when it faces a difficult activities. Does it back track in reverse order of the initial order? If my manual unlocking method has any merit, it means that we might want to back track according to the "connectedness" of the activities. For example, if I am stuck at place order #1074, which is activity id#909, which is a Yr2 chemistry class 2A. Perhaps we should look at all the classes that is "closet" to 2A, meaning ther other 2A classes, and since 2A is often block with other yr=2 classes... in other word, we should unlock all the yr=2 classes that has already been placed and try again... just like my manual process.
Please see: https://lalescu.ro/liviu/fet/doc/en/generation-algorithm-description.html
The essence: FET will displace the conflicting activities for the current activity, which means either same students set, same teacher, or other conflict.
Are the preferred times constraints of the activities in your file needed, or you try to obtain some other features?
Quote from: Liviu Lalescu on June 23, 2025, 07:52:04 AMPlease see: https://lalescu.ro/liviu/fet/doc/en/generation-algorithm-description.html
The essence: FET will displace the conflicting activities for the current activity, which means either same students set, same teacher, or other conflict.
Are the preferred times constraints of the activities in your file needed, or you try to obtain some other features?
What kind of preferred time constraints are you referring to? There should be no preferred starting time constraints.
There are two sections of activities preferred times. See the two attached screenshots (one to this post, the second one in my next post).
And the next screenshot.
They are in theory not necessary. What they do is the following:
- 45 minutes (each "Hour" is actually 15 minutes slots) will always start the day
- 60 minutes will always follow a 45 minutes class in the morning (before 10:30)
- or a 45 minutes following a 45 minutes is also possible
- plus a few variation for activities of 30 minutes or 75 minutes
The result (or desired result) is give the morning more structure so there will never be activities takes up unnecessary space. Imagine a 60 minutes class being placed at 9:00 am, the 15 minutes before or the 30 minutes after became almost unusable. Also, with this structure, there will never be overlapping activities in the morning, making classroom allocation much easier as everything is swappable.
The afternoon (after 12:45 for Y1,2 and after 1:00 pm for yr3,4) is more complicated. But I limit the possible times for activities with different duration to achieve what I described above.
So, in theory, 100% not necessary. I have some debate myself if they are useful, but so far they seems to allow me to get better results.
You can disable all of them to see the effect.
Did you also see my second screenshot? It is a second group of constraints, probably with other purpose.
Actually, I tried last evening to disable the first group, but it seemed still too difficult.
2nd group is also not necessary.
Hello, Yush,
I made some tries to isolate the problematic constraints. It isn't occupy min, it isn't preferred times - the generation kept on being difficult.
The thing I discovered: I tried to make all min days between activities constraints to have the min days option = 1 (via modify multiple option). To my surprise, it made the generation much better. I did not obtain a solution but, as you can see from the attached files, after 20 minutes on the first run (on 8 threads - cores) I had 1101/1136 and on other two threads 1004 and 1005. It might be solvable, but again restarting seems needed, unfortunately.
Is this a feasible approach? To decrease the min days?
I started on 8 threads with random seed 1,0,0, 1,0,0.
Hmm... I might have been just lucky. I am trying again and the results are not so good. Limit 30 minutes, and I got in 2*8 runs only once 1006/1136, and the rest under 1000.
Since we have a 8 days cycle, we want to spread the activities as well as possible. For example, for classes that has only 2, 3, 4 or 5 meetings, we want more days in between, thus all the extra min days constraints. I have already set them to less then 100%, 20.1% or 10.1% or 50.1% in some cases.
Yes, I know for sure that make all min days constraints to be 1 day makes it easier. But we really don't want to see a class with 4 meetings to meet 4 days in a row and now having class in the next 4 days.
I wonder if you can add an advanced "interupt" feature. The user can interupt at any point of the generation. Have everything frozen as a snapshot. Then free to unlock any placed activities. In my case it would work something like this:
- initial run gets stuck at 1082 (which is where I am at now)
- I initiate an "interupt".
- I know by this point I only have a few more yr=2 activities to place
- I place a "temperary unlock/unplace"* (explain more later) on all yr=2 activities
- use group activities in initial order constraint to ensure that all remaining yr=2 activities will be placed ahead of all remaining yr=1 activities
- "uninterupt".
- The generation will pick up from where it left off, but now starts from all the "unplaced" yr=2 activities. However, instead of being randomly put in any available slots, it will be put in a slot that it was last placed, hence the "temperary unplace", it is an unlock with initial preference when placed.
- Since it was unlocked from a placed slot, it is guarantee to be placed if everything is placed in the correct order
- But once placed, the "memory" should be erased
This should mimic my manual process but allow for a more flexible user interaction.
What do you think?
-
Quote from: yush on June 23, 2025, 07:48:38 PMSince we have a 8 days cycle, we want to spread the activities as well as possible. For example, for classes that has only 2, 3, 4 or 5 meetings, we want more days in between, thus all the extra min days constraints. I have already set them to less then 100%, 20.1% or 10.1% or 50.1% in some cases.
Yes, I know for sure that make all min days constraints to be 1 day makes it easier. But we really don't want to see a class with 4 meetings to meet 4 days in a row and now having class in the next 4 days.
I understand. I saw some min days >1 with 100%. But your timetable is too difficult for FET and you might need to reconsider these.
To avoid you 4-4 situation, you might want to use preferred times for subactivities (which is the most efficient for FET), or choose two subactivities and add min 5 days between them.
About your "interrupt" proposal: I need to think of it. But unfortunately it looks quite complicated, and I think not very useful in practice. I tried my best on the current algorithm to avoid these things (I mean to avoid restarting or manual improvements).
Quote from: yush on June 23, 2025, 08:48:21 PMwill be placed ahead of all remaining yr=1 activities
Remaining? Only remaining are yr=2.
Quote from: Liviu Lalescu on June 24, 2025, 01:49:11 PMQuote from: yush on June 23, 2025, 08:48:21 PMwill be placed ahead of all remaining yr=1 activities
Remaining? Only remaining are yr=2.
By the time it get to 1082, only four yr=2 activities are left unplaced. The rest of the unplaced ones are yr=1. Since there are a few yr=1 activities betweens the yr=2 activities, I grouped the yr=2 together to be ahead of the remaining yr=1. Unlocked all the yr=2 and generate again... so far still not able to get all the yr=2 placed.
I hope I understand now.
I propose you to use the official FET without temporarily interrupting. With restarting, which seems needed for your file. But we need to help FET in other ways, with additional 'help' constraints, and you should consider relaxing min days - these two might be related. Otherwise, you don't have 20 8-core computers...
You should consider adding preferred times, with X (red) in all other places than a single day or two. For the activities with the same starting time, you should add for all such activities in the same starting time constraint identical (redundant) preferred times. This might also take care of min days. See also my previous comment, that if you don't want 4 consecutive days you should consider a pair of subactivities and add min days = 4.
The same starting day constraints are needed?
The occupy min constraints are needed? (I think I saw 4 of these.). Maybe these constraints are slowing things, I am not sure.
Then, if the file is easier, we could try it together. Otherwise, as it is now your file, no chance for my computer to finish.
Quote from: Liviu Lalescu on June 24, 2025, 03:20:07 PMYou should consider adding preferred times, with X (red) in all other places than a single day or two.
For prefer start time with more red "x". I can actually do without any of the prefer start time for a certain "duration". Again, that's done to give it more structure, which I think is actually helping. I might be completely wrong. You can remove them and see if it because easier. But remove just the ones that applies to "duration" only.
Quote from: Liviu Lalescu on June 24, 2025, 03:20:07 PMFor the activities with the same starting time, you should add for all such activities in the same starting time constraint identical (redundant) preferred times.
I thought that activities that have "same starting time and day" constraints would be placed together, and it it would be more efficient to have just one of them to have "min day" constraint, since all the other one would be redundant if I add them.
The same starting day constraints are needed.
The occupy min constraint is to ensure that science classes have the same subject have some minimim non-overlapping class cause there is only one lab that they share.
This is how I used min/max day in between to spread the activities currently
- NA=7: minDay=1 100%
- NA=6: minDay=1 100%
- NA=5: minDay=1 100% + A2,A3,A4,A5: minDay=2 10.1%
- NA=4: minDay=1 100% + minDay=2 20.1%
- NA=3: minDay=2 100% + minDay=3 20.1%
- NA=2: minDay=3 100% + minDay=4 20.1% + maxDay=5 10.1%
I used to have the 10.1% and 20.1% at higher percentage. You can try lower them further.
I don't think I want anything less then NA=4 to have too many classes in consecutive days.
But I can probably do NA=5 differently. Would this be easier?
NA=5: minDay=1 100% + A1,A5 minDay=6 50.1%, + A1,A4 minday=4 50.1%
I am not sure what percentage to assign to the non-100% ones. So, I just put 50.1% here. I am afraid a percentage too low, such as 20.1% would allow it to break too often. What do you think?
I decide to try this for NA=4 or 5
- Get the last 3 activities
- A1 & A3 mindays=5 @20%
- A1 & A2 mindays=2 @20%
- A2 & A3 mindays=2 @20%
- let the other activities go anywhere as long as it is not the same day
I think this way allows for more possible arrangement.
Ok. Don t add redundant min days, i was referring to preferred times redundant, which help fet.
The 10% and 20% are very low and easy for the algorithm. I am a bit concerned about min days = 3 or even 2 with 100%.
Could we have min days 3 and 2 with 80%? Also, don't forget to apply the automatic removal of redundant constraints after all the changes.
I think I will have to keep the NA:3+mD:2 and NA:2+mD:3 at 100%. For an 8 days cycle, I really can't have classes that meet only two or three times not spread out. As it is now, the worse case scenarios are:
A1 x A2 x A3 x x x
A1 x x A2 x x x x
Anything worse would not be acceptable.
OK, I see.
What about students not available 3 hours at lunch and teachers max 1 hour from the 4 in the lunch? Could you make these easier? Maybe make for the students max 1 hour from the 4 in the lunch? Maybe allow for teachers 2 hours in the lunch?
The hour is not a real hour. Each hour is really 15 minutes. So, 3 hours = 45 minutes.
Yes, I was talking about FET hours.
So, these constraints (not available students in lunch and teachers work max 1/4 hours at lunch) are not possible to make easier?
I already asked, but I ask you again: if there was no FET, how would they do such a difficult timetable. I am not bragging at all, I am just curious and want to find out possible improvements in the FET file to make it faster.
Yush, I just got an idea: the constraints min days with 100% should be redundant. I mean, if you have A1,A2,A3 same starting time respectively with B1,B2,B3, and you added only min days 100% between As, please add the same min days 100% for Bs. Don't add redundant (in fact, remove them with the automatic function of FET) for min days <100%.
Please let me know.
Got one working! Have to do some manual work:
- It got all the way to 1083/1137
- It has 4 remaining yr=2 activities
- I lock all time, unlock all yr=2, use advanced group activities order to move the yr=2 ahead of all yr=1
- At first it didn't work. Then I moved the the last 4 to earlier in the order
- Then it got to 1090, which means all the yr=2 are done
- lock all, unlock yr=1, try again -> solution!!!
I am happy for you! :) Congratulations!
The thing is that you know better your file than everybody else.
Thinking of your tricks, maybe adding redundant like in my previous post would be a possibility.
I haven't add the redundants in my file that worked. But I am going to keep working to improve it. Let me confirm what you are suggesting:
If I have several groups of activities that happens at the same time (I call them a block), I should have identical minday/maxday constraints for all the activities set in that block? These redundant constraints will help FET to run faster?
Am I right? If so, can you tell me a little more about why it would help? Given that activities with same starting time constraints will be placed together, I can't see why it would help. Or, am I getting it wrong?
Yes, add redundant min and max (I forgot about max) if they are 100%.
Yes, they will be placed together in the initial order. But, this does not make sure they are immediately near. Also, when they are allocated and deallocated many seconds later, they will not be again together.
Example:
A1,A2,A3, min 2 days 100%
B1,B2,B3, same time respectively as A1,A2,A3.
FET might put in the initial order B1,B2,A1,A2,B3,A3 or even B1,B2,B3,A1,A2,A3, if B1, B2, and B3 have the same conflicting factor.
Or, the current placement: Bs and As placed, trying with C1, displaces As and Bs, but As will be say 20 activities after Bs, if FET displaces say 30 activities.
I think you took care too much of not having redundant constraints and fell into another trap... hmm... the other extremity of problems.
Yes. I did most of the min/max day by script, ensuring that I am not creating redundant constraints. I will now write another script to put them back on and try again. It's bed time for me now, will let you know of the result tomorrow! I am running more runs tongiht, so I will have more data to compare tomorrow.
In addition:
A1,A2,A3, min days 2 100%.
B1,B2,B3
C1,C2,C3
D1,D2,D3
same starting time respectively.
It might be that As are last!
Good night! Have a deserved refreshing rest!
Running a new version with the extra min/max days constraints added to all activities that has the same starting time. Seems to be slower, not sure it will go further. Only time will tell. However, I am just thinking if this is true:
If one of the mindays constraint is at 20%, wouldn't have 5 duplicates of the same makes it less likely for FET to break that constraint?
Hmm... I hoped better.
Yes, of course. The new resulting constraint will be (6 times): 1-(1-0.2)^6=0.737856=73.7856%.
In your 2010 case, you had 3 or more 95%, and the resultant is nearly impossible to break, that's why you had to remove redundant constraints.