Arrangement of musicians into distinct bands - combinatorics solution?

57 Views Asked by At

Real life problem.

I have 8 different musical instruments and 14 players of each instrument. There will be 9 sessions where the players are placed into 14 bands (each band has 1 of each instrument). So if each instrumentalist was labeled 1-14 for their respective instrument, the first session could be band 1: all instrument 1s, band 2 all instrument 2s etc.

Is it possible for each band in each session to be unique? I.e. Trumpet 1 doesn't play with clarinet 1 more than once (and doesn't play with any other instrumental person from other instruments more than once). I am able to brute force this with 3 or 4 sessions but past that it gets difficult.

While I have a math degree and took some combinatorics classes, I am definitely not an expert. I think this might fall under Combinatorial Design but I am not really sure.

1

There are 1 best solutions below

5
On

Yes, you can set this up and solve as an integer program. If I'm understanding your requirements correctly, it could be something like the following. (Then this could be solved using a variety of optimization software. E.g., SCIP in python)

Sets:

$S$ Set of sessions

$B$ Set of bands in each session

$P$ Set of people

$I$ Set of instruments

Parameters:

$c_{pi} \in \{0,1\}$ if person $p$ plays instrument $i$, $0$ otherwise

Variables:

$X_{psb} \in \{0,1\}$ if person $p$ plays in band $b$ in session $s$

$Y_{pp'sb} \in \{0,1\}$ if person $p$ plays with person $p'$ in band $b$ in session $s$

Formulation:

min $0$

subject to:

$ \sum_{p \in P} c_{pi}X_{psb} = 1, \forall s \in S, b\in B, i \in I$

$ Y_{pp'sb} \geq X_{psb} + X_{p'sb} - 1, \forall p \in P, p' \in P \setminus \{p\}, s \in S, b\in B$

$ \sum_{s\in S}\sum_{b \in B} Y_{pp'sb} \leq 1, \forall p \in P, p' \in P \setminus \{p\},$

I believe you're looking for any feasible solution that satisfies your constraints - so the objective doesn't matter. The first constraint set requires there to be exactly 1 instrument of each type in each band. The second constraint set assigns an indicator variable if a person has been assigned to the same band as another person in the same session. The third constraint set only allows you to assign 2 people to the same band once.