I asked the same on [math.Stackexchange](https://math.stackexchange.com/q/4520055/721298).


I have $n$ (say $n = 300$) vectors $v\_1,\dots,v\_n$. Each of them has $K$ coordinates (say $K = 30$). For vector $v\_j$ I denote it's coordinates as $v\_{j1},\dots,v\_{jK}$. I want select $M$ (say $M = 5$) vectors ${v\_{\hat s\_1}}, \dots, v\_{\hat s\_M} \in \{v\_1,\dots,v\_n\}$ such that  

$$\sum\_{k=1}^{K}\max\_{1 \le m \le M} v\_{\hat s\_mk} = \max\_{1 \le s\_1 \le n,\dots, \le s\_m \le n}\sum\_{k=1}^{K}\max\_{1 \le m \le M} v\_{s\_mk}.$$
What's the name for this type of questions? How do I (approximately) solve those fast? (I need to solve like 30 per minute)



Given a set of vectors how to pick $M$ such that sum of maximums of coordinates is maximized?
At very least the problem can be approached via (M)ILP by introducing indicator variables $q\_{jk}$ telling whether the corresponding coordinate $v\_{jk}$ is present in the sum of max, and $r\_j$ telling whether the vector $v\_j$ is selected. This results in the following formulation:


$$\begin{cases}
\sum\_{j=1}^n \sum\_{k=1}^K v\_{jk} q\_{jk} \longrightarrow \max\\
\sum\_{j=1}^n q\_{jk} = 1\qquad (k\in[K]), \\
\sum\_{k=1}^K q\_{jk} \leq Kr\_j\qquad (j\in[n]), \\
\sum\_{j=1}^n r\_j = M, \\
q\_{jk}, r\_j\in\{0,1\}\qquad (j\in[n],\ k\in[K]).
\end{cases}$$


