Error Bounds for Rank-one Double Nonnegative Reformulations of QAP and Exact Penalties
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911194173931520 |
|---|---|
| author | Qian, Yitian Pan, Shaohua Bi, Shujun Qi, Houduo |
| author_facet | Qian, Yitian Pan, Shaohua Bi, Shujun Qi, Houduo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11210 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Error Bounds for Rank-one Double Nonnegative Reformulations of QAP and Exact Penalties Qian, Yitian Pan, Shaohua Bi, Shujun Qi, Houduo Optimization and Control 90C27, 90C26, 49M20 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. |
| title | Error Bounds for Rank-one Double Nonnegative Reformulations of QAP and Exact Penalties |
| topic | Optimization and Control 90C27, 90C26, 49M20 |
| url | https://arxiv.org/abs/2403.11210 |