What algorithm should I use to solve this optimization problem?

Question

Suppose that m different n-length row vectors $x_1,...x_{m}$ ($m > n$) are given. For each permutation of 1:m, $i_1,...i_m$, I can build a m by n matrix $X$ = bind_rows($x_{i_1},...,x_{i_m}$). Now I want to maximize the sum of diagonal elements of matrix $T=X_{1,1}+X_{2,2}+...+X_{n,n}$. If m and n are small, I can list all of the permutations and get the best one. But if $m$ and $n$ are greater than 15, for example, $m = 17, n = 15$, what kind of algorithm should I use?

Answer 1

You can think of this as an assignment problem: you are looking for a maximal-weight matching in the bipartite graph where one part consists of the vectors $x_1, \ldots, x_m$, the other the positions $1,\ldots, n$, and edge $(x_i, j)$ has weight $(x_i)_j$. Efficient algorithms are available.