  We derive an explicit formula, as well as an efficient procedure, for
constructing a generalized Jacobian for the projector of a given square matrix
onto the Birkhoff polytope, i.e., the set of doubly stochastic matrices. To
guarantee the high efficiency of our procedure, a semismooth Newton method for
solving the dual of the projection problem is proposed and efficiently
implemented. Extensive numerical experiments are presented to demonstrate the
merits and effectiveness of our method by comparing its performance against
other powerful solvers such as the commercial software Gurobi and the academic
code PPROJ [{\sc Hager and Zhang}, SIAM Journal on Optimization, 26 (2016),
pp.~1773--1798]. In particular, our algorithm is able to solve the projection
problem with over one billion variables and nonnegative constraints to a very
high accuracy in less than 15 minutes on a modest desktop computer. More
importantly, based on our efficient computation of the projections and their
generalized Jacobians, we can design a highly efficient augmented Lagrangian
method (ALM) for solving a class of convex quadratic programming (QP) problems
constrained by the Birkhoff polytope. The resulted ALM is demonstrated to be
much more efficient than Gurobi in solving a collection of QP problems arising
from the relaxation of quadratic assignment problems.
