Error Bounds for Rank-one Double Nonnegative Reformulations of QAP and Exact Penalties

Abstract

This paper focuses on the error bounds for several equivalent rank-one doubly nonnegative (DNN) conic reformulations of the quadratic assignment problem (QAP), a class of challenging combinatorial optimization problems. We provide three equivalent rank-one DNN reformulations of the QAP, including the one proposed in \cite{Jiang21}, and establish the locally and globally Lipschitzian error bounds for their feasible sets. Then, these error bounds are employed to prove that the penalty problems induced by the difference-of-convexity (DC) reformulation of the rank-one constraint are global exact penalties, and so are the penalty problems for their Burer-Monteiro (BM) factorizations. As a byproduct, the penalty problem for the rank-one DNN reformulation in \cite{Jiang21} is shown to be a global exact penalty without the calmness assumption. Finally, we illustrate the application of these exact penalties by proposing a relaxation approach with one of them to seek a rank-one approximate feasible solution. This relaxation approach is validated to be superior to the commercial solver Gurobi for \textbf{132} benchmark instances in terms of the relative gap between the generated objective value and the known best one and the number of instances with better objective values.