Can GLPK be used to solve an optimal team selection problem?

Question

My Problem

I am quite new to optimisation, so any advice is appreciated. I am currently trying to solve a problem as follows:
Given a pool of people, we want to create n teams such to find the optimal solution based on all players' preferences

As a test, I have been assuming there are 6 players, each of which selects a 1st and a 2nd preference for who they would like in their team. For now, I am looking to create 2 teams of 3 players.

How I have attempted it

I want to solve this using an open-source solver in Python, so I am currently trying the 'glpk' solver via Pyomo, however I am stuck. I created a matrix of preferences, whereby each row represents a given player's top 2 preferences (here, 2 means 1st pick) as follows:

preferenceMatrix =  [0 1 0 0 2 0]  # Player 1 would like players 5 (1st pick) and 2 (2nd pick)
                    [2 0 1 0 0 0]  # Player 2 would like players 1 (1st pick) and 3 (2nd pick)
                    [0 0 0 0 2 1]  # Player 3 would like players 5 (1st pick) and 6 (2nd pick)
                    [0 1 2 0 0 0]  # Player 4 would like players 3 (1st pick) and 2 (2nd pick)
                    [0 0 0 1 2 0]  # Player 5 would like players 5 (1st pick) and 4 (2nd pick)
                    [2 0 0 1 0 0]  # Player 6 would like players 1 (1st pick) and 4 (2nd pick)
                    

Next, I multiply the preference matrix by a binary matrix (subject to a constraint of 2 players per row and column), and then maximise the sum over the entire matrix. An example of what the binary matrix could look like is:

binaryMatrix =   [0 1 1 0 0 0]
                 [1 0 1 0 0 0]
                 [1 1 0 0 0 0]
                 [0 0 0 0 1 1]
                 [0 0 0 1 0 1]
                 [0 0 0 1 1 0]

This would form 2 teams: Team 1) players 1,2,3, and Team 2) players 4,5,6 and the objective function (summing over rows) would be 1+3+0+0+1+1 = 6.

My questions

1) If I continue with this approach, then how could I constrain it to create exactly 2 teams? I originally posted this exact issue here

2) As I am finding it hard to approach the problem using glpk, is there a more appropriate open-source solver I could use instead?

3) Or, could I approach this entirely differently (e.g. using networkx where I specify that the problem should create 2 equal-sized connected groups)?

Answer 1

1. If I continue with this approach, then how could I constrain it to create exactly 2 teams?

If you need two teams exactly, you could define a "preference cost" $p_{ij}$ betweeen each pair of players $(i,j)$. For example, you could define $$ p_{ij} = \left\{ \begin{array}{ll} 4 & \mbox{if $i$ and $j$ are each others first pick}\\ 3 & \mbox{if $i$ or $j$ is a first pick} \\ 2 & \mbox{if $i$ and $j$ are each others second pick} \\ 1 & \mbox{if $i$ or $j$ is a second pick} \\ 0 & \mbox{otherwise} \\ \end{array} \right. $$ Then use the following binary variables :

• $x_{ij}^1 = 1$ if and only if players $i$ and $j$ end up in team $1$,
• $x_{ij}^2 = 1$ if and only if players $i$ and $j$ end up in team $2$,
• $w_{ij}=1$ if and only if players $i$ and $j$ end up together (whatever the team),
• $y_i=1$ if and only if player $i$ is selected for team $1$ (and so $y_i=0$ if $i$ is selected for team $2$).

So you want to maximize the global preference : $$ \max \; \sum_{i,j} p_{ij}w_{ij} $$ subject to:

• Each team must have $n/2$ players ($n$ denotes the total number of players): $$ \sum_{i}y_i = n/2 $$
• $x_{ij}$ is only active if $i$ and $j$ are selected simultaneously: $$ x_{ij}^1 \le y_{i} \\ x_{ij}^1 \le y_{j} \\ x_{ij}^2 \le 1-y_{i} \\ x_{ij}^2 \le 1-y_{j} \\ $$
• $i$ and $j$ are together if they are simultaneously in team $1$ or $2$: $$ w_{ij} = x_{ij}^1 + x_{ij}^2 $$
• variables are binary $$ x_{ij}^1,x_{ij}^2,w_{ij},y_i \in \{0,1\} $$

Note: there is probably a way to simplify the above equations. You basically need to model $$ \boxed{ w_{ij}=1 \quad \Rightarrow y_i=y_j } $$

2. As I am finding it hard to approach the problem using glpk, is there a more appropriate open-source solver I could use instead?

I would suggest using pulp instead. Pulp is a modeler, not a solver, but it can call any solver out there (including GLPK). With pulp, you can focus on the modeling part, and not worry about the solver, it will call the default one if you do not have any at hand (CBC). Check out the examples.

3. Or, could I approach this entirely differently (e.g. using networkx where I specify that the problem should create 2 equal-sized connected groups)?

You could create a complete graph with one vertex per player, and one edge between each pair of vertices with the above defined preference cost. You want to partition your vertices into two equal sized sets, so you want to color the vertices of the graph with two colors exactly, such that 1) both colors have the same amount of vertices 2) the preference cost is maximized, and it is only active when both vertices have the same color. There is no algorithm in the networkx package for this, to my knowledge.

---

EDIT :

This is basically a wedding planning problem. There is an example given in pulp's documentation, where the problem is modeled differently than above: it is modeled as a set partitioning problem, where all possible combinations are generated a priori. You can use it and consider that you are planning a wedding with 2 tables. Note that they also define a "preference cost", which they call "happiness."