Question: how to be sure that optimal is unique?
Consider cost c_ij of arc(ij). Let d_ij the maximum value for arc(ij) such that (ij) is in an optimal matching. Note: unicity implies that c_ij < d_ij if (ij) is in the optimum and c_ij > d_ij if not. Hence if optimum unique for no arc c_ij = d_ij. Conversely c_ij ¹ d_ij for all arcs implies unicity.