1

Eight athletes 1, 2, 3, 4, 5, 6, 7, and 8 participate as a team in a multidisciplinary competition.
The four disciplines involved are labeled A, B, C, and D.

The participation constraints for a team are:

  • Each discipline must have four athletes.
  • Each athlete must compete in two different disciplines.

Athletes' performances in their assigned disciplines are given scores between 0 and 7 inclusive (That is, an athlete may score a minimum of 0 and a maximum of 14 points).

Each athlete has an expected score for each discipline. Given the four expected scores (one per discipline) for each of the eight athletes, how does the team maximize its expected score while meeting the participation constraints?

penguinick77
  • 163
  • Not enough information. What does the past performance mean? – Andrei Dec 25 '16 at 19:23
  • You can cast this as a max-flow problem. – LinAlg Dec 25 '16 at 19:26
  • The past performances really don't matter. Each athlete is expected to attain some score if they participate in some discipline for this competition. – penguinick77 Dec 25 '16 at 19:30
  • I get that they are given some scores for the assigned disciplines. How are these scores a constraint for the allocation of disciplines? – YukiJ Dec 29 '16 at 08:51
  • Oh, I see. I suppose the scoring system wouldn't constrain the allocation of disciplines. I think I put it there initially because the set of expected scores is essentially random for this problem, and based upon the four expected scores for each athlete, two disciplines will be allocated for each athlete. So, the set of expected scores for any upcoming competition will likely change the allocation of disciplines from the last competition. But, I think I should remove it from the constraints now. – penguinick77 Dec 29 '16 at 14:40
  • In this case my answer below covers everything: the objective function as well as all constraints listed above. – YukiJ Dec 29 '16 at 20:10

1 Answers1

0

Let $\mathbb{D} := \{A,B,C,D\}$ be the set of disciplines and $\mathbb{A}:=\{1,...,8\}$ be the set of athletes.

Let $E_{ij}$ be the expected score for athelete $i$ in discipline $j$.

Define $x_{ij}$ as a binary variable defined as follows:

$$x_{ij} = \cases{1,~ \text{if athlete i competes in discipline j}\\ 0, \text{ otherwise}}$$

The objective funtion that is to be maximized is $\sum_{i \in \mathbb{A}}\sum_{j \in \mathbb{D}} x_{ij}E_{ij}$.

Now we have to add the constraints. The first constraint requires us to have four athletes in each discipline. So, for every discipline $j$ the following must hold:

$$\sum_{i \in \mathbb{A}} x_{ij} =4$$

This makes sure that for discipline $j$ exactly 4 players are chosen from the set of athletes.

Constraint 2 requires that each athlete $i$ competes in exactly two discipline. Hence,

$$\sum_{j \in \mathbb{D}} x_{ij} =2$$

I am not sure about the last constraint as there is not enough information about it yet. I will include it as soon as you edit the question with more information. So far, the optimization problem that needs to be solved is the following:

$$\max \sum_{i \in \mathbb{A}}\sum_{j \in \mathbb{D}} x_{ij}E_{ij}$$ $$s.t. \sum_{i \in \mathbb{A}} x_{ij} =4 ~~~~~\forall j \in \mathbb{D}$$

$$\sum_{j \in \mathbb{D}} x_{ij} =2 ~~~~~\forall i \in \mathbb{A}$$ $$x_{ij} \in \{0,1\} ~~~~~\forall i \in \mathbb{A}~~\forall j \in \mathbb{D}$$

YukiJ
  • 2,529
  • Edited the original question so that it is more clear. Is there still some aspect of the problem that I have left unclear? – penguinick77 Dec 29 '16 at 03:44
  • You obtain superior performance by modeling this as a flow problem instead of as an MILP (even if the constraint matrix is TUM), due to more efficient algorithms. – LinAlg Jan 15 '17 at 11:32