How to solve this variation of schoolgirls Kirkkmanov

Question

I am trying to implement an application that assigns students to l laboratories in g lab groups. Limitations:

1: Students must work with new students for each laboratory. 2: Each student must be a laboratory leader once.

2 is not solvable if students cannot be divided evenly in laboratory groups. This is acceptable if “weird” students never become laboratory leaders.

I tried two approaches, but I'm not satisfied yet .:

• A taboo search that solves 1 but has problems with solution 2 (I actually solve 1 first and then try to solve 2, which may be the wrong approach, any suggestions)

• A simple solution in which I divide students into #labs in the array [0..6] [7..14] [15..21], and then rotate (from 0.1.2 on) and transpose the matrix, repeat this is for #labs times with increased rotation (1,2,4) and (2,4,6). For 21 students in 3 laboratories with groups of 7 people, the result is as follows:

  • laboratory 1: [0, 7, 14], [1, 8, 15], [2, 9, 16], [3, 10, 17], [4, 11, 18], [5, 12, 19] , [6, 13, 20]
  • Laboratory 2: [6, 12, 18], [0, 13, 19], [1, 7, 20], [2, 8, 14], [3, 9, 15], [4, 10, 16] , [5, 11, 17]
  • Laboratory 3: [5, 10, 15], [6, 11, 16], [0, 12, 17], [1, 13, 18], [2, 7, 19], [3, 8, 20] , [4, 9, 14]

laboratory leaders are the first column for laboratory 1, the second for laboratory 2 ...

This solution works decently, but, for example, 12 students in 3 laboratories or 150 students in 6 laboratories do not work. Any suggestions?

2 seems to handle the same number of cases or combinations and is lightning fast compared to 1. Maybe I should get a noble price :-)

Answer 1

Only a 1st level restriction is commonly called the social golfer problem. (Let parameters g be the number of groups, s be the size of each group, and w be the number of weeks. Grouping is the partition of g * s players in g into groups g of size s. Determine whether it is possible to find groups w such that each a couple of golfers are grouped no more than once.) The problem of a social golfer was studied in the literature of combinatorial optimization, and there are three types of approaches (you can use your favorite search engine to search for research articles):

• Local search. This is effective when w is significantly lower than its maximum possible value. Dotú and Van Hentenryck have a document that applies taboo searches to the social golfer problem.

• Full search. This is necessary when w is above or slightly below its maximum possible value, but it does not scale very well.

• Algebraic constructions. In this way, the notorious case g = 8 s = 4 w = 10 is solved. Unfortunately, no construction is known for many sets of parameters.

To appoint laboratory leaders, calculate the maximum correspondence between students and laboratory groups, where there is an advantage between the student and the laboratory group, if that student belongs to this group.