1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Re-reading the original question - are you trying to make assignments or are you wondering if it is possible or not? If It's the former, an optimization approach will work for you. If the latter - you could use an optimization approach (if there's a feasible solution it means it's possible; infeasible means it's not), though there may be alternate ways to check that than setting up a model. $\endgroup$ – E. Tucker Jun 20 '18 at 20:04
  • $\begingroup$ I am trying to actually make the assignments. At the end of the day, if you pick any player, say Trumpet 12, he/she shouldn't be matched with the same player from any other instrument more than once in all 9 sessions. $\endgroup$ – Brutius Jun 20 '18 at 20:13
  • $\begingroup$ Great - I think an integer program such as above will work for you. If you have trouble implementing, let me know. $\endgroup$ – E. Tucker Jun 20 '18 at 20:48
  • $\begingroup$ I've been thinking about this some more - if you adjusted the variable $Y_{pp'sb}$ to be $Y_{pp's}$ instead, the program would be substantially smaller. Constraint set 2 would stay the same, and for constraint set 3, you would remove the summation over $B$. Also I'm not sure how computational you are, but an easier(?) option than Python might be Open Solver (opensolver.org) for Excel. It's an add-in that allows you to solve moderate size integer programs. Solver Studio - another Excel add-in (solverstudio.org) can handle larger ones. $\endgroup$ – E. Tucker Jun 21 '18 at 20:53
  • $\begingroup$ I am not familiar with any of the computational programs unfortunately. I downloaded scip today and played around with it but couldn’t figure out how to do much. I do appreciate you help this far though. $\endgroup$ – Brutius Jun 22 '18 at 1:00

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.