Very difficult file needing your help

[yush]

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

[Liviu Lalescu]

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.)

[yush]

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%.

[yush]

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.

[yush]

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.

[Liviu Lalescu]

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.

[yush]

Updated FET file

[yush]

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.

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

[Liviu Lalescu]

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.

[Liviu Lalescu]

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?

[yush]

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.

[yush]

I have solution for the +SR.Wed_ file already. I need the -Engfix now.

[Liviu Lalescu]

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).

[yush]

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

[Liviu Lalescu]

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.