Assigning multiple small rooms or one large room

[math]

Hi Liviu!

Yes, I'm working in a computer science department, so bipartite graphs are not entirely unknown to me, but I'm definitely no theory guy - sorry.

After compiling there was only just a single app executable, so I did not check if I'm able to execute it from the command line. I'll try it this evening.

Sorry about confusion caused by my "3 of 5" statement. You're completely right, we can solve all possible situations with the sets you implemented.

[Liviu Lalescu]

Hello again, math,

After compiling there was only just a single app executable, so I did not check if I'm able to execute it from the command line. I'll try it this evening.

Not really something interesting to see - I wrote the output of the program in my post. If you want, you can try to change the source - hopcroftkarp.cpp, to see how it behaves for other graphs, but it is quite difficult, as I did a bit of "axe work" (in Romanian, this means "incorrectly finished", "rough").

Sorry about confusion caused by my "3 of 5" statement. You're completely right, we can solve all possible situations with the sets you implemented.

No problem. And there were also your ideas!

[Liviu Lalescu]

I began working. I included the Hopcroft-Karp code in generate.cpp. There is much more to do, but I began and I hope it will work in the end.

If you want to see my work, you can download and diff generate.cpp (custom VS official) from https://lalescu.ro/liviu/Backup-fet/math/

[Liviu Lalescu]

Work in progress. I hope I have the generate.cpp code good, and this was for me the most uncertain and difficult looking part. But I don't know how it will work in practice.

Now remains also a lot to do in other parts.

I have put a new version, on the same link: https://lalescu.ro/liviu/Backup-fet/math/

[math]

Hi Liviu!

I'm really curious to testdrive the new FET. :-)

I'm able to compile fet-5.39.0, but fet-5.39.1-snapshot-math-snapshot-15-sep-2019-20_48 fails with:
engine/solution.cpp:85:23: error: use of undeclared identifier 'gt'
        realRoomsList.resize(gt.rules.nInternalActivities);

If I relace that line with
        realRoomsList.resize(r.nInternalActivities);
compilation continues, but stops again shortly after with:
engine/generate.cpp:2427:40: error: no member named 'isVirtual' in 'Room'
                                if(gt.rules.internalRoomsList[rm]->isVirtual){
                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  ^
engine/generate.cpp:2428:69: error: no member named 'rrsl' in 'Room'
                                        const QList<QList<int> >& rrsl=gt.rules.internalRoomsList[rm]->rrsl; //real rooms sets list.
                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  ^
engine/generate.cpp:2504:26: error: no member named 'count' in 'Matrix1D<QList<int> >'
                                                for(int i=0; i<adj.count(); i++)
                                                               ~~~ ^
engine/generate.cpp:2859:35: error: member reference type 'Room *' is a pointer; did you mean to use '->'?
                if(gt.rules.internalRoomsList.isVirtual==false){
...
(and many more)

So I'm wondering if you uploaded the currentmost sources and if they compile at your side.

[math]

Sorry, I did not read your posting thouroughly enough. You just encouraged me to take a look at the diffs, you did not mention anything like compiling. The diff is really impressive, looks like a lot of hard work. I'll try to dig into it, but it's really complex imho.

Thanks a lot for your excellent support!

[Liviu Lalescu]

Oh, no problem! The sources do not compile, of course, I only did the generate.cpp (and a bit of other files). And there must also be many small mistakes, like the one you discovered in solution.cpp.

I only wanted to keep you informed of the progress.

I am not sure about the randomization when searching for a solution with maximum bipartite matching. Say we have a very simple possibility, S1 (R1, R2). R1 is occupied at the time t, but R2 not. I choose randomly R1. Then I have a conflict more to fix. If I chose R2 I had no conflicts in this part, but each time I would have chosen R2 in the algorithm if no randomization.

I just hope that practically the randomization will work.

[Liviu Lalescu]

OK, I have good news and not so good news.

The not so good news is not critical. The new code runs approximately 10% slower even if you are not using virtual rooms. For the German example secondary-school-1/using_subactivities_constraints.fet, starting with the random seed X=123, Y=123, instead of 28 seconds it finishes in 31 seconds.

The good news is that I finished the code for the internal parts of the code (generating, saving a file, opening a file, showing a virtual room in the interface), and the new FET custom version compiles correctly. The only unfinished part is the dialog where to define the sets for the rooms, and add/remove/edit sets, add/remove real rooms in the sets.

Also good news is that it seems to run correctly for the above German example.

Short or longer break now, then I am not sure how I will continue. I am very interested to see how the algorithm behaves, so I might modify by hand a .fet file, adding virtual rooms, and generating it. Or I will design the interface to create/modify virtual rooms.

Do you have suggestions on how the dialog for virtual rooms should look like? Maybe a check box, "Virtual", and when you select it you get into an advanced dialog.

Same link: https://lalescu.ro/liviu/Backup-fet/math/

[math]

Congratulations! That's really excellent. I just compiled the snapshot successfully, but I cannot confirm the performace drop you mentioned. I started both 5.39.0 and the snapshot 10 times each and performance was between
real   0m27.542s
user   0m27.419s
sys   0m0.065s
and
real   0m55.074s
user   0m54.868s
sys   0m0.120s
for 5.39.0

and between
real   0m28.876s
user   0m28.794s
sys   0m0.054s
and
real   0m44.630s
user   0m44.537s
sys   0m0.072s
for the snapshot.

I admit that ten tests isn't really a huge number, but at the moment it does not appear to be a general 10 percent performance drop.

Regarding the room dialog, I will think about it.

Again, thank a lot for all your effort!

[Liviu Lalescu]

Thank you for your tests. However, to test more exactly, you need to start with the same file and the same random seed.

Start FET 5.39.0 official, set random seed X=1, Y=1 (or any other values you prefer), and generate n timetables (n can be 1, if the time is long).

Then start FET 5.39.1-snapshot-math, set the same random seed (X=1, Y=1, or the same values as above), and generate n timetables.

The random seed at the end of the generation should be identical in 5.39.0 and in 5.39.1-snapshot-math.

That would be a very precise comparison. Please let me know (but don't try too hard, I might have some tricks to make the new code faster).

[math]

Thanks for the hint, good to know.

Regarding that dialog: I would still prefer a separate dialog for defining virtual rooms, just like I outlined in posting #13. Do you rather prefer a single dialog for both virtual and regular rooms?

[Liviu Lalescu]

I tried to make it faster, but I could not. It seems that it is ~10% slower even for files without rooms, which is acceptable if for any file it is ~10% slower. Maybe (math and Volker) can do some tests on more files. More than ~10% might be too much and I need to check the code and try harder to optimize it.

Maybe: have the dialog of rooms. There are two buttons: "Make this room real" (it loses all the sets of real rooms) and "Make this room virtual", and this last button opens a dialog to define the sets of real rooms.

[Liviu Lalescu]

I began working on the visual department of the rooms' dialog. I think I will follow your suggestions - editDialog.png. I will post updates. It is easy, but tedious.

I used a minor trick to make the new code a bit faster, now instead of 28 seconds with 5.39.0 I get 30 seconds (instead of 31).

[math]

I'm SO curious... :-)

As you recommended, I specified seed parameters when testing performance:
./fet-cl --inputfile=examples/Germany/secondary-school-1/using_subactivities_constraints/German_subact_constr.fet --randomseedx=1 --randomseedy=1

But still I cannot see huge differences between these two versions (currently using a cluster with E3-1230 CPUs running at 3,3GHz): 5.39.0 takes 30secs while 5.39.1 is taking 31secs.

[Liviu Lalescu]

It is so easy in principle, but so difficult for me, since I have no experience in interface design. So it will take a while.

Then, I might find important bugs in the generation when using virtual rooms.

So please be patient.

It is good that it seems that the speed slowdown is not so big. You can test also for other files, if you want.