Nine judges each award 20 competitors a rank from $1$ to $20$. The competitors’ score is the sum of the ranks from the nine judges, and the winner is the competitor with the lowest score. For each competitor the difference between the highest and lowest ranking (from different judges) is at most $3$.
What is the highest score(sum total of all the ranks given by the judges to any individual) the winner could have obtained?
On
This problem can be formulated as an integer linear program, where we introduce decision variables x_{i,j} that take value 1 if competitor i is ranked j by judge k and 0 otherwise. We also introduce a binary decision variable y_i that takes value 1 if competitor i is the winner and 0 otherwise.
We want to minimize the sum of the scores for all competitors, subject to the following constraints:
Each competitor i is ranked exactly once by each judge k: \sum_{j=1}^{20} x_{i,j,k} = 1 for all i and k.
Each rank j is assigned exactly once to a competitor i by any judge k: \sum_{i=1}^{20} x_{i,j,k} = 1 for all j and k.
The difference between the highest and lowest ranking for each competitor i is at most 3: max_{j,k} x_{i,j,k} - min_{j,k} x_{i,j,k} <= 3 for all i.
The winner y_i has the lowest score among all competitors: \sum_{j,k} j x_{i,j,k} >= \sum_{j,k} j x_{j,j,k} for all i.
The winner y_i is unique: \sum_{i=1}^{20} y_i = 1.
The objective function to minimize is: \sum_{i,j,k} j x_{i,j,k} y_i
Using an integer programming solver, we find that the highest score the winner could have obtained is 147, which is achieved when the competitor with the lowest score is ranked first by all nine judges. What is wrong in the above answer?
You can solve the problem via integer linear programming, and the maximum turns out to be $24$.
Let binary decision variable $x_{cjr}$ indicate whether competitor $c$ receives from judge $j$ a rank of $r$, so the rank of competitor $c$ from judge $j$ is $\sum_r r x_{cjr}$. Let decision variable $\ell_c$ represent $\min_j \sum_r r x_{cjr}$, and let decision variable $u_c$ represent $\max_j \sum_r r x_{cjr}$. Let decision variable $z$ represent the score of the winner. The problem is to maximize $z$ subject to linear constraints \begin{align} z &\le \sum_j \sum_r r x_{cjr} &&\text{for all $c$} \tag1\label1 \\ \sum_r x_{cjr} &= 1 &&\text{for all $c$ and $j$} \tag2\label2 \\ \sum_c x_{cjr} &= 1 &&\text{for all $j$ and $r$} \tag3\label3 \\ \ell_c \le \sum_r r x_{cjr} &\le u_c &&\text{for all $c$ and $j$} \tag4\label4 \\ u_c - \ell_c &\le 3 &&\text{for all $c$} \tag5\label5 \end{align} Constraint \eqref{1} enforces the maximin objective. Constraint \eqref{2} assigns one rank per competitor and judge. Constraint \eqref{3} assigns one competitor per judge and rank. Constraint \eqref{4} enforces the definitions of $\ell_c$ and $u_c$. Constraint \eqref{5} restricts the difference in ranks for each competitor to be at most $3$.
Here is one optimal ranking, with one row per competitor and one column per judge, in nondecreasing order of score (the last column): \begin{matrix} 1 &3 &1 &3 &3 &3 &3 &4 &3 &24 \\ 3 &1 &3 &1 &1 &4 &4 &3 &4 &24 \\ 4 &4 &4 &4 &4 &1 &1 &1 &1 &24 \\ 5 &5 &5 &2 &2 &2 &2 &2 &2 &27 \\ 2 &2 &2 &5 &5 &5 &5 &5 &5 &36 \\ 6 &6 &6 &6 &6 &6 &6 &6 &6 &54 \\ 7 &7 &7 &7 &7 &7 &7 &7 &7 &63 \\ 8 &8 &8 &8 &8 &8 &8 &8 &8 &72 \\ 9 &9 &9 &9 &9 &9 &9 &9 &9 &81 \\ 10 &10 &10 &10 &10 &10 &10 &10 &10 &90 \\ 11 &11 &11 &11 &11 &11 &11 &11 &11 &99 \\ 12 &12 &12 &12 &12 &12 &12 &12 &12 &108 \\ 13 &13 &13 &13 &13 &13 &13 &13 &13 &117 \\ 14 &14 &14 &14 &14 &14 &14 &14 &14 &126 \\ 15 &15 &15 &15 &15 &15 &15 &15 &15 &135 \\ 16 &16 &16 &16 &16 &16 &16 &16 &16 &144 \\ 17 &17 &17 &17 &17 &17 &17 &17 &17 &153 \\ 18 &18 &18 &18 &18 &18 &18 &18 &18 &162 \\ 19 &19 &19 &19 &19 &19 &19 &19 &19 &171 \\ 20 &20 &20 &20 &20 &20 &20 &20 &20 &180 \\ \end{matrix}