Is there any conditions that can make the optimal solution of a assignment problem unique?
I know if there is no conditions on the cost matrix, it is not guaranteed to have a unique solution. (e.g. if a cost matrix has same number on all entries, then any assignments is optimal.)
References will also be welcomed. Thank you!
This question is answered in detail in section 5.3 of Assignment Problems (Burkard, Dell'Amico, Martello). Also see: Burkard & Butkovič (2003) "Max algebra and the linear assignment problem." Mathematical Programming 98, 415–429.
Unfortunately, all of these results are approachable but difficult to concisely summarize (for me at least).
Note that, assuming a square cost matrix $C$, all solutions to the linear assignment problem are basic feasible solutions (i.e. solutions lying on a vertex of the constraint set) of a the following linear program:
\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & \sum_{ij} C_{ij} P_{ij} \\ & \text{subject to} & & P_{ij} \geq 0, \quad \sum_i P_{ij} = 1, \quad \sum_j P_{ij} = 1 \end{aligned} \end{equation*}
The feasible set here is the Birkhoff polytope which is the convex hull of the set of all permutation matrices (due to the Birkhoff–von Neumann theorem). In this setting, the solution to an assignment problem will be unique if and only if the solution to this linear program is unique. Sufficient and necessary conditions for the uniqueness of linear programs can be found in, e.g., Mangasarian (1979) "Uniqueness of solution in linear programming." Linear Algebra and its Applications 25, 151-162.