Skip to main content
added 620 characters in body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$; that is, $p_1=15$, $p_2=12$, and $p_j=13-j$ otherwise. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes (each race $k$ yields a permutation of $\{1,\dots,12\}$): \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\2&2&12&2&10&28\\3&3&1&12&11&28\\4&4&11&11&1&28\\5&5&5&10&4&28\\6&6&10&9&7&20\\7&7&3&8&6&28\\8&8&2&6&9&28\\9&9&9&1&8&28\\10&10&6&5&3&28\\11&11&4&4&5&28\\12&12&8&3&2&28 \end{matrix}\begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\ 2&2&12&2&10&28\\ 3&3&1&12&11&28\\ 4&4&11&11&1&28\\ 5&5&5&10&4&28\\ 6&6&10&9&7&20\\ 7&7&3&8&6&28\\ 8&8&2&6&9&28\\ 9&9&9&1&8&28\\ 10&10&6&5&3&28\\ 11&11&4&4&5&28\\ 12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.

Here's a solution with $c=25$: \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&10&9&10&25\\ 2&2&11&11&4&25\\ 3&3&9&12&3&25\\ 4&4&5&7&11&25\\ 5&5&1&1&1&53\\ 6&6&4&5&12&25\\ 7&7&12&2&7&25\\ 8&8&8&6&5&25\\ 9&9&7&10&2&25\\ 10&10&2&8&8&25\\ 11&11&3&4&9&25\\ 12&12&6&3&6&25 \end{matrix}

Here's a solution with $c=29$: \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&6&8&11&29\\ 2&2&9&9&4&29\\ 3&3&7&6&7&29\\ 4&4&5&4&10&29\\ 5&5&1&11&9&29\\ 6&6&2&10&6&29\\ 7&7&12&12&12&9\\ 8&8&4&3&8&29\\ 9&9&11&1&5&29\\ 10&10&10&5&1&29\\ 11&11&8&2&3&29\\ 12&12&3&7&2&29 \end{matrix}

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$; that is, $p_1=15$, $p_2=12$, and $p_j=13-j$ otherwise. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes (each race $k$ yields a permutation of $\{1,\dots,12\}$): \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\2&2&12&2&10&28\\3&3&1&12&11&28\\4&4&11&11&1&28\\5&5&5&10&4&28\\6&6&10&9&7&20\\7&7&3&8&6&28\\8&8&2&6&9&28\\9&9&9&1&8&28\\10&10&6&5&3&28\\11&11&4&4&5&28\\12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$; that is, $p_1=15$, $p_2=12$, and $p_j=13-j$ otherwise. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes (each race $k$ yields a permutation of $\{1,\dots,12\}$): \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\ 2&2&12&2&10&28\\ 3&3&1&12&11&28\\ 4&4&11&11&1&28\\ 5&5&5&10&4&28\\ 6&6&10&9&7&20\\ 7&7&3&8&6&28\\ 8&8&2&6&9&28\\ 9&9&9&1&8&28\\ 10&10&6&5&3&28\\ 11&11&4&4&5&28\\ 12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.

Here's a solution with $c=25$: \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&10&9&10&25\\ 2&2&11&11&4&25\\ 3&3&9&12&3&25\\ 4&4&5&7&11&25\\ 5&5&1&1&1&53\\ 6&6&4&5&12&25\\ 7&7&12&2&7&25\\ 8&8&8&6&5&25\\ 9&9&7&10&2&25\\ 10&10&2&8&8&25\\ 11&11&3&4&9&25\\ 12&12&6&3&6&25 \end{matrix}

Here's a solution with $c=29$: \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&6&8&11&29\\ 2&2&9&9&4&29\\ 3&3&7&6&7&29\\ 4&4&5&4&10&29\\ 5&5&1&11&9&29\\ 6&6&2&10&6&29\\ 7&7&12&12&12&9\\ 8&8&4&3&8&29\\ 9&9&11&1&5&29\\ 10&10&10&5&1&29\\ 11&11&8&2&3&29\\ 12&12&3&7&2&29 \end{matrix}

added 55 characters in body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$; that is, $p_1=15$, $p_2=12$, and $p_j=13-j$ otherwise. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes (each race $k$ yields a permutation of $\{1,\dots,12\}$): \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\2&2&12&2&10&28\\3&3&1&12&11&28\\4&4&11&11&1&28\\5&5&5&10&4&28\\6&6&10&9&7&20\\7&7&3&8&6&28\\8&8&2&6&9&28\\9&9&9&1&8&28\\10&10&6&5&3&28\\11&11&4&4&5&28\\12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes: \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\2&2&12&2&10&28\\3&3&1&12&11&28\\4&4&11&11&1&28\\5&5&5&10&4&28\\6&6&10&9&7&20\\7&7&3&8&6&28\\8&8&2&6&9&28\\9&9&9&1&8&28\\10&10&6&5&3&28\\11&11&4&4&5&28\\12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$; that is, $p_1=15$, $p_2=12$, and $p_j=13-j$ otherwise. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes (each race $k$ yields a permutation of $\{1,\dots,12\}$): \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\2&2&12&2&10&28\\3&3&1&12&11&28\\4&4&11&11&1&28\\5&5&5&10&4&28\\6&6&10&9&7&20\\7&7&3&8&6&28\\8&8&2&6&9&28\\9&9&9&1&8&28\\10&10&6&5&3&28\\11&11&4&4&5&28\\12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.

Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

You can solve the problem via integer linear programming as follows. For $j\in \{1,\dots,12\}$, let $p_j$ be the points awarded for place $j$. For $i\in\{1,\dots,12\}$, $j\in \{1,\dots,12\}$, and $k\in\{1,\dots,4\}$, let binary decision variable $x_{ijk}$ indicate whether player $i$ places $j$ in race $k$. Let decision variable $s_i$ be the total score for player $i$, let decision variable $c$ be the common score, and let binary decision variable $y_i$ indicate whether $s_i=c$. The problem is to maximize $\sum_i y_i$ subject to linear constraints \begin{align} \sum_j x_{ijk} &= 1 &&\text{for all $i$ and $k$} \tag1\label1 \\ \sum_i x_{ijk} &= 1 &&\text{for all $j$ and $k$} \tag2\label2 \\ \sum_{j,k} p_j x_{ijk} &= s_i &&\text{for all $i$} \tag3\label3 \\ -15(1-y_i) \le s_i - c &\le 15(1-y_i) &&\text{for all $i$} \tag4\label4 \end{align} Constraint \eqref{1} assigns one place to each player and race. Constraint \eqref{2} assigns one player to each place and race. Constraint \eqref{3} enforces the definition of $s_i$. Constraint \eqref{4} enforces the logical implication $y_i=1 \implies s_i=c$.

The optimal objective value turns out to be $11$, achieved for example by the following outcomes: \begin{matrix} i & k=1 & k=2 & k=3 & k=4 & s_i\\ \hline 1&1&7&7&12&28\\2&2&12&2&10&28\\3&3&1&12&11&28\\4&4&11&11&1&28\\5&5&5&10&4&28\\6&6&10&9&7&20\\7&7&3&8&6&28\\8&8&2&6&9&28\\9&9&9&1&8&28\\10&10&6&5&3&28\\11&11&4&4&5&28\\12&12&8&3&2&28 \end{matrix}

To find the range of possible common scores $c$, impose an additional constraint $$\sum_i y_i = 11$$ and minimize or maximize $c$. The range turns out to be $25 \le c \le 29$, and all five values are achievable.