2
$\begingroup$

Let's say we have a grouping of people as such:

   Group People
1      1     40
2      2     40
3      3     43
4      4     15
5      5     41
6      6     10
7      7     23
8      8     17
9      9     32
10    10     31
11    11     21
12    12     12
13    13     25

There are 350 people and the goal of this problem is to group those people into 38 "tables" of size 9 and one "table" of size 8.

Rules:

-Make sure that all people are sitting with at least one other person of their original group

-It is best to have 9 people from the same group at the same table but obviously that will not be possible after dividing groups enough times.

-If one person cannot be grouped with another person of their original group, that is okay, but only at the end of the tabling.

Any ideas of how to achieve this will be welcome. And any ideas of how to achieve this in R are also welcome but not required.

Here's the data if you want to play with it in R:

structure(list(Group = structure(1:13, .Label = c("1", "2", "3", 
"4", "5", "6", "7", "8", "9", "10", "11", "12", "13"), class = "factor"), 
    People = c(40L, 40L, 43L, 15L, 41L, 10L, 23L, 17L, 32L, 31L, 
    21L, 12L, 25L)), .Names = c("Group", "People"), row.names = c(NA, 
-13L), class = "data.frame")
$\endgroup$
  • 1
    $\begingroup$ Possibly a question for math.stackexchange.com? $\endgroup$ – mkt Aug 3 '17 at 20:35
  • $\begingroup$ Do you mean 38 tables of size 9 and one table of size 8? $\endgroup$ – saulspatz Aug 11 '17 at 14:16
  • $\begingroup$ @saulspatz Yes, that is correct. $\endgroup$ – user111417 Aug 22 '17 at 15:32
2
$\begingroup$

This is a constraint satisfaction problem. We have 13 groups and 39 tables. For $1 \le g \le13$ and $1 \le t \le 39$, let $x_{gt}$ be the number of members of group $g$ seated at table $t$. We have $x_{gt} \ge 0$ and $x_{gt} \ne 1$. For each $g$ we have $\Sigma_t x_{gt} = p_g$, where $p_g$ is the population of group $g$. For $1 \le t \le 38$ we have $\Sigma_g x_{gt} = 9$, and we have $\Sigma_g x_{g, 39}=8$.

I don't have enough experience with constraint solvers to recommend one, but there are a number of free, open source solvers available. Using one will tell you whether it is possible to solve the problem, with the constraint that no person sits at a table with no other member from his group.

So far, I haven't addressed the requirement that "It is best to have 9 people from the same group at the same table." To do this, we have to convert the problem (somehow) to an optimization problem. We need an objective function to maximize. It seems that $\Sigma_{g,t}x^2_{gt}$ would do the trick.

That makes it a quadratic program with 507 integer variables and 1066 constraints. I know nothing at all about quadratic integer programming. I see that various solvers, like CPLEX, support "integer, linear, and quadratic programming," but I don't know if that means it supports the combination "integer quadratic programming." CPLEX is proprietary, expensive software. There is free software available, but I understand it is much slower than the proprietary programs.

Hopefully, I've given you enough information so that you can proceed by googling, or by asking questions on stackOverflow or math.stackExchange.

EDIT I've done some research on line, and it turns out that a problem of this sort is called mixed-integer quadratic program (MIQP), and a lot of work has been done on the problem which is important in portfolio optimization, for example. So googling MIQP should be helpful.

CPLEX I just did some quick googling, and I found that you can get a free evaluation copy of CPLEX for 90 days. Also, there is an R interface to CPLEX for Windows and "Linux/Unix-like" systems. RCplex's documentation describes it as an, "R interface to CPLEX solvers for linear, quadratic, and (linear and quadratic) mixed integer programs." A mixed-integer program is one in which some of the variables are reals, and some integer, and so it includes the case where they are all integer.

These tools should fill the bill. I don't know how much work it is to install CPLEX or to compile RCplex.

$\endgroup$
1
$\begingroup$

Actually, this problem is easy enough to solve with a pencil in a couple of minutes. Seat as many subgroups of 9 as possible from each group at their own tables, then deal with the remainders. The number of members of Group 6 is congruent to 1 modulo 9, so we leave it to the end. Group 8 is the only one whose population is congruent to 8, so we seat 9 of them at one table and 8 at another.

There are 3 groups (1, 2, and 10) with remainders of 4, and these can be paired with the three groups (5, 7, and 9) with remainders of 5 to make up tables of 9. Group 4 (remainder 6) can be paired with group 11 (remainder 3) to make another table. This leaves group 3 (remainder 7), group 12 (remainder 3) and group 13 (remainder 7). We can pair them with 2, 6, and 2 people, respectively, from group 6 to make up the last 3 tables.

This satisfies all constraints of the OP, and I think that it maximizes the objective function I suggested; if it doesn't, it must come awfully close.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.