Assigning multiple small rooms or one large room

[math]

Ok, let's do it this way.

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

[Liviu Lalescu]

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

[Liviu Lalescu]

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.

[Liviu Lalescu]

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.

[Liviu Lalescu]

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.

[math]

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

[Liviu Lalescu]

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

[Liviu Lalescu]

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.

[Liviu Lalescu]

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

[Liviu Lalescu]

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.

[Liviu Lalescu]

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.

[Liviu Lalescu]

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.

[Liviu Lalescu]

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.

[math]

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!

[Liviu Lalescu]

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

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