FET Forum

In some of our lectures the number of attending students exceeds the capacity of our largest rooms. By removing the walls between three of our rooms, we can create one huge lecture hall, which then has sufficient capacity. In FET I'm modeling it in the following way: first I create a regular activity which is assigned to the first of these rooms. Then I create two "dummy" activities, which have no students or teachers, but which are assigned to the second and third room. Finally I add a time constraint, that these three activities have to have the same starting day and time.

This is working perfectly fine. Until now.

Now the situation has changed because a new lecture hall has been inaugurated in our building. This new lecture hall has sufficient capacity even for the largest lectures. However I'm not quite sure how to model large lectures in FET now. Huge lectures can no EITHER use the new lecture hall OR the three old lecture rooms (as we did it until now).

Is there a way to define some kind of "virtual room" consisting of these three lecture rooms, then assigning these to two rooms in "room -> activities -> an activity has a set of preferred rooms" to the activity.

Do you mean: "can now EITHER use"?

I think: create two dummy rooms R1' and R2'. Together with R1, R2, and R3, and R which is the large room, it should work, if I am not mistaking, but you might need to switch manually the rooms real<->dummy in the final timetable.

Hi!

Thanks for your response, but I'm not quite clear if I understood you correctly.

Up to now we had the rooms R100A, R100B and R100C, each having a capacity for 100 students. It is possible to remove the walls between these three rooms, so that the resulting room can be used for lectures for up to 300 students. For planning such a lecture, I added a regular activity A1 having the constraint "acitivity has a preferred room" R100A. Moreover I added two dummy activities A2 and A3. These two dummy activities do not have a teacher or student group specified, but I specified that A2 shall be in R100B and A3 shall be in R100C (again using the constraint "activity has a preferred room"). I also specified that A1, A2 and A3 shall have the same starting day and time ("time -> activities -> a set of activities has the same starting time").

During schedule generation, the large lecture was planned in a slot where all three rooms R100A, R100B and R100C are available.

Now we have the new room R350, having a capacity for 350 students.

Large lectures can now take place in the new R350 as well as in the connected rooms R100A, R100B, R100C. Using the old connected rooms for large lectures is absolutely fine, so we don't want to use R350 only. We are rather very much focusing on having as much flexibily as possible.

But the question is how to model it in FET.

If I'm doing it the old way, I would specify that A1 may take place in R100A or R350, leaving A2 and A3 as dummies for occupying R100B and R100C as above. This would surely work, but it has the disadvantage that R100B and R100C are always blocked for the lecture, even if it takes place in R350. Since we are very short on rooms, this is a real problem, because R100B and R100C could not be used for other activities during that time (since they are blocked for the lecture, even though the lecture only takes place in the new R350).

I would like to model it in a way that EITHER R350 is allocated for the lecture OR R100A, R100B and R100C.

I'm not quite sure what you mean with dummy rooms. Do you mean "virtual" rooms that are not actually existing? Let's name those rooms "dummy room 1" (DR1) and DR2.
Do you suggest that A1 has preferred rooms R100A and R350, A2 has preferred rooms R100B and DR1, and A3 has preferred rooms R100C and DR2?
I don't think that this would work because FET could generate a result that assigns R100A to A1, DR1 to A2 and DR2 to A3. This is no valid assignment since we need all three rooms R100A, R100B and R100C for having sufficient capacity for the lecture.

From my point of view I need a way to assign more than one room to a single activity. This could work the following way:

In "Data -> Space" there could be a third entry "Virtual Rooms" (beside the existing entries "Buildings" and "Rooms").
In that dialog it could be possible to specify "virtual rooms" by specifying a name and selecting one or more actually existing rooms (that have been entered in "data -> space -> rooms").
In my example I would create a virtual room "VR300", selecting R100A, R100B and R100C as rooms that VR300 exists of.
In all other dialogs of FET, virtual rooms could be treated just like actual rooms. For instance in the constraint "activity has a set of preferred rooms" the list of rooms could be a mix of virtual and regular rooms.
The crucial difference is in the schedule generation. Until now there is a direct relationship between activity and room: for each activity there is at most one room that is assigned to it. With virtual rooms this changes in a way that multiple rooms are assigned to an activity (i.e. all rooms that the virtual room consists of).

Having such functionality I would specify for A1 "activity has a set of preferred rooms": VR300 and R350. If FET schedules A1 to R350, only R350 is allocated. If A2 is scheduled to VR300, the rooms R100A, R100B and R100C are allocated. 


But maybe I'm wrong and it does not need any enhancements to FET. Could you tell me again what you mean with virtual rooms?

Hello,

Sorry, I think I was wrong.

Your suggestion is very good, adding a virtual room to represent 3 real rooms.

I think you cannot represent your situation in FET official as it is now.

In the TODO item #114 (in which many users suggest adding more rooms for an activity) I added your suggestion as well: "Also suggested by math, on the forum: https://lalescu.ro/liviu/fet/forum/index.php?topic=4249.0 (the essence is that he proposes virtual rooms. A virtual room consists of more real rooms and an activity may be allocated to a real room or to a virtual room)."     Please let me know if this is correct or you want other wording here.

As a current workaround i guess you should try to choose the room manualy.

So choose all activities that you used the 3 old rooms and do it like always (with the 2 dummy activity and same starting times constraint).
Use the new large room "normal", so without dummy activities.

The difficult part is choosing manualy. In best case you check if there is one teacher or student many times in a large room. You should place his activitities always in the same large room (so in 3 old rooms OR the single large new room; but not both) to avoid possible conflicts and simplify the data. So it with an other teacher or students that visit large rooms 2nd most times; just into the other room. I am note sure about the other activities. Place them randomly in a room if you can't see a good rule.

@liviu: thanks a lot for adding it to the TODO. Wording is perfect, however I think that the concept of virtual rooms is more powerful than just adding multiple rooms to an activity (which can be realized with the current version of FET by adding dummy activities).

@volker: thanks for the suggestions. That's my current workaround, but it's quite time consuming.

So, math, do you suggest I should add a new TODO item alone for your topic here? If that is true, could you suggest the text?

math, I thought about it and your idea is excellent, both for the result and for the ease of implementation. Congratulations! No other users suggesting this, nor me or Volker, thought of this, over a long time in which I thought adding more rooms for an activity is very complicated (I refer to virtual rooms, each one containing more real rooms).

I think of adding a check box for each room, "Virtual", and each virtual room must contain at least 2 non-virtual (real) rooms (so that the user will know what virtual rooms mean). Can two virtual rooms contain common real rooms?

It seems that the implementation will work easy this way. Each activity will be placed in a single room (real or virtual) and if an activity is in a virtual room all the contained real rooms will be empty at that moment. Also, if an activity is in a real room, all virtual rooms containing this real room must be empty at that moment (is this correct?)

Please let me know, if I will be able to do this, will you help me with advice and intensive testing?

Other users, please let us know your opinion!

Quote from: Liviu Lalescu on September 01, 2019, 12:46:47 PMEach activity will be placed in a single room (real or virtual) and if an activity is in a virtual room all the contained real rooms will be empty at that moment. Also, if an activity is in a real room, all virtual rooms containing this real room must be empty at that moment (is this correct?)

I think it is depeing on the reason why you need several rooms.
The variant looks perfect for data sets similar to maths data set. Also the printed timetables will look fine.

I am a bit thinking about other data sets. For example i also need sometimes 2 or 3 rooms. But only the 1st room is important, the second one can be (nearly) randomly.
In my situation such a new vitual room constraint will be much to strict/difficult. So at my school there is a constraint useful that automaticly add a second (and maybe also third) dummy activity with same starting time constraint. But the printed tables won't look perfect.
hmmm... I think it is not critical, since all the past years i only added a single room and after the timetable was generated i just was always able to choose easily an other 2nd or 3rd room manualy by using TiTiTo.

So i think overall the suggestion is fine.
i am think about a few maybe needed warings. So it should check if the vitual rooms has got the same building as the included real rooms. (Or is there a trick/feature why that might be usefull if they are different?)

@liviu: Thanks a lot that you also like the concept of virtual rooms.

As I outlined in my post, I would clearly differentiate between real and virtual rooms, so I would NOT add a "virtual room" checkbox, but create a separate dialog for defining virtual rooms only. I'm thinking of something like "Time -> Activities -> A set of activities has the same starting time -> Modify". Here you have a list of all activities on the left and a list of selected activities on the right.

Something similar could be used when entering virtual rooms. On the left hand side there could be a list of all rooms, on the right hand side a list of selected rooms.

I really DON'T like your idea that a virtual room has to encompass at least two real rooms. It the same thing like "Space -> Activities -> An activity has a preferred room / An activity has a set of preferred rooms". Why does a "set" have to consist of two or more items? I would really like to see those two constraints to one.

So I would not force users to specify a minimum of two rooms for a virtual room, because the concept also works with a single real room. As a matter of fact, there is no point in defining a virtual room containing only one room, but that should be something that the user decides. Maybe it's a situation where a user already defined a virtual room that encompasses two real rooms. He defined that virtual room as preferred room for numerous activities. Now he has to remove his second room from his configuration (e.g. because the room has been assigned to a different department). If FET forces the user to specify a minimum of two rooms, the user would have to remove the virtual room, then changing all preferred room configuration for affected activities. Most likely, the user will try to circumvent the limitation, e.g. by changing the availability of the room to "unavailable" for all slots instead removing it.

From the functional perspective it's perfectly ok to specify a virtual room with only one real room.

Actually, I think that it would be even possible to allow virtual rooms to not only encompass real rooms but also other virtual rooms. When generating a new schedule, the algorithm has to follow the list from virtual room to virtual room, until all real rooms have been determined. It is only required to detect cycles.

If you need me for testing, just let me know.  :)

@volker: I did not mean that adding virtual rooms would make the multiple-rooms-per-activity todo useless. Actually I have the same problem that you described. So that feature would be highly appreciated. I only commented liviu's comment to subsume virtual rooms under this todo. I just think that the virtual rooms feature is not the same than the multiroom-feature.

@math:

1) The denying of a virtual room to have only a real room was only a thought from me so as to not confuse the users. It would have been only a condition on starting the generation, not something hard-coded which is difficult to change afterwards.

2) My head (and heart  :)  ) hurts thinking of virtual rooms containing virtual rooms. Why? :)

3) (also @Volker) Hmm, Volker's problem and your multiple rooms for an activity problem are so difficult. I was hoping virtual rooms will solve this. I have an idea: a virtual room has say 5 real rooms and needs to occupy say 3 real rooms out of these. Is this OK for every situation? (but I admit this sounds difficult and I am not sure I can do it efficiently).

4) In my imagination, real and virtual rooms are similar, just you need to click something and the options for a virtual room appear. But this is just interface, this is not the problem.

@Volker: I prefer that each real or virtual room has any building. But this is easily modifiable.

Hi Liviu!

1) I don't think that it will confuse any user if you allow selecting a single real room for a virtual room. But at the bottom line, this is your decision.

2) I did not mean that "virtual room inheritance" should be implemented in the first shot. Maybe you put it to the todo list for some future version of FET.

3) I really don't like your idea, because it taints the concept of a virtual room. A virtual room should just be a collection of rooms. Its prime beauty is the possibility of assigning different room sets to an activity. Clearly it could be used as a substitution for the multiroom-feature, I don't like it. Primarily because it does not scale. Imagine that you have a large number of multiroom activities, then a separate virtual room for each of these activities would be necessary. Don't you think that this might get confusing?

5) I don't have any experience in the building feature of FET. In our university the building is coded in the room number (i.e. by looking at the room number, you directly know which building on which campus is meant). But I have a new idea about a scenario how the virtual room feature might be used. Other departments in our university provide lectures on multiple campuses simultaneously. Here, the lecture is held in a lecture room which is equipped with a video conferencing system. The lecture is then streamed to lecture rooms on other campuses, where other students are attending. This means that a virtual room here consists of rooms in different buildings (on other campuses). I even think that this is a scenario that would benefit from virtual room inheritance.  ;)

1) It is also the opinion of the users which counts, and your arguments are good.

3) A large number of multiple room activities. Each will get a preferred room: virtual room VR having in total say 10 real rooms, and each virtual room needs to occupy say 3 rooms out of these at a certain time slot. Otherwise, how do you suggest creating multiple room-ed activities? (I mean creating the constraints, not the internal generation algorithm, which looks difficult to me now).

Hi Liviu!

I thought a little bit about the multiroom feature and created two fake screenshots to illustrate my ideas.

1)
The virtual room feature should be a fixed mapping of one virtual room name to a number of real (and virtual) room names. No "3 of 5 rooms" option, just a fixed mapping. I explained my idea of the mapping algorithm in some posting above.

2)
For the multiroom feature the menu of "Space -> activities" is changed. The first and second entry is deleted and replaced with the entry "An activity has sets of preferred rooms"

3)
In the beginning, there are no room preferences for any activity, so the list "constraints" is empty. For adding a constraint, the "add" button has to be pressed, which automatically opens the edit dialog (second fake screenshot).
In my example, there are already some room preferences defined. Therefore, there are constraints for five activities listed in that window.
I think it's a good idea to show additional information than just "Activity 1", "Activity 2", etc. In the current "Constraints Activity Preferred Room" there is a information field on the top right side ("Current Constraint"). Maybe something like this.
For filtering the list of activities some filters can be applied by using the combo boxes, just like it is already possible in other dialogs of FET.

4)
If a new constraint has been created (by clicking on the "add" button) or an existing constraint has been selected and the "modify" button is clicked, the Edit dialog (depicted in OverviewDialog.png) shows up.

5)
In that edit dialog the leftmost list contains the sets of preferred rooms that have been defined for that activity. In the beginning, there are no room preferences defined for that activity, so the list is empty. For creating a new set, the "Add" button has to be pressed.
By clicking the add button, a new set is generated, where the sets are automatically named "set 1", "set 2", "set 3", etc. The newly generated set is automatically selected (i.e. its entry in the list is selected and appears with blue background color).

6)
For the selected set, the middle list shows the preferred rooms, where regular entries are real rooms and italic entries are virtual rooms. If it is not possible to change the font of list entries, the name of the room could be extended with a "(R)" (real room) or "V" (virtual room).
The list on the right side shows all other rooms that are available in the system.
If an entry in the middle list is double clicked or the ">" button is pressed, the room is deleted in the middle list and added to the right list.
If an entry in the right list is double clicked or the "<" button is pressed, the room is deleted from the right list and added to the middle list.

7)
In the present version of FET, each activity can only have one room. This means, that for each activity there can be only just one set of preferred rooms. Hence, if an old configuration file is opened with a future FET version, this Edit dialog would only just show one set in the left list.
So this modification is backward compatible with old FET configuration files.

8)
In your example you asked me how I would configure an activity that needs 3 of 5 rooms. It would work that I first add "set 1", then clicking "room 1", "room 2", ..., "room 5" from the right list, so that these rooms appear in the middle list.
Then I create a second set. And again, I select the rooms from the right list, so that also "set 2" has
five preferred rooms.
And then I repeat this a third time.
At the end, there are three sets defined, each having preferred rooms "room 1", "room 2", ..., "room 5".

9)
Since I never took a look at the schedule algorithm, this point is pure guessing:
At the moment there has to be some code that tries to allocate one room of the set of preferred rooms of an activity. Maybe its a function that gets a reference to the set of preferred rooms as argument.
This function is now executed multiple times, i.e. one time for each defined set.

I'm sure that item 9) is much more complicated, but I think that you have to solve very similar problems if you add a "3 of 5" property to the virtual room feature.

Anyway, it's just an idea. Hope it helps. If you think that implementing your idea of a virtual room feature for realizing the multiroom feature is much easier and less error prone, please go ahead.

Hello, math,

Thank you for your work! It contains another excellent suggestion, Set1..Set3 of choices for an activity which should take place in 3 rooms. This should solve also Volker's problem, when he says the first room must be fixed and the other two do not matter.

However, I need to keep the fact that each FET activity goes into a single room, real or virtual. Otherwise would be a titanic task. And you reminded me that also nearly all the space constraints would change.

So I propose you that each virtual room has n sets of real rooms, and in the allocation the algorithm will choose a single real room from each set. I am not quite sure if this is acceptably difficult and feasible. I need to think, but maybe the final decision will be made practically.

I think I can try for the beginning to make this as a custom version for you and Volker and, after many tests, this will find its way in the official FET if successful. This is because if I add such a feature in FET and it will not work, it will be a disaster both for impossible files and for the fact that if I remove this feature afterwards the users will lose virtual rooms data and space constraints.

Please let me know if this is acceptable for you.

Ok, let's do it this way.

If you have something to test, just let me know. Really looking forward to it.

I need to think of it, then try something practically. I will keep you informed of the progress. I cannot promise anything, though.

Today's report:

I did many other things, but I had some time to check the code and think about this topic's problem.

When I put an activity into a virtual room, the time slot I need to check is fixed. So I need to compute each time the real rooms which remain available in each set of this virtual room (because there may be different room not available constraints for the real rooms). There will remain say S1 (R1, R2, R3, R4), S2 (R1, R2), and S3 (R1, R2) for VR1.

I think I need to choose randomly in turn a real room for each set.

This is a tricky thing: say I choose R1 for S1 and R2 for S2. Then I cannot continue with S3.

So I need to sort the sets, in increasing order of the number of real rooms in them. Some thinking and drawing should demonstrate that in this case I can choose any rooms I want in this order of the sets (if the situation is impossible, I cannot choose other rooms anyway). If the sets are included one in another in this order, to be possible to choose the rooms, I need the i^th set to have at least i rooms.

Please correct me if I am wrong. Also suggestions are welcome.

This is what I did today. Things are complicated, but I hope possible.

And I found a counter-example of my method   :-[

A virtual room has 4 sets of real rooms (ordered by increasing number of rooms):

S1 (R1, R2), S2 (R1, R2), S3 (R1, R3, R4), S4 (R1, R2, R3).

or

S1 (R1, R2), S2 (R1, R2), S3 (R3, R4), S4 (R1, R2, R3).

or

S1 (R3, R4), S2 (R1, R2), S3 (R1, R2), S4 (R1, R2, R3).

If in the process I choose R3 first over R4, then S4 remains impossible.

I am now thinking of how to solve this, but it looks ugly.

And even a very simple problematic example:

S1 (R1, R2), S2 (R2, R3), S3 (R1, R3).

If I go in the order S1, S2, and S3, and choose say R1 from S1 and R3 from S2, S3 is impossible. Also, any other order of the sets (say, S3, S1, and S2 or the other 4 cases) may lead to impossible cases.

What about the following:
Before assigning a room, you're computing the number of occurrences of a room in all the given sets (setting number to infinity, if the room is already occupied), then selecting the first room with minimum number of occurrences in the first set.

1) S1 (R1, R2, R3, R4), S2 (R1, R2), and S3 (R1, R2)
1a) #R1=3, #R2=3, #R3=1, #R4=1 -> Selecting R3 of S1
1b) Remaining: S2 (R1, R2), and S3 (R1, R2)
-> #R1=1, #R2=2 -> Select R1 of S1
1c) Remaining: S3 (R1, R2)
-> #R1=inf, #R2=1 -> Select R2

2) S1 (R3, R4), S2 (R1, R2), S3 (R1, R2), S4 (R1, R2, R3).
2a) #R1=2, #R2=3, #R3=2, #R4=1 -> Selecting R4 of S1
2b) Remaining: S2 (R1, R2), S3 (R1, R2), S4 (R1, R2, R3)
-> #R1=3, #R2=3, #R3=1 -> Selecting R3 of S4
2c) Remaining: S2 (R1, R2), S3 (R1, R2)
-> #R1=2, #R2=2 -> Selecting R1 of S2
2d) Selecting R2 of S3

3) S1 (R1, R2), S2 (R1, R2), S3 (R3, R4), S4 (R1, R2, R3).
3a) #R1=3, #R2=3, #R3=2, #R4=1 -> Selecting R4 of S3
3b) S1 (R1, R2), S2 (R1, R2), S4 (R1, R2, R3)
-> #R1=3, #R2=3, #R3=1 -> Selecting R3 of S4
3c) S1 (R1, R2), S2 (R1, R2)
-> #R1=2, #R2=2 -> Selecting R1 of S1
3d) Selecting R2 of S2

4) S1 (R3, R4), S2 (R1, R2), S3 (R1, R2), S4 (R1, R2, R3)
4a) #R1=3, #R2=3, #R3=1, #R4=1 -> Selecting R3 of S4
4b) S1 (R3, R4), S2 (R1, R2), S3 (R1, R2)
-> #R1=2, #R2=2, #R3=inf, #R4=1 -> Selecting R4 of S1
4c) S2 (R1, R2), S3 (R1, R2)
-> #R1=2, #R2=2 -> Selecting R1 of S2
4d) Selecting R2 of S3

5) S1 (R1, R2), S2 (R2, R3), S3 (R1, R3)
5a) #R1=2, #R2=2, #R3=2 -> Selecting  R1 of S1
5b) S2 (R2, R3), S3 (R1, R3)
-> #R1=inf, #R2=1, #R3=2 -> Selecting R2 of S2
5c) S3 (R1, R3)
-> #R1=inf, #R3=1 -> Selecting R3 of S3

I will read thoroughly your message a bit later. But I think there is a misunderstanding: I don't want a fixed choice. I want a random choice out of the possible ones. So in your (1) I want to choose randomly R3 or R4 (50%/50%).

I read your message and indeed, I think it will produce a solution, if it exists. Good idea! And a random solution might be found if we choose randomly the next room from the rooms with the same minimum value.

But I am not sure it will be an "enough random" solution. Please allow me some time to think of some examples.

Minor mistakes: I think in (1b) you should have #R1=2. And in (2a) #R1=3. And in (4a) #R3=2 (changing the whole (4) ).

I am thinking now from which set you need to remove the room (for instance, in (2c) you can choose either S2or S3). If you choose randomly you might obtain a random solution, but we need to check if it might lead to dead-ends.

I found a simple counter-example to your method:

S1 (R1), S2 (R2, R3), S3 (R1, R2, R3).

All rooms appear twice, we choose randomly R1 (from R1, R2, and R3 - 33.(3)% each) and then S3 (from S1 and S3, 50%-50%), so S1 will remain impossible.

Maybe you can argue if the same room with the lowest number of appearances appears in more sets, choose the smallest set. Let me think of that, too (I think this should keep all the sets non-empty, but I am not sure if it leads to "random enough" choices).

For this example, if we do it like in your suggestion to choose the smallest # and like in mine to choose the smallest set:

S1 (R1, R2), S2 (R2, R3, R4).

If we choose R1 from S1 (mandatory, because R1 appears with #1 and S1 is the smallest), we deny the pairs R2 from S1 and R3 or R4 from S2.

It is possible, but not so random.

I am still thinking and making schemes for this.

I think an acceptable solution is to choose the smallest set and a random real room from it, and then update the remaining sets and continue. If there is a dead end, start again the procedure. I think the maximum probability of failure is 1/2 (50%), so if I do say 20 tries the probability of failure is 1/2^20~=1/1,000,000. But I have no clear proof of this.

I am thinking also on other approaches.

Oh, I found the theoretically perfect solution!  :)

Luckily I participated in some programming contests and I was interested in a difficult programming problem: maximum flow/bipartite graph matching.

Draw on the left the rooms (R1, R2, ...) and on the right the sets (S1, S2, ...) (or viceversa). Draw a line from R_i to S_j if the room i is contained in the set j. Now select a maximum set of lines so that each room/set has at most one selected line leaving/entering it. If each set has a selected line, we have a solution. This is a classic problem, solvable in polynomial time, efficiently (Ford-Fulkerson, Edmonds-Karp, and maybe some newer and better algorithms).

Now I need to think of additional problems: select a random maximum bipartite graph matching, and maybe add weights on the lines (representing conflicts if the room is occupied) and find a random maximum bipartite graph matching of minimum cost.

Unfortunately, it is a long time since I did not program a maximum flow/bipartite graph matching program, but I have the internet to remind me.

math, please let me know if you understand and agree with what I wrote.

Later edit 1: I decided to add two graphical examples (attached image).

In example 1, you cannot couple R1 or R2 with S1. In example 2, you cannot couple R3 with S1.

Later edit 2: I think I can use the Hopcroft-Karp algorithm ( https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm ). Its run time is O(|E| sqrt(|V|)). In our case |E| is the total number of rooms, counted with 1 in each appearance in each set (duplicates counted), and |V| is the sum of the number of rooms (only counted once) and the number of sets. A reasonable time. Hmm, but I need to check how to find a random bipartite matching.

Today's report: I implemented the algorithm Hopcroft-Karp from that link from Wikipedia, and I managed a way to make it generate a random maximum bipartite matching. It seems to work, and very fast.

I attach two examples. Two small graphs:

1) The first is S1( R1, R2) and S2 (R2, R3, R4).

It seems to run in about 1 microsecond (1 billion runs in about 1000 seconds).

cnt12==208328089
cnt13==208333858
cnt14==208330083
cnt23==187503007
cnt24==187504963

cnt12+cnt13+cnt14==624992030
cnt23+cnt24==375007970

real   17m53.688s
user   17m53.457s
sys   0m0.012s

cnt12 means R1 from S1 and R2 from S2, etc. I cannot really explain the numbers (20.83% with R1 and 18.75% with R2), but it is good they are acceptably well distributed. Edit: I computed the numbers, they are as they should be (20.8(3)% with R1 and 18.75% with R2).

2) The second is "Example 1" from my drawing above. This one is clear - 25% each:

cnt312==249431
cnt321==250432
cnt412==250220
cnt421==249917

real   0m1.316s
user   0m1.316s
sys   0m0.000s

This one runs a bit slower - 1 million runs in 1.316 seconds.

I attach the code as well, can be compiled with Qt.

So it seems things are OK. I will try to continue in the next interval.

Hi Liviu!

Sorry, I was off the last week. I read your postings but did not have the time to check that algorithm or even test your source.

Treating the problem as bipartite graph using Hopcroft Karp is a brilliant idea. I just downloaded the zip and succeeded compiling it with OSX. Unfortunately the resulting app does not start up, so I cannot test it on my own. Are you still happy with your implementation and its performance or do you see any drawbacks in the context of FET?

And what does that mean for the integration of virtual rooms in FET? I assume that this new algorithm is the building block which realizes my initial concept of virtual rooms. Now only the "3 of 5 rooms" option is missing. Correct?

If there's anything I can do for supporting you, please let me know. Thanks a lot for your excellent work!

Hello, math,

No problem! I was also talking to myself, putting the things in order.

So, you know the bipartite matching problem and the Hopcroft-Karp algorithm? Are you in mathematics or computer programming?

The application is the separate algorithm. It runs on command line, you need to run it on the terminal. I made a quick implementation and hard-coded one example into it, to check it, as I wrote above.

I am happy with the results, and it should run successfully in FET. But it won't be easy. I did not begin working on adding virtual rooms.

I do not understand your

Quote"3 of 5 rooms" option is missing

. If we do it with virtual rooms, where a virtual room has n sets, and each set has m_i rooms, it solves every possible situation. We need to select a real room from each set, using the bipartite matching algorithm.

Thank you as well for your ideas. I will keep you posted about the progress.

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.

Hello again, math,

Quote from: math on September 13, 2019, 03:54:58 PM
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").

Quote
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!

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/

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/

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.

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!

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.

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/

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!

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

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?

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.

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

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.

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.

I attach the Qt Designer source of the file and the screenshot of the dialog. I only designed the dialog, I did not begin coding in C++.

You're really fast in getting things done. Thanks a lot.  :)

What's the purpose of "Remove selected" and "Insert after"? Should the add/remove sets or rooms? I guess it's sets. But why "insert after"? Isn't the order of sets irrelevant?

I would recommend renaming the buttons "insert" and "delete". Since they are placed below the list of sets, each user should be able to trace the context, i.e. that they refer to insertion and deletion of sets.

If the order of sets is irrelevant, I would recommend adding new sets always at the end, setting its number as maximum number of sets plus one (not caring if the numbers are continous). Otherwise the dialog needs additional buttons for changing the order of sets (e.g. buttons "up" and "down").

The dialog also lacks buttons for adding/removing rooms to/from the set. I would recommend adding a "remove" button below the middle list and an "add" button below the right list. Again, from the context it should be clear that these buttons refer to the respective list above them.

OK, "Insert" (at the end) and"Remove". Yes, order is irrelevant, but I thought users want a nice order. But it is more difficult with order.

No space for "Up" and "Down" :(  (but anyway useless).

Double-click should do it. I will add "Clear" under "Selected rooms" and "All" under "All real rooms".

Thank you for your suggestions. Maybe you have more? :)

Attached a screenshot from Qt Designer.

Looks perfekt!

Regarding performance comparison of 5.39.0 and 5.39.1 (math-snapshot-16-sep-2019-20_29): I'm currently executing both FET versions on all example configuration files. 20-30 files are already finished and at the moment I cannot see mayor differences. Maximum performance drop is about 5%, but most values are very close. For one file 5.39.1 is even slightly faster.  ;)

I also tried increasing the optimization factor of g++ from -O2 to -O3. For 5.39.0 runtime decreased from 32,5s to 31,2s, for 5.39.1 it decreased from 32,9s to 32,4s. (all executed with --inputfile=examples/Germany/secondary-school-1/using_subactivities_constraints/German_subact_constr.fet --randomseedx=1 --randomseedy=1)

Thank you!  :)

Quote from: math on September 17, 2019, 05:28:07 PM
For one file 5.39.1 is even slightly faster.  ;)

hmm... Just to be sure maybe recheck if the seed at the end is the same. Maybe it generated an other result.

OK, I did the virtual rooms' dialog, which seems to be working; I have put the latest snapshot on https://lalescu.ro/liviu/Backup-fet/math/

I did not test generating with virtual rooms. I will do this now. There might be important bugs.

If you meet any bug, please report.

Edited to add: it does not generate. It crashes immediately on the attached file. I will try to find the bugs. I am not sure if today or tomorrow.

It seems I fixed the bugs and it seems to run on the modified file above. But I need to rest a bit, I am really tired of the work, and then check all what I done. I will inform you of the progress.

I hope later today I'll be ready, but I cannot guarantee.

I have good news and (very?) bad news:

The good news is that it works correctly when the timetable is not fixed. There are 3 files. The first is simple, the second is a bit more complicated and the third is more difficult (it requires the physics and chemistry labs, rooms 161 and 162, to be nearly fully occupied - see the last room in the rooms list - it is a virtual room).

You could try this snapshot on your file, if it does not contain (many) fixed activities.

The (very?) bad news is that FET won't generate on the fixed timetable of a more difficult file. It generates always on file 1, sometimes on file 2, and never on file 3. It is logical to me now, knowing that part of the algorithm, when I choose random rooms for a virtual room.

The link to the snapshot and to the examples: https://lalescu.ro/liviu/Backup-fet/math/

I will try now practically and theoretically to see what's wrong. But it might be a big unsolvable problem.

I hope I have good news: I made a small hack and the problem of locked timetables is solved.

How I made it: I consider that an activity which is locked in time and in a virtual room is only locked in time. So at the next allocation it might be scheduled in other real rooms (but in the same virtual room). Is that a problem?

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

After you generate, you will see only the virtual room in the studentss/teachers' timetables. The activities will appear in the real rooms' timetables, not in the virtual rooms' timetables, and the exact real rooms for an activity will appear (I implemented this) in the activities.xml. It is possible for me and/or Volker to add the real rooms in the HTML and View timetable students/teachers and Print timetables. This is as a future work.

Huu... it was difficult (the whole thing, from the beginning), but now I hope it is good  :)  Your suggestions were very good and helpful. But I am tired, need some rest now.

Quote from: Liviu Lalescu on September 18, 2019, 06:45:08 PMHuu... it was difficult the whole thing, but now I hope it is good  :)   I am tired, need some rest now.

hmm... You should work only like normal people. The problem is that you always forget to rest as soon as you are working. You skip too much private time and you skip too much resting time. You should work max 1/3 of a day. You need the other 1/3 of the day for resting and the last 1/3 of the day should be for private other stuff to keep you brain and body in shape.

Thank you, Volker   :)

PS: I modified slightly my message above, please read again.

yes, that correct. I am sorry, my grammar is bad and I do too many spelling error.

I fully agree with Volker: Liviu, you're working way too much. I never imagined you'd be able to complete that project that fast. Now please take all the time you need for debugging and improving, nobody's haunting you. Not even me.  ;)

Here's some feedback from my side:
Firstly, I was able to compile the version under Linux and OSX without any problems.

Secondly, I don't think that the room dialog is very intuitive:
- In listbox I cannot distinguish between real rooms and virtual rooms. Would it be possible to make the virtual entries appear in italic font or to add something to their name (e.g. "(virtual)")?
- for creating a virtual room, I first have to create a regular room, then making it virtual in the second step. Why not adding virtual rooms in the first place?
- when double-clicking a virtual room, the regular room dialog shows up where I can specify a building and a capacity. What relevance does this have in the context of virtual rooms? Since a virtual room encompasses multiple rooms, it does have multiple capacity values and may also spread over multiple buildings.
- wouldn't it make more sense to start the "make/edit virtual room" dialog when double-clicking?
- it seems as if virtual rooms can consist of real rooms only, i.e. FET does not support nesting of virtual rooms. However it is possible to add a real R1 room to a virtual room VR2, making that real room R1 virtual afterwards. This way VR2 consists of another virtual room.
(at least, FET complains about this when generating a new schedule.)


Moreover, it is possible to specify "room not available times" for a virtual room. Does this make sense?


Generating a schedule worked like a charm. I specified a virtual room which consists of two sets. When scheduling to this virtual room, FET allocates a real room for each set. In the student and teacher timetables there's no information about the real rooms but only the virtual room. However it should be easy to output both, e.g. "VR2 (R10, R15)" (allocated real rooms R10 and R15 representing virtual room VR2).


Thanks for all the work you put into this feature. Great job!

Quote
Secondly, I don't think that the room dialog is very intuitive:

Sorry, I am bad at interfaces  :)

Quote
- In listbox I cannot distinguish between real rooms and virtual rooms. Would it be possible to make the virtual entries appear in italic font or to add something to their name (e.g. "(virtual)")?

I will do this: "Room1", "VR: Room2" (begin with "VR: ").

Quote
- for creating a virtual room, I first have to create a regular room, then making it virtual in the second step. Why not adding virtual rooms in the first place?

Because most users will not use virtual rooms, and for simplicity. And because I am bad at interfaces.

Quote
- when double-clicking a virtual room, the regular room dialog shows up where I can specify a building and a capacity. What relevance does this have in the context of virtual rooms? Since a virtual room encompasses multiple rooms, it does have multiple capacity values and may also spread over multiple buildings.

It has a specified building which will be used in the buildings constraints. Also the capacity - each activity which is put into this virtual room must have the number of students less or equal to the room capacity. Unfortunately, the capacity of the real rooms will be neglected in this case.

Quote
- wouldn't it make more sense to start the "make/edit virtual room" dialog when double-clicking?

See above.

Quote
- it seems as if virtual rooms can consist of real rooms only, i.e. FET does not support nesting of virtual rooms. However it is possible to add a real R1 room to a virtual room VR2, making that real room R1 virtual afterwards. This way VR2 consists of another virtual room.
(at least, FET complains about this when generating a new schedule.)

:)

Thank you for this bug report! What a tricky thing you thought!  :)  I will fix it (disallow making a real room virtual if it is in the real rooms sets of a virtual room).

Quote
Moreover, it is possible to specify "room not available times" for a virtual room. Does this make sense?

Yes, it will be an overall constraint. See also the building and capacity problems above.

Quote
Generating a schedule worked like a charm. I specified a virtual room which consists of two sets. When scheduling to this virtual room, FET allocates a real room for each set. In the student and teacher timetables there's no information about the real rooms but only the virtual room. However it should be easy to output both, e.g. "VR2 (R10, R15)" (allocated real rooms R10 and R15 representing virtual room VR2).

Yes, it is easy. I will do this. However, I need also Volker's help in the Print dialog and in the outputting of the HTML timetables (and exporting the timetable as CSV?)

Unfortunately, the locking is bad. The activity will be locked to the virtual room, but not to each real room of this virtual room as needed. If you generate again, you might get other real rooms for this virtual room.

This topic started due to your problem that you want to allocate a virtual room (with three sets of one room each?) or a real room to an activity. Is this problem solved?

QuoteThis topic started due to your problem that you want to allocate a virtual room (with three sets of one room each?) or a real room to an activity. Is this problem solved?

It's working like a charm. I don't need any more christmas presents this year.

Thanks a lot!

Thank you for your very valuable suggestions which made this possible!

I thought about it. If we don't risk, we don't get progress. I also risked much in the past on the new FET features. So I think I will add this to the official FET, the future 5.40.0. It should stay in a prerelease state for some time, though.

I corrected the above minor bugs. Now me and Volker need to unite our efforts to output the real rooms of a virtual room in the HTML timetables, in the XML timetables, in the CSV timetables, and in the Print dialog. Also, we need to update the import/export for the rooms (to allow virtual rooms).

Adding such a feature is definitely a risk. I guess it will take some time until all bugs are found and all inconsistencies have been solved. Thanks a lot for providing us with such a powerful tool. From my work at our university I know other commercial planning tools which have a nicer interface, but which do not even come close to the featureset of FET.

I would like to continue testing the new feature, so I would appreciate if you could update the snapshot. But don't hurry, nobody's pushing you.


There's one thing that I noticed:
I'm using tags for assigning rooms, as you suggested some months ago. So I have a tag "150+P", saying "this is a lecture for 150+ students". Then I used "Space -> Tags -> An activity tag has a set of preferred rooms" for specifying preferred rooms for activities with this tag.
Now I'm able to select virtual rooms here. Assuming I have a virtual room with two sets, FET allocates a room for each set, so that multiple rooms are allocated for an activity with this set. This is working like a charm, as I already stated.

Now the thing: If I take this tagged activity, I'm able to specify "Space -> Activities -> An activity has a preferred room" (resp. a set of preferred rooms). I'm not quite sure how to understand that constraint in the context of virtual rooms.

Up to now it was easy: If I'm tagging an activity and specify this constraint, a room is allocated that is both listed as preferred for the tag and the activity.

I guess the meaning of this constraint is still the same. So if I'm specifying a preferred room for such an activity, FET tries to use this room for all sets of the virtual room. As a matter of fact, this is impossible since a room cannot be allocated by multiple sets at the same time. Unsurprisingly, generating a schedule fails, but the error message is kind of confusing: "Cannot generate timetable, because for activity with id==20 you have no allowed preferred room (from preferred room(s) constraints)." Would it be possible to change that error message in a way that the user knows where to look for the problem? Example: "Cannot generate timetable, because for activity with id==20 you defined more sets in virtual rooms than you allowed as preferred room (from preferred room(s) constraints)."


And another question, just for curiosity: in the FET-News section I can see that you did not increase the major version of FET during the last 10 years. Following that logic, you started the FET development about 50 years ago.  ;)
So when did you actually start with FET? Has there ever been a version 4?

Quote from: math on September 20, 2019, 06:03:45 PM
I guess the meaning of this constraint is still the same. So if I'm specifying a preferred room for such an activity, FET tries to use this room for all sets of the virtual room. As a matter of fact, this is impossible since a room cannot be allocated by multiple sets at the same time. Unsurprisingly, generating a schedule fails, but the error message is kind of confusing: "Cannot generate timetable, because for activity with id==20 you have no allowed preferred room (from preferred room(s) constraints)." Would it be possible to change that error message in a way that the user knows where to look for the problem? Example: "Cannot generate timetable, because for activity with id==20 you defined more sets in virtual rooms than you allowed as preferred room (from preferred room(s) constraints)."

Good thing you observed this.

1) Each activity has some preferred rooms items. It does not matter if a room is virtual or real. They are treated the same. The intersection of the preferred rooms items must not be void. In your case it is void: one item is the virtual activity, one item is the real activity. I cannot improve the error message, unfortunately. Luckily it reports impossibility in a real case.

2) If the user had a virtual room VR ((R1, R2, R3)) and preferred room for A to VR and another preferred room for A to R1, FET would report again impossible, even if VR has a single set and the timetable is possible, theoretically. Because VR is different from R1, in FET. So, I just made an assertion that each virtual room has at least two sets (otherwise you could use directly preferred rooms constraints, isn't it? - please confirm this, it is important - I am tired, I might be wrong).

Quote
And another question, just for curiosity: in the FET-News section I can see that you did not increase the major version of FET during the last 10 years. Following that logic, you started the FET development about 50 years ago.  ;)
So when did you actually start with FET? Has there ever been a version 4?

:)

Please see:

1) Documentation page of FET homepage, History.

2) FET package - ChangeLog file (without dates, unfortunately).

Are you suggesting now FET-6.0.0?  :)  I would like, but the changes are not so important. FET-5 means good algorithm, FET<5 was using the genetic algorithm, which was very bad.

I will post at least each day I work a new snapshot (in fact just did, but I will now make some more changes and update a bit later a new snapshot).

I have updated to FET-5.40.0-snapshot - your virtual rooms are now official. I hope no critical things will show up.

I have also compiled it for Windows. And I have good news: it takes the same time as FET-5.39.0 on my test. I don't know why on GNU/Linux it is a bit slower.

The link: https://lalescu.ro/liviu/Backup-fet/  , for now.

I added the real rooms in the Timetable view dialogs (if the activity is scheduled in a virtual room), please verify me.

Also please verify my text I have put in the Rooms->Help and Make/edit virtual->Help. Please make suggestions, if you want.

I think that in the Make/edit virtual dialog, instead of "Insert", I should write "Add". What do you think?

We did a good job!  :)

QuoteIf the user had a virtual room VR ((R1, R2, R3)) and preferred room for A to VR and another preferred room for A to R1, FET would report again impossible, even if VR has a single set and the timetable is possible, theoretically. Because VR is different from R1, in FET. So, I just made an assertion that each virtual room has at least two sets (otherwise you could use directly preferred rooms constraints, isn't it? - please confirm this, it is important - I am tired, I might be wrong).

I understand the problem: scheduling fails because there is no intersection set between VR and R1 - even though R1 is part of VR - because VR is handled as a room, not resolving the real rooms within the sets.  I think that this way of handling virtual rooms definitely makes sense.

QuoteAre you suggesting now FET-6.0.0?

Not really. I was curious. 5.40.0 is perfectly fine for me.  :)

Just two questions to other users, since Liviu and me disagree:

a) In the interface the virtual room AND real room might be useful, since the timetable maker might need to hunt bugs. The critical stuff is that it might be too much information, the interface might be to full. So is it needed to enable/disable them (both)?

b) What about the html files for teachers and students. Teachers and students don't know where to go if they see a virtual room. So they need to know the real room. So we must print the real room of course.
But what about the virtual room. Is there any reason to print also the virtual room? In my opinion it is just very critical and wasting space. FET users already complained right now that the timetables doesn't fit on a paper. So why printing the virtual room name into the html timetable? Is there any reason why a teacher or a student needs to know the virtual room name if he can already see the real room names? Isn't that just wasting space and confusing fet users, teachers and students since the same virtual room might end up in different real rooms?! So I also fear students and teacher might run into the wrong room if they only quick read the virtual room name.

My proposal is to have a check box, Print virtual rooms in HTML timetables, active by default. This is in my opinion logical. If the user does not want to see virtual rooms, he can simply disable that check box. But the preferred room(s) constraints in FET relate to the virtual room(s), not to the chosen sets of real rooms for that virtual room.

i must admit that i don't like that proposal, since:
a) Most users are not experts. many won't find the checkbox. just read this forum, we help them already now many times, even similar stuff is written in the manual. it is just complicating things. if, then it should be disabled by default.
b) i can't see a single reason why the virtual room name should be useful for a teacher or a student. it will confuse them. i can tell you that even with real rooms only some students and some teachers are already confused today if they have got for example physics one time on room A and the other day in room B. Printing virtual room names with the same name but in fact different rooms will confuse them (and others) much more. i highly suggest to not print virtual room names. only real room names.
c) i also fear of the space problem of the paper, just check how many guys ask because printing problems in this forum. we only need to help more guys to disable an needed feature. it is unneeded work (the coding of printing the virtual room name and the help for disabling an unneeded feature.)

My arguments are that users may use in other ways the virtual rooms. And that they might want to see the virtual room. And that FET will not retain the real rooms in a generation on a locked file, which might puzzle the users.

I don't understand. What other ways?

The "And that FET will not retain the real rooms in a generation on a locked file, which might puzzle the users." is a second other big problem of the current solution. Other school administration software that tries to load a fet file can't restore the real rooms. So for example TiTiTo and other tools will only get a virtual room, not the real room. So teachers and students don't know where to go :-(

If they want to have for instance virtual rooms representing real rooms. Or other ways in which the user wants to see the virtual room.

Yes, this is a problem. I will think of it, but it is very difficult. If I cannot solve it, the users should avoid virtual rooms or use both the .fet file and the activities.xml file. It is above my possibilities for now  :(

but in that case the real rooms are already printed. So you will print the same name 2 times. That is only wasting space.

No, because the virtual room (corresponding to a real-life room) contains more sets of rooms (which say might be uninteresting).

I don't understand. Can you give me an example file?

Maybe if the user wants to name three rooms R1, R2, and R3 as VR. I am not sure, I just gave a possibility.

OK, Volker, you win. I added a check box, 'Print virtual rooms in timetables', and by checking how the timetables look I decided to make it 'false' by default.

I added a new snapshot, please test it: https://lalescu.ro/liviu/Backup-fet/

There remains the serious problem that a fixed timetable cannot store the real rooms for each activity scheduled in a virtual room. And in a new generation these real rooms might change. But I don't know how to solve it, because of the internal data structure  :(

In general I would agree with Volker. In most scenarios the virtual room is only relevant for internal purposes and does not need to be printed anywhere. However there might be scenarios where this is not the case.

In our university I book all required rooms on basis of the generated schedule. As I mentioned in my first posting, we can remove the rooms between three lecture rooms, making it a combined lecture hall. This hall then can be used for our large lectures that would not fit in any regular room. In fact I'm reserving the three rooms under their regular rooms, setting a flag that the walls need to be removed. However this could also happen in a different way, reserving the hall using the virtual room name.

So I like the idea of adding a checkbox to the FET configuration. And again I agree with Volker, this checkbox should be disbled by default.


Concerning the locking issue: I understood that only the virtual room is locked but not the real rooms representing the virtual room. So it might happen that - after locking time and space of all activities of a generated schedule - the real rooms change when generating the schedule again?

If this is the case, this would be a real problem. After I generated a schedule, I have to reserve all required rooms. At this, details of the lecture have to be specified for every room, i.e. name of lecture, name of teacher, ... It is quite usual that parts of the schedule have to be changed at a later point of time, so I remove the space/time locking of SOME activities, generating a schedule for that part again. It is absolutely essential that the other part remains unchanged. If not, I would need to check ALL activities (not only the activities that I unlocked) whether the activity has changed or not.

Moreover this would contradict the manual optimization of schedules. Here I often manually shift room allocations so that specific activities have rooms close to each other or that are particularly well suited for specific activities.

I will try to make activities retain also the real rooms if they are locked in a virtual room.

I released a new snapshot. This has not implemented this correctly, yet, and locked timetables might become impossible if using virtual timetables (as I wrote previously). I gave up that hack I made.

https://lalescu.ro/liviu/Backup-fet/

Good news: I finished the most difficult part of locking virtual rooms in real rooms, and it works!  :)

Now I have some more things to do, then checking, but I hope it will work. And it satisfies everybody: me, Volker, math, and other users (and the users of TiTiTo).

I will let you know of my progress.

I am not completely finished, but the difficult part is done. I did a lot of bug fixing and testing.

I have put the latest snapshot here: https://lalescu.ro/liviu/Backup-fet/  (only the tar.bz2 for now, because math and Volker usually compile on their own).

It misses only one thing: to add/modify completely a constraint activity preferred room (if the room is virtual, the dialogs need to allow modifying the list of real rooms).

I am really happy with the results.

math, I would be interested in your feed-back (but you can wait for the finished snapshot, hopefully tomorrow). Try to crash FET, to make impossible timetables when it should be possible. Try your usual operation of locking/unlocking partially (only some activities).

Volker, maybe you could also test and check my code by random inspection.

My head hurts now, I need a longer break/sleep.

You should really take some time off. Are you counting the numbers you put into FET? :)

I'm looking forward testing the new version. Unfortunately tomorrow is fully booked, so it might take until Tuesday.

Thanks a lot again!

:)

I have released a new snapshot. Still not ready yet, but I changed a bit the .fet XML file. If you have virtual rooms in your file, you either can manually edit the .fet XML file (ask me how), or input them again.

Same link: https://lalescu.ro/liviu/Backup-fet/ , again only tar.bz2.

I hope I am finished with the new code, correctly (the add/modify constraint activity preferred room dialogs - please check them). The same link: https://lalescu.ro/liviu/Backup-fet/

I will now test some more, translate to Romanian and hopefully put a new snapshot for the translators to translate and for the users to test.

I corrected some minor things. The new version (including Windows executable) is on https://lalescu.ro/liviu/fet/download/test/  (also on the old link).

Please test and let me know.

Hi Liviu!

Thanks for the new version. Yesterday evening I was testing the previous version for an hour or two, but did not find any problems. I was primarily focusing on the consistency of locked schedules, resp. partially unlocked schedules. Everything worked pretty fine, especially  locked real rooms of a virtual room did not change.

Today it's my wife's birthday, so I better should not spend my time with FET.  ;)

Thank you!

Happy Birthday to her! Have fun! See you tomorrow.  :)

I added a new snapshot, with minor updates: https://lalescu.ro/liviu/fet/download/test/  . I am not sure which version were you using, but you might want to use this latest one.

Virtual rooms idea is great and working perfectly. I tried checking by considering 3 sets with one real room in each set.

Since, FET is picking one real room from each set to assign an activity to virtual room, I couldn't think about the practical application of having 2 or more real rooms in each set.

Thank you for your report!

It is useful one or more sets with >= 2 real rooms in them. Maybe the user wants an activity into two rooms: R1 and (any of R2 or R3).

I added a new snapshot.

Hi Liviu!

It's amazing how well the virtual room feature is already working. Excellent work! And thanks for the new version. I played around quite a lot with today's version and did not find that much. Basically it's only just optical issues and a single technical question. Let's begin with that.

Attached you find a configuration file that has a tag that is linked to a virtual room. Two activities are using that tag, so that two rooms are assigned for these activities at schedule generation time. So far, so good.

Now I select "Space -> Activities -> An activity has a set of preferred rooms". Here I select the mentioned tagged activity, assigning a lecture room and a tutorial room (exam room). Theoretically, the lecture room could be assigned as room for set 1 of the virtual room, while the tutorial room suits the requirements of set 2. However, schedule generation fails. I guess you already explained the reason: FET tries to assign the preferred room as virtual room (and NOT the sets inside this virtual room). Hence, schedule generation fails.

Hoever, even if I select the virtual room inside this constraint dialog, the schedule generation fails. Shouldn't it succeed?

Moreover, it's strange that I'm able to specify the virtual room in that dialog, because it's a single room only. Doesn't this dialog require a minimum of two rooms?

Also surprising: when selecting "Space -> Activities -> An activity has a preferred room", I can only select real rooms (not virtual rooms). If FET maps virtual rooms to preferred rooms (this is how I understood you), why is this dialog reserved for real rooms only?


Now some optical issues:
- In the "Data -> Space -> Rooms" dialog you add a "V:" in front of virtual rooms, so that real rooms can be distinguised from virtual rooms. Unfortunately this differentiation is available in this dialog only. In all other roomlists the "V:" is missing, so the user has to know whether a room is real or virtual.
- When double clicking a virtual room in the "Data -> Space -> Rooms" dialog, the dialog "Modify room" pops up. Doesn't it make more sense to start the "Make/edit virtual room" dialog instead?
- "Data -> Space -> Rooms -> Modify room" allows specifying a building and a capacity for a virtual room. Does this make any sense? If it is required for scheduling, both values could be derived from the real rooms that have been allocated.
- When trying to save a virtual room with an empty set, the following error message is displayed: "The set of real rooms number 1 has no real rooms - incorrect, because each set must be nonvoid". I doubt that the regular user understands that message. "Error: sets must not be empty. Please specify at least one real room for set 1" is perhaps easier to understand.
- When removing a set in that dialog, the set is deleted without any confirmation message. So it's quite easy to remove a set by mistake. Shouldn't there be some "Are you sure to remove that set? Yes/No" kind of thing?
- When removing set 1 in that dialog, the old set 2 becomes the new set 1. So the optical impression is that the user deleted the last set (by mistake) instead of the first set. Is it necessary to reorder the sets? Is the number of the set saved somewhere? Or is it just a list of elements, where set 1 is the first element of the list?


And most important: I still think that is is a very very very bad idea to specify both real rooms and virtual rooms in a single dialog. I still recommend to leave the room dialog as it was in the previous version, adding a "virtual room" dialog in addition. From the programming perspective this does not require any modifications in the data structures, because these two dialogs could work on the same data set, only just not on the entire data set but parts of it.

For the regular user this has the advantage, that she does not have to learn anything new and everything looks familiar. The new functionality is capsuled in a new dialog, so it's a clear cutting line between old and new.


That's it for today, bed is calling me. :)

Quote from: Liviu Lalescu on September 25, 2019, 10:30:05 PM
I added a new snapshot.

Maybe you can think to extend the virtual rooms feature to virtual activities. A virtual activity contains 2 or more real activities. This way 2 or more activities can be scheduled in one room (eg: something like a big hall)

Quote from: Nagendra on September 26, 2019, 05:29:06 AM
Maybe you can think to extend the virtual rooms feature to virtual activities. A virtual activity contains 2 or more real activities. This way 2 or more activities can be scheduled in one room (eg: something like a big hall)

I think too complicated and unnecessarily. You could add more rooms to represent a big hall.

Hello, math, and thank you for the very detailed report!

Quote from: math on September 25, 2019, 10:55:52 PM
It's amazing how well the virtual room feature is already working. Excellent work! And thanks for the new version. I played around quite a lot with today's version and did not find that much. Basically it's only just optical issues and a single technical question. Let's begin with that.

Attached you find a configuration file that has a tag that is linked to a virtual room. Two activities are using that tag, so that two rooms are assigned for these activities at schedule generation time. So far, so good.

Now I select "Space -> Activities -> An activity has a set of preferred rooms". Here I select the mentioned tagged activity, assigning a lecture room and a tutorial room (exam room). Theoretically, the lecture room could be assigned as room for set 1 of the virtual room, while the tutorial room suits the requirements of set 2. However, schedule generation fails. I guess you already explained the reason: FET tries to assign the preferred room as virtual room (and NOT the sets inside this virtual room). Hence, schedule generation fails.

Indeed.

Quote
Hoever, even if I select the virtual room inside this constraint dialog, the schedule generation fails. Shouldn't it succeed?

I tried and it solves. See the attached file.

Quote
Moreover, it's strange that I'm able to specify the virtual room in that dialog, because it's a single room only. Doesn't this dialog require a minimum of two rooms?

I don't understand. In the "activity preferred rooms" dialog you can add any number of rooms and FET will choose only one in the generation.

Quote
Also surprising: when selecting "Space -> Activities -> An activity has a preferred room", I can only select real rooms (not virtual rooms). If FET maps virtual rooms to preferred rooms (this is how I understood you), why is this dialog reserved for real rooms only?

You select the room from the combo box on the left. If that room is virtual, you can select also the real rooms from the list box on the right if you want, but in this case the weight must be 100% and the number of real rooms should be the same as the number of sets in the virtual room.

Quote
Now some optical issues:
- In the "Data -> Space -> Rooms" dialog you add a "V:" in front of virtual rooms, so that real rooms can be distinguised from virtual rooms. Unfortunately this differentiation is available in this dialog only. In all other roomlists the "V:" is missing, so the user has to know whether a room is real or virtual.

Sorry, feature not bug :(  . Too difficult to change now.

Quote
- When double clicking a virtual room in the "Data -> Space -> Rooms" dialog, the dialog "Modify room" pops up. Doesn't it make more sense to start the "Make/edit virtual room" dialog instead?
- "Data -> Space -> Rooms -> Modify room" allows specifying a building and a capacity for a virtual room. Does this make any sense? If it is required for scheduling, both values could be derived from the real rooms that have been allocated.

Sorry, feature not bug :(  . Read the Help in the Make/edit virtual room. The building and the capacity accepted for an activity are those of the virtual room, not those of the chosen real rooms.

Quote
- When trying to save a virtual room with an empty set, the following error message is displayed: "The set of real rooms number 1 has no real rooms - incorrect, because each set must be nonvoid". I doubt that the regular user understands that message. "Error: sets must not be empty. Please specify at least one real room for set 1" is perhaps easier to understand.

Hmm, sorry, I already asked the translators to translate. I'll think about it.

Quote
- When removing a set in that dialog, the set is deleted without any confirmation message. So it's quite easy to remove a set by mistake. Shouldn't there be some "Are you sure to remove that set? Yes/No" kind of thing?

Also you can double-click a real room without confirmation. I am not sure. You could press "Esc" or "Cancel" if you removed a set by mistake, and start over with that virtual room.

Quote
- When removing set 1 in that dialog, the old set 2 becomes the new set 1. So the optical impression is that the user deleted the last set (by mistake) instead of the first set. Is it necessary to reorder the sets? Is the number of the set saved somewhere? Or is it just a list of elements, where set 1 is the first element of the list?

I wrote about this in the Help button.

I could write "Set", "Set", ..., "Set", but I think numbers will help more than disturb.

Quote
And most important: I still think that is is a very very very bad idea to specify both real rooms and virtual rooms in a single dialog. I still recommend to leave the room dialog as it was in the previous version, adding a "virtual room" dialog in addition. From the programming perspective this does not require any modifications in the data structures, because these two dialogs could work on the same data set, only just not on the entire data set but parts of it.

For the regular user this has the advantage, that she does not have to learn anything new and everything looks familiar. The new functionality is capsuled in a new dialog, so it's a clear cutting line between old and new.

I prefer my way, because virtual rooms are nothing but rooms in the generation. I'll think about it.

Some improvements:

1) If there are 4 sets with one real room (capacity of each real room:30) in each set. If an activity with 90 students needs to be scheduled then the present form of virtual rooms "allot" all 4 real rooms (example attached) whereas only three real rooms are sufficient to cater to 60 90 students.

If only three real rooms are allotted then the fourth real room can be utilized for another activity with 30 students.

2) Virtual room capacity should be variable based on the capacity of real rooms in it. User shouldn't be asked to specify it.

Thank you, but unfortunately both (1) and (2) are too difficult for me.

Hmm....

(1) can be handled by the below trick though
1) VR-2 (Virtual room-2) will have 2 sets
2) VR-3 (Virtual room-3) will have 3 sets
.
.
.
VR-infinity :P

(2) need to look for a trick...

Hi Liviu!

QuoteHoever, even if I select the virtual room inside this constraint dialog, the schedule generation fails. Shouldn't it succeed?
I tried and it solves. See the attached file.

Don't know what I did yesterday. Now it's working on my side as well

QuoteAlso you can double-click a real room without confirmation. I am not sure. You could press "Esc" or "Cancel" if you removed a set by mistake, and start over with that virtual room.

I don't think that sets and rooms can be compared in this context. If I'm double clicking a room by mistake, I can revert this mistake by clicking on the same room again. If I'm deleting a set, all the specified rooms inside the set are deleted as well. So it's more difficult to revert the error. At the end it's your decision, but I wouldn't mind a confirmation message.

QuoteI wrote about this in the Help button.
I could write "Set", "Set", ..., "Set", but I think numbers will help more than disturb.

The help text did not answer my question. I asked whether a set has an id in the internal data structures or if it's just a list (so that number 2 gets automatically number 1 as soon as the old number 1 is deleted.

QuoteI prefer my way, because virtual rooms are nothing but rooms in the generation. I'll think about it.

I know that virtual rooms are nothing but regular rooms (and that this was the beauty that attracted your attention). But that is your developer's perspective. The regular user does not know internals, so that regular rooms are regular rooms and virtual rooms are virtual rooms. I guess the average user will never work with virtual rooms, so having two different dialogs would reduce the complexity of the room dialog. But again, it's entirely your decision.

Quote from: math on September 26, 2019, 06:40:08 PM
I don't think that sets and rooms can be compared in this context. If I'm double clicking a room by mistake, I can revert this mistake by clicking on the same room again. If I'm deleting a set, all the specified rooms inside the set are deleted as well. So it's more difficult to revert the error. At the end it's your decision, but I wouldn't mind a confirmation message.

OK, your way is better. I added a confirmation here. I added a new snapshot ( https://lalescu.ro/liviu/fet/download/test/ ).

Quote
The help text did not answer my question. I asked whether a set has an id in the internal data structures or if it's just a list (so that number 2 gets automatically number 1 as soon as the old number 1 is deleted.

No id, just a list. I added an explanation when you remove a set (in the confirmation, see above).

Quote
I know that virtual rooms are nothing but regular rooms (and that this was the beauty that attracted your attention). But that is your developer's perspective. The regular user does not know internals, so that regular rooms are regular rooms and virtual rooms are virtual rooms. I guess the average user will never work with virtual rooms, so having two different dialogs would reduce the complexity of the room dialog. But again, it's entirely your decision.

I am sorry to disagree with you here. But I will think about it and wait to see also what other users say.

I added a new snapshot, with a rare but important crash bug fix. There is a file to prove that in the downloads directory ( https://lalescu.ro/liviu/fet/download/test/crash-file-solved-on-2019-09-27/k.fet ).

Link, as usual: https://lalescu.ro/liviu/fet/download/test/

There is something interesting about finding a random bipartite matching in the graph:

Consider the example S1 (R1, R2), S2 (R2, R3, R4).

If you draw the graph with the rooms on the left and the sets on the right, the probabilities are: (R1, R2), (R1, R3), and (R1, R4) - 20.83%, (R2, R3) and (R2, R4) - 18.75%.

If you draw the graph with the rooms on the right and the sets on the left, the probabilities are: (R1, R2) - 25%, (R1, R3) and (R1, R4) - 16.67%, (R2, R3) and (R2, R4) - 20.83%.

(I mean I am applying a kind of randomization of the Hopcroft-Karp algorithm on this graph).

I am using the first variant. I am not sure how to ensure that the matching will be "random enough". I hope in practice my simple randomization will work (the randomization means the order of the rooms on the left considered in the algorithm is random and the adjacency of these rooms will also have a random order).

Maybe you can help me with ideas.

I added a new snapshot, making things a bit faster in some situations.

The same link: https://lalescu.ro/liviu/fet/download/test/

Sorry, I did not understand your previous posting regarding the differences in percentages (probabilities?) of sets. But maybe it's more a reminder for yourself than an information for us. Right? ;)

Thanks for the new versions, but I'm not quite sure if I find the time for testing before Monday. It's quite a busy weekend...

Quote from: math on September 28, 2019, 06:27:40 PM
Sorry, I did not understand your previous posting regarding the differences in percentages (probabilities?) of sets. But maybe it's more a reminder for yourself than an information for us. Right? ;)

:)

If you draw a bipartite graph, you can have R (rooms) on the left and S (sets) on the right, or viceversa, S on the left and R on the right.

I now apply a randomization (randomize the order of the nodes on the left, and randomize each node's from the left order of links to the nodes on the right).

The results (practical and theoretical) for the two graphs are different. This might be normal.

I am searching for the best way to get a random maximum bipartite matching.

Quote
Thanks for the new versions, but I'm not quite sure if I find the time for testing before Monday. It's quite a busy weekend...

Absolutely no problem! You tested enough.

I hope to release someday next week.

I have put a new snapshot (as usual: https://lalescu.ro/liviu/fet/download/test/ ).

Please test again on a few of your files and report to me as soon as you finish. I hope to release the official tomorrow or the day after tomorrow.

I have released FET-5.40.0 with virtual rooms. Thank you!