  Given a dissimilarity matrix, the metric nearness problem is to find the
nearest matrix of distances that satisfy the triangle inequalities. This
problem has wide applications, such as sensor networks, image processing, and
so on. But it is of great challenge even to obtain a moderately accurate
solution due to the $O(n^{3})$ metric constraints and the nonsmooth objective
function which is usually a weighted $\ell_{p}$ norm based distance. In this
paper, we propose a delayed constraint generation method with each subproblem
solved by the semismooth Newton based proximal augmented Lagrangian method
(PALM) for the metric nearness problem. Due to the high memory requirement for
the storage of the matrix related to the metric constraints, we take advantage
of the special structure of the matrix and do not need to store the
corresponding constraint matrix. A pleasing aspect of our algorithm is that we
can solve these problems involving up to $10^{8}$ variables and $10^{13}$
constraints. Numerical experiments demonstrate the efficiency of our algorithm.
  In theory, firstly, under a mild condition, we establish a primal-dual error
bound condition which is very essential for the analysis of local convergence
rate of PALM. Secondly, we prove the equivalence between the dual nondegeneracy
condition and nonsingularity of the generalized Jacobian for the inner
subproblem of PALM. Thirdly, when $q(\cdot)=\|\cdot\|_{1}$ or
$\|\cdot\|_{\infty}$, without the strict complementarity condition, we also
prove the equivalence between the the dual nondegeneracy condition and the
uniqueness of the primal solution.
