I want to formulate the following problem in an integer linear programming problem:
We have $n$ elements $m_1,\dots, m_n$ elements with $m_i = (m_i^1, \dots, m_i^p) \in \mathbb{R}_{\geq 0}^p$ for all $i = 1,\dots, n$. $p$ is the number of groups we have. For each $m_i$, $m_i^j$ describes how good we can separate group $j$ from all the other groups, $j=1,\dots, p$. For example, lets say $p=3$ and we have elements $m_1 = (3,8, 1), m_2 = (0,0, 5)$, then with $m_1$, we can for example separate group $2$ very good the other groups, because $m_1^2 = 8$, and with $m_2$, we can not separate group $1$ from the others ($m_2^1 = 0$) and also not group $2$ from the others ($m_2^2 = 0$), but we can separate group $3$ as $m_2^3 = 5$.
For a given number $q \in \mathbb{N}$ with $0<q<n$, I now want to choose $q$ different elements of $m_1,\dots, m_n$, such that we can separate the different $p$ groups in the best way possible. This means that i do not necessarily only want to pick the $q$ elements which have the highest absolute separation value (with the absolute separation value of an element $m_i$ I mean the sum $\sum_{j=1}^p{m_i^j}$), because this may not give the optimal separation of all groups. For example for $3$ groups and with $4$ elements $m_1 = (8,3,1)$, $m_2 = (2,9,0)$, $m_3 = (1, 3, 8)$, $m_4 = (5,5,5)$, where we want to choose $q=3$ elements, this method would say I should pick $m_4$, $m_1$ and $m_3$, because $\sum_{j=1}^3{m_4^j} = 15$, $\sum_{j=1}^3{m_1^j} = 12$, $\sum_{j=1}^3{m_3^j} = 12$, $\sum_{j=1}^3{m_2^j} = 11$. In this case, I would rather like to choose $m_1$, $m_2$ and $m_3$, because $m_1$ is best to separate group $1$ from the others, $m_2$ to separate group $2$, $m_3$ to separate group $3$.
I had the following idea, but do not know if it is a good formulation of the problem: Let $c_i = (m_1^i, \dots, m_n^i)$ be the separation values for group $i$ of the $n$ elements , so we have $p$ of these vectors. We call $\bar{c_i} = \frac{1}{n}\sum_{j=1}^n{m_j^i}$ the mean of $c_i$. Then we want to solve the following problem:$$\max_{x \in \{0,1\}^n}\sum_{i=1}^p{\frac{1}{\bar{c_i}}c_i^tx}\text{ , subject to } \sum_{i=1}^n{x_i} = q.$$
This is of course equivalent to $$\max_{x \in \{0,1\}^n}(\sum_{i=1}^p{\frac{1}{\bar{c_i}}c_i})^tx\text{ , subject to } \sum_{i=1}^n{x_i} = q.$$
In the example above, this would give us $m_1$, $m_3$ and $m_4$, which in my opinion is still not the best choice.
Does someone have an idea how i could formulate an objective function that works good? I am happy about any help!
