mdgp_solver.RdGiven a distance metric for each possible pair in the frame of n individuals, find a partition into as many groups as possible with group size at least m. This is an instance of the maximallz diverse grouping problem, which we use the algorithm by Lai and Hao (2016) to solve.
mdgp_solver(mdgp_format_file, time_limit = 30)
| time_limit | Number of seconds to iteratively optimize each run. The larger the number of participants to group, the larger this value should be. Rule of thumb: time_limit = exp(0.5 + 0.0025*n) |
|---|---|
| mdg_format_file | Path to the file containing the MDGP specification in mdgplib format |
File name of the solution file
The maximally diverse grouping problem is about partitioning \(n\) individuals into groups of size at least \(m\) while maximizing a sum of utility values computed by summing the utility \(u(i,j)\) over all individuals \(i\),\(j\) partitioned into the same group. and summing this quantity over all groups. More formally, let \(d_{ij}\) denote the number of time unit (typically days) ago, that individual \(i\) and \(j\) were in the same group. Note: This distance is derived by looking at the previous partitions and it is a matter of definition what this value should be, if \(i\) and \(j\) have not previously been in the same group. Let \(n_g=n\> \text{div}\> m\) denote the resulting number of groups where \(\text{div}\) denotes integer division. For a given partition let \(x_{ig}\) be an indicator variable, which is 1, if \(i\) is assigned into group \(g\) and zero otherwise. A solver of the maximally diverse grouping problem now tries to maximize $$\sum_{g=1}^G \sum_{i=1}^n \sum_{j=i+1}^n d_{ij} x_{ig} x_{jg},$$ subject to the conditions $$\sum_{g=1}^{G} x_{ig} = 1, \quad i=1,\ldots,n,$$ $$\sum_{i=1}^n x_{ig} = n_g, \quad g=1,\ldots,G,$$ $$x_{ig} \in \{0,1\}, \quad i=1,\ldots,n; g=1,\ldots,G,$$ where \(n_g\) is the size of group \(g\), i.e. \(\sum_{g=1}^G n_g = n\). We shall adopt the convention that group sizes are determined by assigning the labels \(1,\ldots,G\) to all individuals and then count how often each label occurs. This means, e.g., that for \(n=7\) and \(m=4\) we get \(n_g=7\> \text{div}\> 4=1\) group with 7 members.
Note: The code calls C++ code by Xiangjing Lai and Jin-Kao Hao, for this several temporary files are generated using `tempfile()`.
Xiangjing Lai and Jin-Kao Hao (2016). *Iterated maxima search for the maximally diverse grouping problem*. European Journal of Operational Research, 254(3), pp. 780-800, https://doi.org/10.1016/j.ejor.2016.05.018
Xiangjing Lai and Jin-Kao Hao, R interface by M. Höhle