Optimization problem over matrices (part 2)

Question

Background

Yesterday I've asked some questions about a particular optimization problem that I have to resolve. I've found a simple solution which it turns out to be suboptimal (I have found a counterexample that clearly shows this fact), so now I'm trying to find the optimal solution.

Thanks to the help of Rodrigo, I've realized through this post that my problem is "almost" a linear programming problem. Indeed, its easy to see that my problem can be formulated as follows \begin{equation} \max_{P\in \mathcal{P}} \sum_{i=1}^{p} (MP)_{ii} \tag{1} \end{equation} where:

• $M$ is a given $m\times n$ matrix whose entries are integers;
• $p\triangleq\min(m,n)$;
• $(MP)_{ii}$ denotes the $i$-th diagonal entry of the product $MP$;
• $P$ is the optimization variable;
• $\mathcal{P}$ is the set of permutation matrices that permutate the columns of $M$.

since $P$ is a permutation matrix, each column of $P$ is a vector with one component equal to $1$ and $p-1$ components equal to $0$. Similarly, each row of $P$ is a vector with one component equal to $1$ and $p-1$ components equal to $0$. This two properties can be expressed in weaker form via the relations \begin{equation*} \begin{aligned} 1_p'P&=1_p'\\ P 1_p&= 1_p \\ P_{ij}&\geq 0 \qquad j,i = 1,\dots, p \end{aligned} \end{equation*} where $1_p$ is a $p\times1$ vector in which each entry is $1$ and $'$ is the transpose operator. Consequently, a relaxation of my original problem $(1)$ is given by \begin{equation} \begin{aligned} \max_{P} &\sum_{i=1}^{p} (MP)_{ii}\\ \text{st} \quad & 1_p'P=1_p'\\ &P 1_p= 1_p\\ &P_{ij}\geq 0 \qquad j,i = 1,\dots, p \end{aligned} \tag{2} \end{equation}

which is a linear programming problem. The point is that now the optimization variables (i.e. the entries $P_{ij}$ of $P$) can be any positive real number, and so it is not clear to me if the optimum $P^*$ of $(2)$ is, as I desire, a permutation matrix.

Questions

1. The solution of the relaxed problem $(2)$ can be used to find the solution of my original problem $(1)$? Maybe, if necessary, I can round the optimum $P^*$ of the relaxed problem towards the nearest permutation matrix
2. Is there some integer solver for my original problem $(1)$?