Given a matrix $M\in\mathbb{N}^{n\times n}$, let $Z$ be the set of all the $M$'s entry subsets $S$ such that **(i)** no two entries of $S$ are on the same row or column of $M$ and **(ii)** $|S|=n$. Clearly we have $|Z|=n!$. 


**Question**: How can we (efficiently) find the $M$'s entry subset $S^\* \in Z$ whose element sum is the *smallest* over all the $M$'s entry subsets belonging to $Z$? 


*We are interested in finding one of $Z$'s element attaining the minimum of the above question when it is not unique. Furthermore, a method to (efficiently) obtain just the sum of the elements of $S^\*$ (without necessarily finding $S^\*$) would be a significant result.*



Finding the minimum sum of a subset of entries of a given matrix with combinatorial constraints
Here is a way to formulate it as a convex optimization problem, which can then be solved in polynomial time. Your variables are $a\_{i,j}$, one for each position in the matrix. The problem is then:
$$0\le a\_{i,j} \le 1$$
$$\forall\_j \sum\_i a\_{i,j} = 1$$
$$\forall\_i \sum\_j a\_{i,j} = 1$$
$$\textrm{Minimize } M\bullet a$$
The first constraint defines $a$ as binary variables, the second and third define your "one per row/col" rule, and the last is the linear objective function. This leaves off the mention that $a\_{i,j}$ are integer: the values allowed by the above only restrict to the matrices $A$ that are doubly stochastic. However, the space of doubly stochastic matrices is the convex hull of permutation matrices, which are the ones you want. Thus, any linear objective function will naturally converge to a proper integer solution.


You can solve the above problem with any linear programming toolkit, such as GLPK, Gurobi, CPLEX...


There is a great deal of literature on the topic of optimizing over the space of permutation matrices, because they are such a convenient space to describe. e.g. <https://www.di.ens.fr/~aspremon/PDF/Simons13.pdf>


