Formation of student groups with the help of optimisation

Abstract

We study the problem of forming groups of students so that the groups are as even as possible with respect to certain aspects and group members are changed as much as possible compared to previous groups, and formulate it as a mixed integer programming problem. We find that standard software cannot solve real life sized instances, so we develop several heuristics and metaheuristics for the problem. Computational tests are made on randomly generated instances as well as real life instances. Some of the heuristics give good solutions in short time, and tests on real life problems indicate that satisfactory solutions can be found within 60 seconds.

Keywords:

• Group forming
• heuristics
• metaheuristic
• mixed-integer programme

1. Introduction

In the IT-programme at Linköping University, the students are each semester divided into base groups, as a consequence of the problem based learning profile used. Each base group contains around seven students, depending on the total number of students, which is between 20 and 40. This is done in five semesters in sequence. Goals of the base group work are that each student should be active, participate in the discussions, and be able to work together with many different persons.

When forming a base group for a semester, some aspects are taken into account. First of all, the number of students should be the same, if that is possible, or otherwise as similar as possible.

One wish is that the students should as much as possible have different comrades in the base group from semester to semester. The students should learn to work together in groups, and this is best done if the groups are as different as possible.

Another aspect is that after some time, the students show different progress in their studies. This is quantified by the number of examination points each student has obtained. While this measure does not exactly show how well each student will do in the base group work, it is still preferred that all the best students should not be in the same group and all the worst students should not be in the same group.

There are more aspects that may be interesting, for example gender. One might want to have similar mixes between boys and girls in the groups, especially if one gender is much less represented than the other. There are also other aspects which one might like to divide evenly among the groups, such as age, various computer skills etc. We will include a list of aspects that may include whatever one wishes, and the goal will be to spread the measures of the aspects as evenly as possible between the groups.

The formation of base groups has in our case previously been done by hand, based on the information of each student’s points and all the previous groups the student has been in, and to some extent the gender. Sometimes additional information has been taken into account, such as two students not working well together, or two students working too well together (in which case they might dominate the group and give less room for the other students in the group).

In this paper, we describe a new optimisation model for the formation of good groups, and some experiences in using it. In our tests, we first take the three factors number (number of students in each group), points (total number of points of the students in a group) and repetition (a measure of how much two students have been in the same group in previous time periods) into account, but open the model for more aspects, such as gender etc, as discussed in Graf and Bekele (2006).

Considering literature in the area, we find a recent overview over some existing group formation approaches in Maqtary, Mohsen, and Bechkoum (2017). Another algorithm for group formation, GroupAL, can be found in Konert, Burlak, and Steinmetz (2014). In Craig, Horton, and Pitt (2010) “reasonably optimal” groups are formed with genetic algorithms, and in Agustín-Blas, Salcedo-Sanz, Ortíz-García, Pérez-Bellido, and Portilla-Figueras (2008) a hybrid grouping genetic algorithm is used. In Graf and Bekele (2006) ant colony optimisation is used, while Yeoh and Nor (2011) propose an ad-hoc heuristic. Spoelstra, Rosmalen, van de Vrie, Obreza, and Sloep (2013) discuss several different measures, while Dascalu, Bodea, Lytras, de Pablos, and Burlacu (2014) focus on an interactive system, containing particle swarm optimisation. Other publications dealing with the issue in various ways are Ounnas, Davis, and Millard (2009), Cocea and Magoulas (2010), Tourtoglou and Virvou (2010), Abnar, Orooji, and Taghiyareh (2012), and Cocea and Magoulas (2012). We have not found any mixed-integer programming model in the literature that resembles ours and takes our aspects into account. Especially, the wish to avoid historical repetition is not present in any of the papers we have found. Often pairwise properties are used, rather then the group properties we use. Furthermore, we allow any number of aspects.

Another difference between our work and most others is that we do not use any input from the students, i.e. in principle all of our indata are undisputable numbers coming from our student registration system and from participation in previous groups. We do not use any subjective opinions from the students.

2. The mathematical model

Specifically we consider the following problem. We have n persons which shall be divided into m groups. As shown in Henry (2013) there are $$(n!/(m!(n-m)!\left)\right)/\left(\right(n/m)!((n!/(m!(n-m)!\left)\right)-n/m)!$$ different ways of doing this, and enumerating all possibilities has complexity $O(2^n)$, Konert (2015), so complete enumeration is not a possibility.

There are q previous time periods, in which the persons have been allocated to different groups. We let g_jt be the number of the group that person j was allocated to in time period t. Apart from the number of persons in each group, we have p different aspects that we wish to spread as evenly as possible between the groups, the first one being the points each person has obtained, and the following anything that is of interest (for example gender etc). We let a_lj be the measure of aspect l for person j. For example, $a_{1j}$ is the number of points person j has obtained. and $a_{2j}$ may be 1 if person j is female and 0 if person j is male.

Also needed are weights reflecting the importance we put on the different parts of the objective. We let w^N be the weight on the wish that the number of persons should be the same in each group, and w^T the weight on the wish that the persons should have different group partners from term to term. Furthermore, we let $w_l^P$ be the weight on the measure of aspect l, so $w_1^P$ will be the weight on the wish that each group should have a good mixture of high and low points. It is only the relation between these weights that is interesting. However, they must reflect the scaling of the aspects, since the number of persons in our real life examples will be below 10, while the number of points will be up to 120. Unlike the previous indata, which is given with certainty, these weights may need to be adjusted so that they accurately model our wishes.

Furthermore, the disadvantage of putting two persons, that previously were in the same group, in the same group again, may decrease by time. It may not be that serious if they were in the same group several time periods ago. We call this discounting. Therefore we let $w_t^A$ be the (relative) weight of time period t, i.e. reflect how much we take previous groups into account. We let $w_t^A$ be one for the most recent time period (the last time period in the model), and decrease the weights as we go back in time. One possibility (which is used in our computational tests) is to set $w_t^A=1/(1+q-t)$. If we do not use discounting, we set $w_t^A=1$ for all t.

The basic variable in the model is x_ij which is equal to 1 if person j is put in group i, and 0 if not. We also need the variable y_jk which is equal to 1 if persons j and k are put in the same group.

Furthermore, in order to control the properties of each group, we let v_i be the number of persons in group i and z_li the sum of the measure of aspect l in group i (so $z_{1i}$ is the total number of points in group i, and $z_{2i}$ could be the number of girls in group i, etc). We will also use v^L and v^U as the lowest and highest number of persons in a group, and $z_l^L$ and $z_l^U$ as the lowest and highest sum of measure of aspect l in a group.

The first and most obvious constraint in the model is that each person should be allocated to one group. $$\sum _i{x}_{ij}=1\text{for}\text{all}j.$$

Then, we need to get correct values of the additional variables. y_jk should be equal to 1 if both person j and person k belong to some group i, i.e. if x_ij = 1 and x_ik = 1. We get the following constraints. $$y_{jk}\ge x_{ij}+x_{ik}-1\text{for}\text{all}j,k\text{and}i,j\ne k$$

The values of v and z are simply obtained by summing up. $$v_i=\sum _j{x}_{ij}\text{for}\text{all}i.$$ $$z_{li}=\sum _j{a}_{lj}{x}_{ij}\text{for}\text{all}i\text{and}l.$$

Then, we get the variable upper and lower bounds on these variables as follows. $$v^L\le v_i\le v^U\text{for}\text{all}i.$$ $$z_l^L\le z_{li}\le z_l^U\text{for}\text{all}i\text{and}l.$$

Finally, we have the domain of the variables: $x_{ij}\in \{0,1\}$ for all i and j, $y_{jk}\in \{0,1\}$ for all j and k, $z_{li}\ge 0$ for all i and l, $v_i\ge 0$ for all i, $z_l^L,z_l^U\ge 0$ for all l, $v^L,v^U\ge 0$. (v will automatically become integer, and the same holds for z if all measures a are integral. However, in our real life example, half points are possible.)

Now, we need to formulate the objective function. The slightly difficult part is to minimise the negative effect of putting two persons in the same group. For this, it is more convenient to have the coefficients d_jkt = 1 if person j and person k were in the same group in time period t. These coefficients are easily calculated by initiating d to zero, and then setting d_jkt = 1 if g_jt = g_kt.

The total disadvantage of putting person j in the same group as person k is then $$c_{jk}=\sum _t{w}^T{w}_t^A{d}_{jkt}\text{for}\text{all}j\text{and}k,j\ne k.$$

We multiply this by y_jk, sum this over all persons j and k and put it in the objective function. (If we are using discounting, all of c will not be integer, so non-integral objective function values will be possible.)

Next we need to address the number of persons and points in each group. Since we know that $v^L\le v^U$, we simply wish to minimise $v^U-v^L$, with weight w^N. The same reasoning applies to the number of points and other aspects.

Thus, we obtain the following objective function. $$\text{min}\sum _j\sum _k{c}_{jk}{y}_{jk}+\sum _l{w}_l^P(z_l^U-z_l^L)+w^N(v^U-v^L)$$

(We let c_jj = 0, and can remove y_jj from the model.)

One may note that we only take pairwise effects into account for previous groups. It is conceivable that certain subgroups of three or more persons may have other effects that what is measured by this. These factors were not possible to take into account when this was done by hand. What is possible in this model is to introduce a new aspect with the single purpose of keeping three or more persons apart, by letting a_lj = 1 for those persons and a_lj = 0 for the others, similarly to what was done for gender. In general, this optimisation model allows taking more aspects into account then what is possible by hand.

Let us sum up the mathematical model.

(1) $$\begin{array}{cc}\min \sum _j\sum _k{c}_{jk}{y}_{jk}+\sum _l{w}_l^P(z_l^U-z_l^L)+w^N(v^U-v^L)& \\ \mathrm{s}.\mathrm{t}.\sum _i{x}_{ij}=1\forall j\end{array}$$(1) (2) $$\begin{array}{lllllll}& & y_{jk}-x_{ij}-x_{ik}& \ge & -1& \forall j,k,i& \end{array}$$(2) (3) $$\begin{array}{ccccccc}& & v_i-\sum _j{x}_{ij}& =& 0& \forall i& \end{array}$$(3) (4) $$\begin{array}{ccccccc}& & z_{li}-\sum _j{a}_{lj}{x}_{ij}& =& 0& \forall i,l& \end{array}$$(4) (5) $$\begin{array}{ccccccc}& & v^L\le v_i\le v^U& & & \forall i& \end{array}$$(5) (6) $$\begin{array}{ccccc}& & z_l^L\le z_{li}\le z_l^U& \forall i,l& \end{array}$$(6) (7) $$\begin{array}{ccccccc}& & x_{ij}\in \{0,1\}& & & \forall i,j& \end{array}$$(7) (8) $$\begin{array}{ccccccc}& & y_{jk}\in \{0,1\}& & & \forall j,k& \end{array}$$(8) (9) $$\begin{array}{ccccccc}& & z_{li}\ge 0& & & \forall i,l& \end{array}$$(9) (10) $$\begin{array}{ccccccc}& & v_i\ge 0& & & \forall i& \end{array}$$(10) (11) $$\begin{array}{ccccccc}& & z_l^L,z_l^U\ge 0& & & \forall l& \end{array}$$(11) (12) $$\begin{array}{ccccccc}& & v^L,v^U\ge 0& & & & \end{array}$$(12)

The size of the model is as follows. There are mn x-variables, n² y-variables, pm z-variables, m v-variables, plus the $2p+2$ bounds, i.e. a total of $n^2+mn$ binary variables and $(p+1)m+2p+2$ continuous variables. As for the constraints, there are n in the first group and $n^{2}q$ in the second. The following constraints are $(2p+2)m$, of which half are variable upper and lower bounds.

It is also possible to fix some of the bounds v^L, v^U, z^L and z^U. If n is an integer multiple of m, we may fix $v^L=v^U=n/m$ to get groups of equal size, otherwise we may fix $v^L=v^U-1$ so that $v^L\le n/m\le v^U$.

This is a linear mixed integer programming model, with similarities to the generalised assignment problem and bin packing. The more specific part is the repetition, modelled by the y-variables.

3. Constructive heuristics

Preliminary tests (see section 5) reveal that the MIP-model is too hard to be solved by standard MIP-software. (We have tried GLPK and CPLEX.) Therefore we have developed a few constructive heuristics for finding feasible, hopefully good, solutions.

The heuristics sequentially build up a feasible solution, by allocating one person at a time to a group. Only information about the previously allocated persons are taken into account.

We start by sorting the persons in order based on the points. Then, we allocate the best person first, then the second best, and so on. In each step, when considering a certain person, we calculate penalties for the existing groups based on c, i.e. add a penalty if the previously allocated persons in a group has been in the same group as the person in question in earlier time periods. This is heuristic A.

In heuristics B, C and D, we also add penalties based on the number of persons in each group, and the total number of points in each group etc, as described below.

Let $J\subseteq 1,\dots ,n$ be the persons for which the group allocation has been done, and let α_j be the group person j is allocated to. Also, let $J_i\subseteq J$ be the set of persons that are allocated to group i, i.e. $J_i=\{j:{\alpha }_j=i\}$.

The measures to keep into account are the following.

${\overline{v}}_i=\left|J_i\right|$ for all i (the number of persons in each group)

${\overline{z}}_{li}=\sum _{j\in J_i}{a}_{lj}$ for all i and l (the measure of aspect l in each group)

${\overline{r}}_i=\sum _{j\in J_i}\sum _{k\in J_i,k\ne j}{c}_{jk}$ for all i (the total repetition in each group)

With these, we sum up a total cost for allocating person j to group i as follows. $${\overline{t}}_i={\overline{r}}_i+{\overline{s}}_i\text{for}\text{all}i$$ where ${\overline{s}}_i$ is given below, in different ways for the different heuristics. Then we simply choose the group that yields the minimal total cost. $$\widehat{i}={\text{argmin}}_i{\overline{t}}_i$$

After this we set $J=J\cup j,J_{\widehat{i}}=J_{\widehat{i}}\cup j$, ${\alpha }_j=\widehat{i}$, and repeat for the next person.

In heuristic A, we set ${\overline{s}}_i=0$.

In heuristic B, we use the following, inspired by the objective function. $${\overline{s}}_i=w^N{\overline{v}}_i+\sum _l{w}_l^P{\overline{z}}_{li}\text{for}\text{all}i$$

In heuristic C, we do a more elaborate evaluation of including person j in group i for the numbers and other aspects. If the group has less than the maximal number of persons, i.e. if ${\overline{v}}_i<{\overline{v}}^U$, then adding a person to the group does not increase the maximal number of students in a group. Then, the penalty is set to zero. If ${\overline{v}}_i={\overline{v}}^U$, then adding a person to the group will increase the maximal number of students in a group, and the penalty will be w^N. Furthermore, if the number of persons in the group is equal to the minimal number, and all other groups have more persons, i.e. if ${\overline{v}}_i={\overline{v}}^L$ and ${\overline{v}}_k>{\overline{v}}^L$ for all $k\ne i$, then the minimal number of persons in a group will increase, which is good. Then, we set the penalty to $-w^N$.

The other aspects are handled similarly, but is slightly more complicated, since the coefficient a_lj may be other than zero or one. If ${\overline{z}}_{li}+a_{lj}\le {\overline{z}}_l^U$ (and ${\overline{z}}_{li}>{\overline{z}}_l^L$), then the penalty will be zero, while if ${\overline{z}}_{li}+a_{lj}>{\overline{z}}_l^U$, we use the penalty $w_l^P{a}_{lj}$. If ${\overline{z}}_{li}={\overline{z}}_l^L$, and ${\overline{z}}_{lk}>{\overline{z}}_l^L$ for all $k\ne i$, we use the penalty $-w_l^P{a}_{lj}$.

Therefore, in heuristic C, we let $L_i^U=\{l:{\overline{z}}_{li}+a_{lj}>{\overline{z}}_l^U\}$ and $L_i^L=\{l:{\overline{z}}_{li}={\overline{z}}_l^L\text{and}{\overline{z}}_{lk}>{\overline{z}}_l^L\text{for}\text{all}k\ne i\}$, and calculate

${\overline{s}}_i^P=\sum _{l\in L_i^U}{w}_l^P{a}_{lj}-\sum _{l\in L_i^L}{w}_l^P{a}_{lj}$ for all i.

Furthermore, for each i, we let ${\overline{s}}_i^N=w^N$ if ${\overline{v}}_i={\overline{v}}^U$, ${\overline{s}}_i^N=-w^N$ if ${\overline{v}}_i={\overline{v}}^L$ and ${\overline{v}}_k>{\overline{v}}^L$ for all $k\ne i$, and ${\overline{s}}_i^N=0$ otherwise. We then use $${\overline{s}}_i={\overline{s}}_i^N+{\overline{s}}_i^P\text{for all}i$$

In heuristic D, we take this further and calculate the exact increase/decrease of the bounds for the aspects. For the numbers, there is no difference, but for the other aspects, we find the following. If ${\overline{z}}_{li}+a_{lj}>{\overline{z}}_l^U$, then the upper bound will not increase by a_lj, but only by ${\overline{z}}_{li}+a_{lj}-{\overline{z}}_l^U$, so the penalty will be $w_l^P({\overline{z}}_{li}+a_{lj}-{\overline{z}}_l^U)$.

Furthermore, the increase of the lower bound will be ${\overline{z}}_{li}+a_{lj}-{\overline{z}}_l^L$, so the penalty will be $-w_l^P({\overline{z}}_{li}+a_{lj}-{\overline{z}}_l^L)$.

So in heuristic D, we use $${\overline{s}}_i^P=\sum _{l\in L_i^U}{w}_l^P({\overline{z}}_{li}+a_{lj}-{\overline{z}}_l^U)-\sum _{l\in L_i^L}{w}_l^P({\overline{z}}_{li}+a_{lj}-{\overline{z}}_l^L)\text{for}\text{all}i.$$

Otherwise, we use the same values as in heuristic C.

A partly manual version of the heuristics has been constructed. The difference is only that the allocation is made by the user. The method loops over the persons, highest points first, presents the current situation (of the partly fixed solutions, ${\overline{v}}_i,{\overline{z}}_{li},{\overline{r}}_i$ and ${\overline{t}}_i$ for each i) and asks the user to decide in which group to put the person. This is possible as long as the number of groups is not to large. In our real life case m is around 5, and we believe that the user will be able to quickly scan five values. It is also possible for the user to deviate from the given weights by taking certain aspects more into account, and to take other (non-numerical) aspects into consideration.

4. Local search and metaheuristics

It is also possible to use metaheuristics on the problem, and we have chosen tabu search, Glover (1989), Glover (1990), and simulated annealing, Kirkpatrick, Gelatt, and Vecchi (1983), Černý (1985). Considering neighbourhoods for local search, we can use move, i.e. moving a person from one group to another, and swap, i.e. swapping groups between two persons. We have implemented the following methods with these two neighbourhoods.

Method 20: Heuristic A.

Method 21: Start by heuristic A. Then check all move-neighbours once, directly do all changes that yield improvement.

Method 22: Start by heuristic A. Then check all swap-neighbours once, directly do all changes that yield improvement.

Method 23: Start by heuristic A. Then check all move-neighbours repeatedly, doing all changes that yield improvement, until no more improvement is obtained.

Method 24: Start by heuristic A. Then check all swap-neighbours repeatedly, doing all changes that yield improvement, until no more improvement is obtained.

Method 25: Start by heuristic A. Then use methods 23 and 24 mixed, i.e. iterate between move and swap moves, doing all changes that yield improvement, until no more improvement is obtained.

Method 26: Start by heuristic A. Then run tabu search with moves. In each step the best move is made.

Method 27: Start by heuristic A. Then run tabu search with swaps. In each step the best swap is made.

Method 28: Start by heuristic A. Then run simulated annealing with moves.

Method 29: Start by heuristic A. Then run simulated annealing with swaps.

Methods 30, …, 39 are the same as 20, …, 29, but initiated with heuristic B.

Methods 40, …, 49 are the same as 20, …, 29, but initiated with heuristic C.

Methods 50, …, 59 are the same as 20, …, 29, but initiated with heuristic D.

Methods 60, …, 69 are the same as 20, …, 29, but initiated with a random solution.

5. Computational tests

The model is implemented in GMPL and solved by glpsol. Calculation of the coefficients d and c is done by a code in Python, which also reads indata in a simple format and writes an indata file in GMPL/AMPL-format. The heuristics are also implemented in Python. Some tests are also done with CPLEX, just in order to check if a better code easily solves all problems of interest.

The main tests are run on computer 1, which is an Acer Aspire X3 X3995, Intel Core i7-3770, 3.4 GHz, running Linux, Fedora Core 19, and the CPLEX-tests are run on computer 2, which is a HP Compaq 8100 Elite, Intel Core i5-650 3,2 GHz, running Linux, CentOS 6. Only one processor was used during the runs with the Python code and GLPK, while CPLEX uses more (up to 4). The CPU-time was limited to 60 seconds.

The tabu search was made with a tabu list length of 7, and 100 iterations. For simulated annealing, the starting temperature was 100, the cooling factor 0.7, and 50 outer iterations was made, each with 20 inner iterations with the same temperature. We did not attempt to optimise the values of these parameters, so it is likely that the results can be improved somewhat by tuning of the methods. (Therefore, we believe that a comparison to GLPK is more relevant than to CPLEX or another highly optimised code.)

5.1. Test problems

Some artificial test problems of different sizes were generated and solved. There is only one aspect in the first set of instances, namely the points, which were randomly generated between 10 and 100. The group allocation in the first of the previous time periods was to put person 1 in group 1, person 2 in group 2, …person m in group m, person m + 1 in group 1, person m + 2 in group 2, etc. The subsequent allocations were random permutations of the first. The parameter values are $w^P=10,w^N=10$ and $w^T=100$, and we use discounting. The maximal size of these instances is n = 35, m = 5 and q = 4, which is the approximate size of the real life instance we wish to solve.

The second set of test problems contains more instances of different sizes. They are similar to the first, but with other weights, namely $w^P=1,w^N=10$ and $w^T=100$.

The third set of test problems has two aspects (points and gender), but the same parameter setting as the second set. In order to better investigate the limits of our solutions methods, more instances with sizes at the higher end are used. The maximal size of these instances is n = 40, m = 6 and q = 5.

Finally a fourth set of problems contains three real life instances, which however are rather similar.

The two first sets of problems have been used for preliminary tests, mainly to see how far exact optimisation with the MIP-model can go. The third and the fourth sets of problems are considered to be the main tests.

5.2. Computational results

In Table 1, we give the results by the first tests with GLPK on computer 1. The table gives problem size, in the form of n, m and q, as well as the number of rows, columns and binary variables. The number of nodes in the branch-and-bound tree is given, as well as the solution time and the objective function value (rounded). If the CPU-time of 60 seconds was not enough to finish the solution procedure, we report the number of nodes at termination, the remaining nodes + those investigated, as a lower bound on the total number of nodes, and the best integer solution found, as an upper bound on the optimal value.

Table 1. Results by GLPK on the first problem set.

Instance	n	m	q	Rows	Cols	Bin	Nodes	Time	Obj
inst1-1	5	2	2	68	43	35	31	0.0	710
inst1-2	10	3	2	329	140	130	99	0.1	420
inst1-3	12	3	3	463	190	180	2651	2.2	1160
inst1-4	15	4	3	940	297	285	15,497	28.5	420
inst1-5	20	5	3	2051	514	500	≥5394 + 1350	≥60	≤317
inst1-6	30	5	4	4561	1064	1050	≥2271 + 67	≥60	≤3560
inst1-7	35	5	4	6191	1414	1400	≥1240 + 147	≥60	≤5323

Table 2 give the resulting objective function values of the initial constructive heuristics, on computer 1. Here we see that several methods yield the optimal solution to inst1-1, and a couple for inst1-2. Some other heuristics, however, yield solutions that are not very good. For inst-13, inst1-4 and inst1-5, GLPK yields the best solutions, which are optimal for inst1-3 and inst1-4. For inst1-6, method 32 gives the best solution, while for inst1-7, method 22 gives the best solution. Preliminary conclusions are that GLPK cannot solve the larger problems to optimality, and that heuristics using swap seem to be stronger than heuristics using move. The simple methods 20 and 30 may give quite bad solutions, see for example inst1-3 and inst1-4.

Table 2. Results (objective function values) by the heuristics on the first problem set.

Instance	n	m	q	GLPK	M20	M21	M22	M30	M31	M32
inst1-1	5	2	2	710	1150	730	710	710	710	710
inst1-2	10	3	2	420	700	700	420	810	810	420
inst1-3	12	3	3	1160	2340	1530	1230	1960	1780	1450
inst1-4	15	4	3	420	1743	1146	673	1310	1310	693
inst1-5	20	5	3	≤317	2093	1053	623	983	983	476
inst1-6	30	5	4	≤3560	3573	3020	3080	3390	3313	2836
inst1-7	35	5	4	≤5323	6193	4890	4606	5296	5183	4620

Table 3 give the results for CPLEX (on computer 2). Here we see that CPLEX is better than GLPK, but not good enough to solve the larger problems to optimality in 60 seconds. (There is one unit difference in the optimal objective function value for some instances, which is due to different rounding in the output.)

Table 3. Results by CPLEX, computer 2, on the first problem set.

Instance	n	m	q	Nodes	Time	Obj
inst1-1	5	2	2	0	0.0	710
inst1-2	10	3	2	31	0.07	420
inst1-3	12	3	3	1512	0.14	1159
inst1-4	15	4	3	802	0.47	419
inst1-5	20	5	3	32,970	35.82	233
inst1-6	30	5	4	≥58,006	≥60	≤2799
inst1-7	35	5	4	≥35,396	≥60	≤4799

A conclusion of the firsts tests is that problems of realistic size cannot be solved by GLPK or CPLEX. Tests allowing more than 60 seconds reveal that the time is increasing quickly, and solving for example inst1-5 would take several hours. Another conclusion is that the initial heuristics sometimes yield good solutions, but sometimes quite bad.

The second set of tests have $w^P=1,w^N=10$ and $w^T=100$, and discounting. The weight on the points is more realistic than in the first set, so we rely a bit more on these tests. Here we only made tests with the MIP-model, which again were unable to solve problems of interesting sizes. The results can be found in Tables A1 and A2 in the Appendix. We see that CPLEX is better than GLPK, but not efficient enough. Both codes run into difficulties when the number of persons is around 20 or more. Another observation is that inst2-7 is easier to solve than inst2-6, although inst2-7 has one group more, and thus is a larger problem. The same holds for inst2-8 and inst2-9.

The third set of instances has two aspects, the points and the gender (or any other binary measure). In Table 4, we give the results from GLPK (on computer 1). We give n, m, q, p, followed by the number of rows and columns of the MIP-model, the total number of simplex iterations and the number of branch-and-bound nodes that were investigated. We give two objective function values, the first, obj1, is the optimal value, if optimality was verified, which can be seen by a solution time less than 60, or the best upper bound that was found in 60 seconds. The second value is only given if optimality is not verified, and is the best lower bound that was obtained in 60 seconds.

Table 4. Results by GLPK on the third problem set.

Instance	n	m	q	p	Rows	Cols	Iter	Nodes	Obj1	Obj2	Time
inst3-1	10	3	2	2	339	145	6033	453	377	0.0	0.2
inst3-2	10	3	2	2	339	145	1648	99	339	0.0	0.1
inst3-3	12	3	3	2	473	195	30,366	1709	1126	0.0	1.5
inst3-4	12	3	4	2	473	195	28,729	1311	1269	0.0	1.2
inst3-5	15	3	4	2	719	285	244,979	11,157	2534	0.0	17.7
inst3-6	17	3	4	2	913	355	624,661	5264	3466	2870.5	60.0
inst3-7	17	4	4	2	1211	375	309,396	9629	609	0.0	26.0
inst3-8	20	4	4	2	1658	498	498,447	1118	1728	388.0	60.0
inst3-9	21	4	4	2	1823	543	434,746	874	2251	303.9	60.0
inst3-10	23	4	4	2	2177	639	341,924	409	3049	356.5	60.1
inst3-11	23	5	4	2	2715	665	325,924	885	539	52.0	60.1
inst3-12	25	5	4	2	3197	771	265,773	323	839	65.0	60.2
inst3-13	27	5	4	2	3719	885	225,309	446	1781	108.5	60.1
inst3-14	29	5	4	2	4281	1007	186,192	155	2372	105.0	60.2
inst3-15	30	5	4	2	4577	1071	167,016	41	2666	22.6	60.2
inst3-16	32	5	4	2	5199	1205	145,616	28	3539	31.2	60.3
inst3-17	35	5	4	2	6207	1421	127,429	141	4712	113.2	60.4
inst3-18	36	6	4	2	7868	1536	112,455	96	1433	0.0	60.5
inst3-19	38	6	5	2	8758	1696	93,825	164	2558	10.0	60.6
inst3-20	40	6	5	2	9696	1864	91,725	11	3779	0.0	60.8

Some reflections of Table 4 are that increasing q, as done between inst3-3 and inst3-4 does not seem to increase the difficulty of the problem. Increasing n, as between inst3-5 and inst3-6, definitely makes the problem harder to solve. And again we find that increasing m, as between inst3-6 and inst3-7, may make the problem easier to solve.

In Tables A3–A7 in the Appendix, we give the results for all the heuristics, methods 20 - 69. We have also added the results from GLPK, as method 1, for comparison. The tables give the instance name on top, the name of the method, followed by the objective function value and the solution time for each instance. All these test are made on computer 1.

Here we find that for small problems, some heuristics give the optimal solution in a fraction of the time needed by GLPK. For larger problems, some of the heuristics yield better solutions in much shorter time. In no case does GLPK yield a better solution than all heuristics (in 60 seconds).

In more detail, we find the following. For the smallest problem, inst3-1, many methods yield the optimal solution (377). The fastest of those is method 22 (as well as 32, 42, 52 and 62), which only needs 0.02 seconds. For inst3-2 even more methods yield the optimal value (339), and here methods 41 and 50 are the fastest. Similar results hold for inst3-3 and inst3-4, where the best method 62 (and 32) yield the optimal solution in 0.03 seconds.

For problems up to this, GLPK is a viable option. However, for inst3-5 and upwards, GLPK needs more time than the alternatives. For inst3-5 only four methods give the optimal value (2534), with method 49 as the fastest, 0.57 seconds.

For inst3-6, GLPK failed to find the optimum within 60 seconds. The best solution was found by five methods, of which method 64 is the fastest, 0.17 seconds.

Inst3-7 is slightly easier than inst3-6, and here GLPK and six other methods give the optimal solution. Method 62 does this in 0.12 seconds, while GLPK needs 26 seconds.

From inst3-8 and upwards, GLPK fails to find and/or verify the optimum within 60 seconds, so for these problems, we do not know the optimal solution. For inst3-8, method 57 gives the best solution in 17.63 seconds. One interesting question is how fast a method can yield a solution that is better than what GLPK gave in 60 seconds. Here, method 64 does this in 0.36 seconds.

For inst3-9, method 37 gives the best solution in 21.33 seconds. Here 29 methods give better solutions than GLPK, often in much shorter time, the fastest being 0.21 seconds for methods 32 and 42.

For inst3-10, method 47 gives the best solution, in 29.29 seconds. Also, here many (32) methods give better solutions than GLPK, and the fastest is 0.06 seconds for method 61.

For inst3-11, method 57 gives the best solution, in 30.18 seconds. Here, the GLPK-solution is rather good, and only 6 methods find better solutions.

For inst3-12, method 67 gives the best solution, in 40.61 seconds, while method 32 finds a better solution than GLPK in 0.40 seconds.

For inst3-13, method 67 gives the best solution, in 53.10 seconds, while methods 22 and 32 give a better solution than GLPK in 0.52 seconds. For inst3-14, method 37 gives the best solution, in 60 seconds. Here, the method is terminated because of the time limit of 60 seconds. Even so, it found a much better solution than GLPK. A slightly better solution than GLPK was found in 0.02 seconds by method 50. For these more difficult problems, we find that GLPK does not find a good solution at all within 60 seconds, so it is easy for a heuristic to find a better one.

For inst3-15, method 65 gives the best solution, in 2.71 seconds. For inst3-16, method 67 gives the best solution, in 60 seconds. For both these instances, a simple method as 20 finds a better solution than GLPK in 0.02 seconds.

For inst3-17, method 64 gives the best solution, in 5.23 seconds. For inst3-18, method 47 gives the best solution, in 60 seconds. For inst3-19, method 47 gives the best solution, in 60 seconds. For inst3-20, method 67 gives the best solution, in 60 seconds. For these harder problem, the stronger heuristics are terminated because of the maximal time allowed.

Concerning the comparison to GLPK, we find that for easy problems, is is not that hard to find the optimal solution. For hard problems, GLPK gives a quite bad solution in 60 seconds, so then it is easy to find a better solution. In intermediate cases, GLPK finds a rather good solution, so the heuristics need to work more to find a better solution, and some of them fail to find a better solution. However, we can note that in all cases, some heuristic finds a better or equal solution in much shorter time.

Summing up the number of times a method gives the best solution in shortest time (of the ones found), we get the following result. One best solution was found by the methods 22, 41, 42, 49, 50, 52 and 65. Many of these were best only for the smallest problems. Two best solutions were found by methods 32, 57 and 64. Three best solutions were found by method 47. Four best solutions were found by methods 62 and 67. Five best solutions were found by method 37, and this is the maximum, so by this measure, method 37 would be a winner. However, methods 47 and 67 are also rather strong.

All in all we find that methods ending with 7, i.e. use tabu search with swaps, are quite strong. They take more time than many other heuristics, but yield better solutions.

A comparison of the simple and very fast one-shot heuristics 20, 30, 40, 50 and 60 is made in Table 5. The time is in principle negligible for all of them, so the question is simply which one gives the best solutions. Obviously the random solution (60) is worse by far (which however does not stop it from giving good final results of the metaheuristics). Apart from this, the conclusions are not very evident. Summing up, method 20 gives the best solution in 4 cases, method 30 in 4 cases, method 40 in 10 cases and method 50 in 5 cases. Thus each method has its merits, but method 40 seems to be slightly better than the others. It is interesting to see that the simple method 20 is almost as good as the more advanced method 50.

Table 5. Results for one-shot heuristics.

	inst3-1		inst3-2		inst3-3		inst3-4
Method	Obj	Time	Obj	Time	Obj	Time	Obj	Time
20	396.00	0.00	449.00	0.00	1217.00	0.00	1413.67	0.00
30	387.00	0.01	339.00	0.01	1207.67	0.00	1441.00	0.01
40	378.00	0.00	359.00	0.00	1345.00	0.00	1356.67	0.01
50	387.00	0.00	339.00	0.00	1401.67	0.01	1441.00	0.00
60	835.00	0.00	968.00	0.00	1362.00	0.00	2414.00	0.00
	inst3-5		inst3-6		inst3-7		inst3-8
	Obj	Time	Obj	Time	Obj	Time	Obj	Time
20	2760.67	0.00	3821.00	0.00	1154.33	0.01	2069.33	0.01
30	2682.67	0.01	3809.00	0.01	1080.67	0.00	2391.00	0.01
40	2644.67	0.01	3809.00	0.00	1290.33	0.00	2095.67	0.02
50	2682.67	0.00	3933.00	0.00	1080.67	0.01	2095.67	0.01
60	2940.00	0.00	5191.00	0.00	2676.67	0.00	3071.00	0.01
	inst3-9		inst3-10		inst3-11		inst3-12
	Obj	Time	Obj	Time	Obj	Time	Obj	Time
20	2589.00	0.00	3151.67	0.00	1018.67	0.01	1281.33	0.00
30	2517.67	0.01	3632.33	0.02	872.67	0.01	1120.67	0.01
40	2386.33	0.01	3087.67	0.01	816.67	0.01	904.33	0.02
50	2421.00	0.01	3238.67	0.01	872.67	0.01	1542.67	0.01
60	3748.00	0.01	6138.67	0.00	3058.33	0.00	2410.67	0.00
	inst3-13		inst3-14		inst3-15		inst3-16
	Obj	Time	Obj	Time	Obj	Time	Obj	Time
20	2090.33	0.00	2511.67	0.01	2533.00	0.01	3366.00	0.02
30	2222.33	0.02	2741.00	0.02	2911.67	0.02	3848.00	0.02
40	2292.33	0.01	2642.67	0.02	2945.67	0.01	3274.33	0.02
50	2292.33	0.02	2367.00	0.02	2621.00	0.02	3861.00	0.02
60	4147.33	0.00	5221.67	0.00	5093.00	0.00	6909.67	0.00
	inst3-17		inst3-18		inst3-19		inst3-20
	Obj	Time	Obj	Time	Obj	Time	Obj	Time
20	4666.33	0.01	2000.33	0.01	2746.67	0.02	3503.33	0.02
30	4657.00	0.02	2190.67	0.03	2809.33	0.03	3504.67	0.03
40	4537.67	0.03	1855.67	0.03	2699.00	0.03	3589.33	0.02
50	4530.33	0.03	1846.67	0.03	3693.00	0.03	3943.67	0.04
60	7889.00	0.00	6052.33	0.01	6155.33	0.01	8084.00	0.00

Finally, tests were made on real life data. The first problem has n = 31, m = 5, q = 4 and p = 1, which yields 4868 rows, 1130 columns, 15,284 non-zeros and 1116 binary variables in the MIP-model. The second problem has n = 30, which gives 4562 rows, 1064 columns, 14,327 non-zeros and 1050 binary variables. The third problem has p = 2 (points and gender), but is otherwise similar to the first problem. Table 6 gives the results of these tests for GLPK, and Table A8 in the Appendix gives the results for the heuristics.

Table 6. Results by GLPK, computer 1, on the fourth problem set.

Instance	n	m	q	p	Rows	Cols	Iter	Nodes	Obj1	Obj2	Time
instre1	31	5	4	2	4868	1130	163,134	357	2592	228.7	60.3
instre2	30	5	4	1	4562	1064	173,501	128	2404	194.4	60.2
instre3	31	5	4	2	4883	1137	162,922	272	2986	223.7	60.3

For all of these three problems, method 20 gives a better solution in 0.01 seconds than GLPK did in 60 seconds. These three problems also have in common that method 37 yields the best solution (using all the 60 seconds).

For the first problem, the objective function value of GLPK was 2592 after 60 seconds, while heuristic 20 yields objective function value 2530 after 0.01 second. Local search with move-neighbourhood (method 21) decreased it slightly to 2526. Local search with swap-neighbourhood (method 22) decreased it to 2493. Continued local search (methods 23 and 24) does not improve these values, but using both neighbourhoods (method 25) improves it to 2323. Tabu search with move-neighbourhood (method 26) gave the value 2396, while tabu search with swap-neighbourhood (method 27) decreased it to 2129. Using simulated annealing (instead of tabu search) (methods 28 and 29) yields 2478 and 2530, so here tabu search with swaps is the best method.

Starting with heuristic B (methods 30-39) gives similar results, most solutions somewhat worse, but slightly better for method 37. Starting with heuristic C (methods 40-49) gives in general worse solutions, and the same applies for heuristic D (methods 50-59) as well as starting with a random solution (methods 60-69).

Similar results were obtained for the second and third problems.

Methods 30 and 20 are very similar to the procedure used when this is done by hand, and it is interesting to see that both these give a better solution than GLPK in a much shorter time. For these problems, the simple heuristics give better solutions than GLPK very quickly, and tabu search improves these solutions further. However, in a fair amount of cases, a random starting solution (which may be very bad) enables the metaheuristics to find even better solutions.

5.3. Summary of the computational tests

We find that for small instances, a MIP-solver can be used, but when the size grows, it is better to use heuristics. For large problems, even the simplest heuristics produce better solutions than the MIP-solver. Further improvement can be obtained by many of the methods, but the best method seems to be tabu search with swap neighbourhood. However, the performance of simulated annealing can probably be improved by tuning the parameters.

Considering the starting solution, it is interesting to see that although method 20 sometimes gives lower objective function value than method 30, the final result is often worse than starting by 30. Also, random starting points can yield good results. Heuristics C and D can be seen as more intricate extensions of A and B, so it is slightly surprising to see that they are not always better.

6. Practical use

As mentioned in the introduction, the formation of base groups has previously been done manually, five times each year. At each occasion two or three teachers were present and it took approximately two hours. The method used was a simplified version of heuristic A, in the following sense. Penalities were not explicitely calculated. An attempt to minimise repetition was made by considering previous groups. By allocating the sorted list of students in a cyclic manner, the best students were not allocated to the same group.

We cannot really compare our methods with the manual method, but we know that method 20 is better than the manual, so a comparison between method 20 and method 37 (which we here pick as the best one) gives a lower bound on the improvement obtained. The relative improvements are shown in Table 7.

Table 7. Comparison between methods 20 and 37.

Instance	M 20	M 37	Impr
inst3-1	396	377	0.05
inst3-2	449	339	0.32
inst3-3	1217	1126	0.08
inst3-4	1413	1269	0.11
inst3-5	2760	2544	0.08
inst3-6	3821	3455	0.10
inst3-7	1154	608	0.89
inst3-8	2069	1791	0.15
inst3-9	2589	2134	0.21
inst3-10	3151	2955	0.06
inst3-11	1018	381	1.67
inst3-12	1281	639	1.00
inst3-13	2090	1263	0.65
inst3-14	2511	1841	0.36
inst3-15	2533	2196	0.15
inst3-16	3366	2973	0.13
inst3-17	4666	4244	0.09
inst3-18	2000	677	1.95
inst3-19	2746	1983	0.38
inst3-20	3503	2628	0.33
intre1	2530	2119	0.19
intre2	2243	1881	0.09
intre3	2552	2152	0.18

We see that the size of the improvements vary much, but the average improvement is 40%. In other words, letting the computer work in 60 seconds gives in average 40% better results than manual work for a couple of hours.

The code was supplied with an interface in Python and Tkinter that allows selection of solution method and changing of all parameters. The groups and all names are displayed on the screen (which is possible for 30 students and 5 groups but not much more). In addition, manual changes, such as inserting students in groups, removing students, fixing parts of the solution etc. are possible.

First the code was used by myself for a couple of years, yielding groups for all semesters for the IT-programme, and also for the psychology programme.

Then, the code was made available to the teachers responsible for the semesters, together with a manual. It turned out that removing many possibilities from the interface improved usability for inexperienced users (albeit university lecturers). By now all groups are made by the responsible teachers themselves. They are able to test different values of the parameters and observe the differences in the result.

In practice, this tool has enabled fast decisions, so that more recent data can be used. There are exams just before the groups should start, but previously the results of these exams could not be included, since the grouping was planned before the exams were corrected. Now the grouping only takes 10 minutes, so indata have a better quality.

Futhermore, there are sometimes defections, i.e. students leaving at short notice. Now more information of that type can be included when doing the grouping.

An interesting aspect is that a good optimisation tool such as this puts focus on the quality of the indata. Previously, the grouping was done so approximately that inaccurate indata was not considered a problem. There was never time to reflect on this when using the manual method. Now everyone can see how a change in indata affects the solution.

A general opinion is that the groups work well, and no complaints have been made. If there were better ways of obtaining feedback, one could put more effort in trying to find the best values for the weights w.

In the psychology programme (where there are more girls than boys), it turned out that one does not want a single boy in a group. Instead there should be either zero or at least two. This introduced a complicated non-convexity, which in theory requires further development of the model and methods.

However, in practice it was easier to include a possibility of fixing one gender and optimise over the other. First, an optimal allocation of only the (few) boys were made to the number of groups that were needed, and then this solution was fixed and the girls added. It meant deciding a priori the number of groups that should consists of only girls.

7. Conclusions and future work

We have formulated the problem of forming suitable groups as a MIP-problem. Computational tests reveal that standard MIP-codes, such as GLPK and CPLEX, cannot solve problems of realistic size.

We present a couple of constructive heuristics for the problem, and describe how metaheuristics, such as tabu search and simulated annealing, can be used to improve the solutions. Computational results are presented, showing that tabu search with swap neighbourhood is a good method for the problem.

The code, together with an interface in Python and Tkinter that allows manual changes, has been used when forming certain student groups at Linköping University. It has saves much manual time, and produces good groups, as reported by the users.

The code is presently not public domain, but such a version might be made later. Also, the test data may be available. Please contact the author, [email protected], for more information.

A direction for future research is to model and handle non-convexities, for example that a group should contain either zero or at least two of a certain type of students. Another obvious direction is to improve the solution methods. Furthermore, the current interface is mostly suitable for research, since it allows changing all method parameters. Another version for users only interested in the result, not in comparing different solution methods, will be made. That version may also contain a more general/standardized input format. Finally we are searching for better ways of evaluating the final groups, so that feedback can enable further improvements.

In practice, this tool has enabled fast decisions, so that more recent and accurate data can be used. The speed also enables testing of different weights and even new aspects.

Disclosure statement

No potential conflict of interest was reported by the authors.

Appendix

Table A1. Results by GLPK, computer 1, on the second problem set.

Instance	n	m	q	Rows	Cols	Bin	Nodes	Time	Obj
inst2-1	5	2	2	69	43	32	5	0.0	317
inst2-2	10	3	2	330	140	130	77	0.0	331
inst2-3	12	3	3	464	190	180	1531	1.3	1110
inst2-4	13	2	3	365	203	195	375	0.3	5512
inst2-5	13	3	5	540	218	201	2435	2.4	1850
inst2-6	15	3	4	710	280	270	197,554	30.5	2506
inst2-7	15	4	4	941	297	285	5221	9.6	333
inst2-8	20	4	4	1646	492	475	≥7822 + 2075	≥60	≤1838
inst2-9	20	5	4	2052	508	500	≥5163 + 1186	≥60	≤222
inst2-10	24	5	4	2936	710	696	≥4095 + 357	≥60	≤872
inst2-11	27	5	4	3704	872	864	≥2598 + 401	≥60	≤1600
inst2-12	30	5	4	4562	1064	1050	≥2142 + 233	≥60	≤2646
inst2-13	33	5	4	5510	1268	1254	≥1627 + 84	≥60	≤3849
inst2-14	35	5	4	6192	1414	1400	≥1266 + 106	≥60	≤4751

Table A2. Results by CPLEX, computer 2, on the second problem set.

Instance	n	m	q	Rows	Cols	Bin	Nodes	Time	Obj
inst2-1	5	2	2	69	43	32	0	0.02	317
inst2-2	10	3	2	330	140	130	0	0.04	331
inst2-3	12	3	3	464	190	180	516	0.21	1109
inst2-4	13	2	3	365	203	195	319	0.16	5511
inst2-5	13	3	5	540	218	201	811	0.41	1849
inst2-6	15	3	4	710	280	270	9743	7.04	2505
inst2-7	15	4	4	941	297	285	332	0.23	332
inst2-8	20	4	4	1646	492	475	≥72,552	≥60	≤1713
inst2-9	20	5	4	2052	508	500	2173	2.72	212
inst2-10	24	5	4	2936	710	696	≥50,325	≥60	≤550
inst2-11	27	5	4	3704	872	864	≥70,205	≥60	≤1194
inst2-12	30	5	4	4562	1064	1050	≥60,649	≥60	≤2274
inst2-13	33	5	4	5510	1268	1254	≥44,907	≥60	≤3477
inst2-14	35	5	4	6192	1414	1400	≥37,273	≥60	≤4385

Table A3. Results for instances inst3-1, inst3-2, inst3-3 and inst3-4.

	inst3-1		inst3-2		inst3-3		inst3-4
Method	Obj	Time	Obj	Time	Obj	Time	Obj	Time
1	377.00	0.20	339.00	0.10	1126.00	1.50	1269.00	1.20
20	396.00	0.00	449.00	0.00	1217.00	0.00	1413.67	0.00
21	396.00	0.01	423.00	0.01	1147.00	0.01	1305.00	0.01
22	377.00	0.02	356.00	0.02	1199.00	0.03	1405.00	0.03
23	396.00	0.01	423.00	0.01	1147.00	0.02	1305.00	0.02
24	377.00	0.03	356.00	0.04	1199.00	0.07	1405.00	0.06
25	377.00	0.04	339.00	0.07	1126.00	0.07	1269.00	0.08
26	377.00	0.57	342.00	0.55	1126.00	0.78	1290.00	0.81
27	377.00	1.64	339.00	1.73	1196.00	2.79	1405.00	2.98
28	379.00	0.34	339.00	0.35	1126.00	0.42	1290.00	0.42
29	377.00	0.33	356.00	0.35	1199.00	0.43	1389.67	0.42
30	387.00	0.01	339.00	0.01	1207.67	0.00	1441.00	0.01
31	387.00	0.01	339.00	0.01	1207.67	0.02	1441.00	0.02
32	377.00	0.02	339.00	0.02	1126.00	0.03	1291.00	0.03
33	387.00	0.01	339.00	0.01	1207.67	0.01	1441.00	0.01
34	377.00	0.04	339.00	0.02	1126.00	0.07	1269.00	0.10
35	377.00	0.04	339.00	0.03	1126.00	0.08	1269.00	0.13
36	377.00	0.56	339.00	0.54	1133.00	0.82	1290.00	0.82
37	377.00	1.63	339.00	1.66	1126.00	2.96	1269.00	3.06
38	387.00	0.33	339.00	0.34	1207.67	0.42	1417.00	0.43
39	379.00	0.35	339.00	0.32	1153.00	0.42	1269.00	0.41
40	378.00	0.00	359.00	0.00	1345.00	0.00	1356.67	0.01
41	378.00	0.01	339.00	0.00	1345.00	0.01	1356.67	0.02
42	377.00	0.02	356.00	0.02	1126.00	0.04	1269.00	0.04
43	378.00	0.01	339.00	0.02	1345.00	0.01	1356.67	0.01
44	377.00	0.04	356.00	0.03	1126.00	0.07	1269.00	0.06
45	377.00	0.05	339.00	0.05	1126.00	0.08	1269.00	0.08
46	377.00	0.53	339.00	0.57	1157.00	0.84	1269.00	0.79
47	377.00	1.61	339.00	1.68	1126.00	3.40	1269.00	2.98
48	378.00	0.35	339.00	0.34	1233.00	0.42	1356.67	0.44
49	377.00	0.35	356.00	0.33	1126.00	0.42	1290.00	0.43
50	387.00	0.00	339.00	0.00	1401.67	0.01	1441.00	0.00
51	387.00	0.01	339.00	0.01	1248.67	0.02	1441.00	0.01
52	377.00	0.02	339.00	0.02	1126.00	0.04	1291.00	0.04
53	387.00	0.01	339.00	0.01	1248.67	0.02	1441.00	0.01
54	377.00	0.04	339.00	0.02	1126.00	0.07	1269.00	0.10
55	377.00	0.05	339.00	0.03	1171.00	0.08	1269.00	0.12
56	377.00	0.59	339.00	0.59	1126.00	0.81	1290.00	0.82
57	377.00	1.63	339.00	1.60	1126.00	2.95	1269.00	2.98
58	387.00	0.34	339.00	0.35	1168.00	0.41	1421.00	0.45
59	377.00	0.33	339.00	0.34	1157.00	0.41	1269.00	0.42
60	835.00	0.00	968.00	0.00	1362.00	0.00	2414.00	0.00
61	439.00	0.00	549.00	0.00	1169.00	0.01	1587.00	0.01
62	377.00	0.02	339.00	0.02	1126.00	0.03	1269.00	0.03
63	380.00	0.01	549.00	0.02	1246.00	0.01	1438.00	0.02
64	377.00	0.04	356.00	0.04	1126.00	0.13	1269.00	0.06
65	379.00	0.05	339.00	0.07	1171.00	0.08	1269.00	0.10
66	378.00	0.59	342.00	0.54	1133.00	0.84	1290.00	0.84
67	377.00	1.61	339.00	1.66	1126.00	3.02	1269.00	3.01
68	401.00	0.33	557.00	0.33	1166.00	0.41	1492.00	0.47
69	435.00	0.34	339.00	0.31	1126.00	0.41	1302.00	0.41

Table A4. Results for instances inst3-5, inst3-6, inst3-7 and inst3-8.

	inst3-5		inst3-6		inst3-7		inst3-8
Method	Obj	Time	Obj	Time	Obj	Time	Obj	Time
1	2534.00	17.70	3466.00	60.00	608.67	26.00	1727.67	60.00
20	2760.67	0.00	3821.00	0.00	1154.33	0.01	2069.33	0.01
21	2554.00	0.01	3647.33	0.03	1154.33	0.03	2069.33	0.04
22	2634.67	0.07	3536.00	0.10	614.67	0.11	1846.67	0.18
23	2554.00	0.03	3647.33	0.04	1154.33	0.03	2069.33	0.04
24	2634.67	0.12	3536.00	0.19	608.67	0.30	1846.67	0.34
25	2554.00	0.15	3536.00	0.23	608.67	0.40	1726.67	0.61
26	2536.00	1.35	3467.33	1.84	668.33	2.60	1733.67	3.91
27	2629.67	6.35	3455.33	9.07	608.67	10.46	1808.67	18.66
28	2554.00	0.57	3647.33	0.66	1154.33	0.73	1865.67	0.89
29	2745.00	0.56	3621.00	0.65	727.00	0.73	1811.67	0.92
30	2682.67	0.01	3809.00	0.01	1080.67	0.00	2391.00	0.01
31	2682.67	0.01	3581.33	0.02	1070.00	0.04	2131.33	0.05
32	2575.00	0.07	3536.00	0.09	693.33	0.11	1861.33	0.19
33	2682.67	0.01	3581.33	0.04	907.00	0.10	2070.33	0.12
34	2575.00	0.13	3536.00	0.19	693.33	0.22	1799.67	0.53
35	2575.00	0.16	3508.33	0.23	608.67	0.27	1818.33	0.42
36	2566.00	1.33	3473.33	1.85	805.67	2.69	1733.67	3.89
37	2544.00	5.94	3455.33	9.63	608.67	9.98	1791.67	18.44
38	2682.67	0.54	3569.33	0.69	907.00	0.72	1962.67	0.90
39	2575.00	0.57	3526.33	0.64	788.00	0.81	1836.67	0.90
40	2644.67	0.01	3809.00	0.00	1290.33	0.00	2095.67	0.02
41	2644.67	0.02	3581.33	0.03	1216.00	0.04	2095.67	0.05
42	2566.00	0.06	3536.00	0.10	1045.33	0.12	1759.67	0.18
43	2644.67	0.02	3581.33	0.05	1216.00	0.06	2095.67	0.05
44	2566.00	0.13	3536.00	0.20	1045.33	0.21	1759.67	0.36
45	2566.00	0.15	3508.33	0.22	608.67	0.28	1759.67	0.46
46	2566.00	1.26	3473.33	1.69	735.33	2.76	1787.67	3.70
47	2534.00	6.39	3455.33	9.57	1022.00	10.10	1696.67	17.94
48	2644.67	0.53	3669.00	0.62	889.67	0.75	1970.67	0.96
49	2534.00	0.57	3559.00	0.65	981.33	0.76	1741.67	0.93
50	2682.67	0.00	3933.00	0.00	1080.67	0.01	2095.67	0.01
51	2682.67	0.02	3692.67	0.02	1070.00	0.03	2095.67	0.05
52	2575.00	0.07	3536.00	0.09	693.33	0.11	1759.67	0.19
53	2682.67	0.02	3692.67	0.04	907.00	0.10	2095.67	0.04
54	2575.00	0.12	3536.00	0.18	693.33	0.21	1759.67	0.36
55	2575.00	0.16	3508.33	0.22	608.67	0.24	1759.67	0.45
56	2566.00	1.34	3562.00	1.92	805.67	2.66	1787.67	3.75
57	2544.00	5.85	3455.33	9.05	608.67	10.21	1696.67	17.63
58	2644.67	0.54	3692.67	0.68	817.67	0.76	1927.33	0.88
59	2597.00	0.57	3502.00	0.68	937.00	0.71	1779.67	0.92
60	2940.00	0.00	5191.00	0.00	2676.67	0.00	3071.00	0.01
61	2791.67	0.01	3898.67	0.02	1269.33	0.04	2091.33	0.04
62	2647.00	0.07	3580.33	0.10	608.67	0.12	1729.67	0.18
63	2766.67	0.03	3618.00	0.06	973.00	0.08	2040.67	0.08
64	2587.00	0.12	3455.33	0.17	747.67	0.29	1702.67	0.36
65	2536.00	0.16	3563.33	0.22	807.67	0.25	1756.67	0.41
66	2587.00	1.34	3610.33	1.68	727.00	2.46	1719.67	3.85
67	2534.00	6.65	3472.33	9.92	608.67	10.63	1696.67	17.73
68	2667.00	0.56	3814.67	0.67	804.00	0.70	1987.67	0.86
69	2554.00	0.55	3492.00	0.65	608.67	0.70	1748.67	0.89

Table A5. Results for instances inst3-9, inst3-10, inst3-11 and inst3-12.

	inst3-9		inst3-10		inst3-11		inst3-12
Method	Obj	Time	Obj	Time	Obj	Time	Obj	Time
1	2251.33	60.00	3048.67	60.10	539.00	60.10	839.33	60.20
20	2589.00	0.00	3151.67	0.00	1018.67	0.01	1281.33	0.00
21	2466.33	0.05	3145.67	0.06	1018.67	0.07	1145.33	0.08
22	2214.33	0.22	2980.67	0.28	634.00	0.30	937.67	0.42
23	2416.33	0.13	3145.67	0.10	1018.67	0.08	1145.33	0.19
24	2163.33	0.60	2980.67	0.56	634.00	0.61	937.67	0.81
25	2188.33	1.20	3018.67	1.05	634.00	0.72	672.33	1.44
26	2279.33	4.23	2979.67	5.32	596.67	6.89	621.00	8.80
27	2160.33	19.82	2976.67	28.70	551.67	30.34	968.00	41.70
28	2348.00	1.06	3145.67	1.13	1018.67	1.18	1145.33	1.32
29	2192.33	0.95	3043.67	1.17	614.33	1.14	1097.67	1.26
30	2517.67	0.01	3632.33	0.02	872.67	0.01	1120.67	0.01
31	2412.00	0.05	3465.67	0.06	872.67	0.08	1120.67	0.10
32	2200.33	0.21	3016.67	0.30	731.67	0.33	808.00	0.40
33	2412.00	0.09	3465.67	0.11	872.67	0.07	1120.67	0.09
34	2173.33	0.65	2976.67	0.83	577.00	0.94	808.00	0.84
35	2279.33	0.73	2990.67	0.99	551.67	1.14	808.00	0.96
36	2181.33	4.20	3109.33	5.37	551.67	6.80	827.00	8.32
37	2134.33	21.33	2955.67	28.96	381.67	31.90	639.00	40.33
38	2292.33	0.96	3248.67	1.17	527.33	1.19	1079.33	1.32
39	2150.33	1.07	2977.67	1.07	423.67	1.15	883.67	1.37
40	2386.33	0.01	3087.67	0.01	816.67	0.01	904.33	0.02
41	2371.33	0.05	3085.67	0.05	766.33	0.08	904.33	0.10
42	2215.33	0.21	3032.67	0.31	638.33	0.34	739.00	0.42
43	2266.33	0.18	3085.67	0.11	551.67	0.21	904.33	0.10
44	2199.33	0.69	3032.67	0.56	551.67	0.94	739.00	0.85
45	2196.33	0.77	2984.67	0.95	551.67	1.07	739.00	0.98
46	2201.33	4.15	2982.67	5.22	551.67	7.23	752.00	8.99
47	2176.33	21.26	2949.67	29.29	551.67	31.01	703.00	46.04
48	2386.33	0.93	3087.67	1.09	638.33	1.18	904.33	1.45
49	2160.33	0.96	2965.67	1.14	635.33	1.17	791.67	1.27
50	2421.00	0.01	3238.67	0.01	872.67	0.01	1542.67	0.01
51	2381.00	0.05	3238.67	0.07	872.67	0.09	908.33	0.10
52	2231.33	0.22	3009.67	0.28	731.67	0.34	857.33	0.43
53	2381.00	0.09	3238.67	0.06	872.67	0.08	908.33	0.17
54	2150.33	0.60	3006.67	0.81	577.00	0.93	768.00	1.30
55	2178.33	1.00	2980.67	1.36	551.67	1.17	883.67	0.99
56	2173.33	4.35	2983.67	5.00	551.67	6.67	827.00	8.43
57	2150.33	20.11	2987.67	28.27	381.67	30.18	639.00	42.25
58	2190.33	0.98	3238.67	1.08	872.67	1.22	1162.33	1.36
59	2421.00	0.93	3055.33	1.07	655.33	1.17	808.00	1.46
60	3748.00	0.01	6138.67	0.00	3058.33	0.00	2410.67	0.00
61	2668.00	0.04	2972.67	0.06	1618.33	0.07	1133.00	0.09
62	2241.33	0.23	3007.67	0.29	825.00	0.30	894.33	0.40
63	2613.00	0.13	3014.67	0.37	1051.00	0.28	1242.33	0.24
64	2149.33	0.61	2984.67	0.86	763.00	0.89	591.00	1.18
65	2178.33	1.04	2972.67	0.96	576.67	1.49	692.00	1.44
66	2200.00	4.25	3025.67	5.31	569.00	6.91	686.33	8.31
67	2148.33	20.47	2970.67	27.69	498.67	30.26	511.00	40.61
68	2285.00	1.06	3007.67	1.09	1246.67	1.18	1257.67	1.34
69	2157.33	0.96	3021.67	1.14	573.33	1.11	891.67	1.25

Table A6. Results for instances inst3-13, inst3-14, inst3-15 and inst3-16.

	inst3-13		inst3-14		inst3-15		inst3-16
Method	Obj	Time	Obj	Time	Obj	Time	Obj	Time
1	1780.67	60.10	2372.00	60.20	2666.33	60.20	3538.67	60.30
20	2090.33	0.00	2511.67	0.01	2533.00	0.01	3366.00	0.02
21	2090.33	0.10	2181.00	0.14	2533.00	0.14	3225.00	0.15
22	1503.33	0.52	2003.00	0.69	2418.00	0.78	3366.00	0.94
23	2090.33	0.10	2181.00	0.24	2533.00	0.16	3225.00	0.33
24	1334.33	1.67	2003.00	1.45	2418.00	1.60	3366.00	1.92
25	1397.33	3.24	2181.00	1.62	2418.00	1.77	3050.33	2.17
26	1463.00	10.22	2181.00	11.73	2380.33	14.10	3145.33	15.74
27	1463.00	52.20	2003.00	60.34	2418.00	60.29	3238.33	60.60
28	1872.33	1.61	2511.67	1.62	2533.00	1.73	3233.33	1.97
29	1560.00	1.54	2248.33	1.67	2418.00	1.68	3337.00	1.97
30	2222.33	0.02	2741.00	0.02	2911.67	0.02	3848.00	0.02
31	1985.00	0.12	2715.00	0.15	2911.67	0.15	3589.00	0.18
32	1601.00	0.52	2245.33	0.73	2401.00	0.80	3076.67	1.08
33	1980.00	0.37	2715.00	0.26	2911.67	0.15	3589.00	0.32
34	1320.33	2.09	2245.33	1.38	2236.33	2.34	3062.67	3.18
35	1292.67	2.42	2003.67	1.61	2236.33	3.46	3181.33	3.36
36	1524.33	10.17	2146.67	12.71	2333.00	13.84	3102.33	14.99
37	1263.67	56.03	1841.33	60.48	2196.33	60.21	2973.67	60.10
38	1655.33	1.53	2344.00	1.73	2811.67	1.76	3307.33	1.96
39	1571.67	1.55	2145.33	1.67	2202.33	1.84	3334.67	1.79
40	2292.33	0.01	2642.67	0.02	2945.67	0.01	3274.33	0.02
41	2240.67	0.13	2634.67	0.13	2712.00	0.15	3270.67	0.20
42	1915.33	0.53	2187.33	0.68	2463.00	0.85	3117.67	1.12
43	1912.67	0.50	2634.67	0.27	2698.33	0.40	3270.67	0.32
44	1610.00	2.80	2028.33	2.16	2374.33	2.38	3117.67	1.84
45	1635.67	1.88	1925.67	3.25	2193.33	4.56	3076.67	2.21
46	1524.33	9.63	2093.00	12.77	2256.33	13.64	3270.67	14.98
47	1502.67	50.75	2018.67	60.57	2388.33	60.24	3036.67	60.11
48	1865.00	1.62	2634.67	1.67	2567.00	1.97	3274.33	1.87
49	1900.00	1.43	2190.33	1.79	2369.33	1.85	3177.00	1.95
50	2292.33	0.02	2367.00	0.02	2621.00	0.02	3861.00	0.02
51	2240.67	0.13	2347.33	0.14	2530.33	0.15	3480.00	0.17
52	1915.33	0.52	2293.33	0.68	2327.00	0.79	3036.67	0.94
53	1912.67	0.55	2270.33	0.38	2530.33	0.28	3480.00	0.31
54	1610.00	2.58	2137.33	2.78	2315.00	2.15	3036.67	1.93
55	1635.67	2.05	2000.67	3.35	2229.33	2.02	3127.67	3.32
56	1524.33	10.32	2085.33	12.22	2344.00	13.08	3088.67	15.75
57	1502.67	52.87	1948.67	60.21	2349.00	60.45	3003.67	60.45
58	1602.33	1.47	2270.33	1.71	2490.67	1.83	3256.00	2.03
59	1681.33	1.44	2266.67	1.68	2487.00	1.80	3191.00	1.84
60	4147.33	0.00	5221.67	0.00	5093.00	0.00	6909.67	0.00
61	2572.67	0.11	2996.00	0.14	2759.00	0.14	3784.33	0.17
62	1379.00	0.53	2185.33	0.71	2419.33	0.78	3205.33	0.93
63	2030.00	0.32	2527.67	0.25	2792.33	0.39	3243.33	0.61
64	1471.00	1.10	2041.00	2.73	2420.67	2.36	3077.67	2.82
65	1363.67	1.97	2062.00	2.55	2156.33	2.71	3011.67	3.46
66	1418.67	10.43	1986.00	12.27	2434.67	13.12	3013.67	15.65
67	1211.67	53.10	1940.33	60.02	2186.33	60.40	2969.67	60.66
68	1885.00	1.58	2303.00	1.74	2617.33	1.78	3406.33	1.99
69	1407.00	1.53	2227.67	1.69	2204.00	1.71	3260.67	2.00

Table A7. Results for instances inst3-17, inst3-18, inst3-19 and inst3-20.

	inst3-17		inst3-18		inst3-19		inst3-20
Method	Obj	Time	Obj	Time	Obj	Time	Obj	Time
1	4712.33	60.40	1433.33	60.50	2558.00	60.60	3779.00	60.80
20	4666.33	0.01	2000.33	0.01	2746.67	0.02	3503.33	0.02
21	4596.33	0.22	1825.33	0.25	2653.00	0.29	3221.67	0.35
22	4363.67	1.45	1311.33	1.48	2412.67	1.96	2883.33	2.26
23	4596.33	0.37	1825.33	0.58	2653.00	0.58	3043.00	1.44
24	4293.67	3.94	1274.00	4.36	2412.67	3.90	2866.67	6.66
25	4529.33	2.97	885.33	3.45	2336.33	6.85	2620.33	8.19
26	4295.33	19.93	1100.00	28.70	2099.00	36.21	2694.00	39.00
27	4306.67	60.89	1114.67	61.28	2002.67	61.64	2931.33	61.66
28	4626.33	2.13	1828.67	2.25	2680.00	2.46	3120.00	2.96
29	4470.33	2.13	1390.00	2.39	2560.33	2.61	3105.67	3.10
30	4657.00	0.02	2190.67	0.03	2809.33	0.03	3504.67	0.03
31	4434.33	0.21	2190.67	0.27	2299.33	0.34	3211.67	0.36
32	4469.67	1.39	1182.33	1.55	1994.67	1.97	2820.67	2.28
33	4434.33	0.41	2190.67	0.27	2158.00	0.95	2713.00	1.75
34	4361.67	3.95	1166.00	4.87	1994.67	4.54	2620.00	6.63
35	4284.67	3.21	1166.00	5.31	1976.67	6.56	2752.67	9.64
36	4304.67	20.31	814.33	25.37	2109.00	30.79	2623.00	33.51
37	4244.67	60.69	677.33	60.68	1983.00	61.12	2628.67	61.38
38	4399.00	2.13	1851.00	2.47	2199.33	3.27	3230.00	2.87
39	4418.33	2.24	1166.67	2.37	2360.33	2.60	3194.67	3.17
40	4537.67	0.03	1855.67	0.03	2699.00	0.03	3589.33	0.02
41	4523.33	0.22	1855.67	0.27	2453.67	0.32	3056.67	0.36
42	4443.00	1.38	1374.33	1.50	1995.67	2.03	3134.33	2.30
43	4523.33	0.39	1855.67	0.29	2337.00	0.92	2974.67	1.51
44	4443.00	2.71	1022.67	4.73	1995.67	4.12	2800.33	6.91
45	4277.33	4.31	1022.67	5.83	1880.00	4.49	2665.33	13.98
46	4260.67	18.96	1121.00	29.43	2022.67	33.05	2598.67	33.30
47	4256.67	61.40	648.67	60.96	1843.67	61.16	2713.00	61.91
48	4537.67	2.15	1855.67	2.74	2291.33	2.65	3379.33	2.81
49	4376.67	2.07	931.33	2.52	2136.00	2.59	3223.67	2.77
50	4530.33	0.03	1846.67	0.03	3693.00	0.03	3943.67	0.04
51	4411.33	0.21	1846.67	0.30	2602.00	0.35	3394.67	0.40
52	4308.33	1.35	1149.33	1.50	2368.33	1.85	3093.00	2.20
53	4411.33	0.40	1846.67	0.29	2502.00	0.94	3150.00	1.59
54	4308.33	2.57	1149.33	3.21	2348.33	6.03	2907.33	6.51
55	4284.67	2.87	1149.33	3.53	2063.00	4.57	2701.33	8.00
56	4297.67	19.47	1216.33	27.62	1952.67	31.01	3155.33	35.57
57	4278.67	60.09	734.33	61.44	2242.00	60.31	2836.33	60.34
58	4405.67	2.35	1816.67	2.35	2373.67	2.69	3402.00	2.92
59	4401.33	2.21	1150.00	2.33	2721.00	2.65	3001.00	2.87
60	7889.00	0.00	6052.33	0.01	6155.33	0.01	8084.00	0.00
61	4917.33	0.21	2024.00	0.29	3188.33	0.31	3201.00	0.41
62	4347.33	1.38	1155.33	1.60	2471.00	1.81	2938.33	2.18
63	4419.33	0.61	1625.00	0.80	2493.00	0.90	3250.67	1.36
64	4201.67	5.23	1254.67	3.07	2277.67	6.06	2852.00	4.41
65	4266.67	8.71	1156.67	5.19	1891.00	8.47	2611.33	9.72
66	4275.67	19.25	925.33	29.23	2057.67	34.32	2853.33	33.53
67	4282.67	61.29	861.00	60.87	2048.00	60.41	2589.33	61.58
68	4375.33	2.12	1709.00	2.76	3168.33	3.04	3206.00	2.76
69	4310.67	2.21	1443.67	2.71	2256.67	2.48	3046.33	3.16

Table A8. Results for instances instre1, instre2 and instre3.

	instre1		instre2		instre3
Method	Obj	Time	Obj	Time	Obj	Time
1	2591.67	60.30	2404.33	60.20	2985.67	60.30
20	2530.33	0.01	2243.67	0.01	2552.67	0.01
21	2526.33	0.14	2182.67	0.13	2496.67	0.14
22	2493.33	0.79	2186.67	0.71	2519.67	0.86
23	2526.33	0.25	2182.67	0.25	2496.67	0.29
24	2493.33	1.60	2186.67	1.39	2488.67	2.45
25	2323.00	3.50	2036.33	3.20	2455.67	2.96
26	2396.33	13.03	2076.00	12.30	2482.67	13.91
27	2129.33	60.17	1934.00	60.14	2247.33	60.28
28	2487.67	1.72	2182.67	1.55	2482.67	1.98
29	2530.33	1.71	2243.67	1.65	2552.67	1.91
30	2872.33	0.01	2473.00	0.01	2720.67	0.01
31	2872.33	0.15	2473.00	0.13	2691.00	0.16
32	2509.67	0.77	2007.33	0.68	2501.00	0.85
33	2872.33	0.14	2473.00	0.14	2691.00	0.30
34	2259.00	2.54	2007.33	1.46	2501.00	1.68
35	2251.33	3.49	2007.33	1.70	2344.33	3.11
36	2659.67	12.93	2293.00	11.73	2491.67	14.31
37	2119.33	60.69	1881.33	60.25	2152.33	60.04
38	2746.00	1.65	2234.00	1.55	2720.67	1.91
39	2593.00	1.67	2235.67	1.62	2356.00	1.76
40	3230.67	0.01	2684.33	0.01	2887.33	0.02
41	3114.67	0.14	2527.67	0.13	2633.33	0.17
42	2560.00	0.78	2194.67	0.75	2532.33	0.92
43	3005.67	0.38	2527.67	0.26	2633.33	0.31
44	2238.00	2.29	2194.67	1.55	2462.00	2.92
45	2315.67	2.84	1981.33	2.36	2201.33	4.23
46	2284.67	13.27	2405.67	13.09	2461.00	14.89
47	2418.67	60.10	2185.67	60.48	2354.67	60.04
48	2809.33	1.62	2639.33	1.55	2474.67	1.84
49	2463.67	1.58	2163.33	1.53	2542.00	1.80
50	3516.33	0.01	2994.67	0.01	3327.67	0.01
51	3311.67	0.15	2698.33	0.13	2995.00	0.16
52	2553.00	0.78	2254.00	0.68	2536.67	0.86
53	3118.67	0.42	2485.67	0.34	2737.67	0.57
54	2532.33	2.27	2222.33	2.09	2536.67	1.72
55	2303.67	3.55	1894.33	2.53	2316.33	3.08
56	2637.67	14.52	2312.33	11.86	2602.00	14.76
57	2337.67	60.02	1918.33	60.17	2169.33	60.56
58	2615.00	1.61	2459.33	1.55	2514.67	1.82
59	2408.67	1.71	2239.33	1.55	2693.67	1.83
60	5522.33	0.00	5533.67	0.01	5961.33	0.00
61	3302.00	0.14	2951.33	0.12	2678.67	0.15
62	2415.00	0.75	2088.33	0.70	2493.33	0.90
63	2933.00	0.26	2648.00	0.23	3213.00	0.29
64	2367.00	3.07	2108.00	1.72	2230.33	3.42
65	2298.67	1.83	2169.33	2.52	2346.00	4.03
66	2632.00	13.08	2156.67	12.14	2503.67	14.06
67	2231.00	60.46	1925.33	60.59	2198.33	60.79
68	2959.00	1.75	2467.33	1.51	2709.67	1.90
69	2447.67	1.63	2052.00	1.49	2612.00	1.83