  Optimization problems over permutation matrices appear widely in facility
layout, chip design, scheduling, pattern recognition, computer vision, graph
matching, etc. Since this problem is NP-hard due to the combinatorial nature of
permutation matrices, we relax the variable to be the more tractable doubly
stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization term to
the objective function. The optimal solutions of the $L_p$-regularized problem
are the same as the original problem if the regularization parameter is
sufficiently large. A lower bound estimation of the nonzero entries of the
stationary points and some connections between the local minimizers and the
permutation matrices are further established. Then we propose an $L_p$
regularization algorithm with local refinements. The algorithm approximately
solves a sequence of $L_p$ regularization subproblems by the projected gradient
method using a nonmontone line search with the Barzilai-Borwein step sizes. Its
performance can be further improved if it is combined with certain local search
methods, the cutting plane techniques as well as a new negative proximal point
scheme. Extensive numerical results on QAPLIB and the bandwidth minimization
problem show that our proposed algorithms can often find reasonably high
quality solutions within a competitive amount of time.
