Optimization Online


Centering ADMM for the Semidefinite Relaxation of the QAP

Shin-ichi Kanoh (s1920456***at***s.tsukuba.ac.jp)
Akiko Yoshise (yoshise***at***sk.tsukuba.ac.jp)

Abstract: We propose a new method for solving the semidefinite (SD) relaxation of the quadratic assignment problem (QAP), called the Centering ADMM. The Centering ADMM is an alternating direction method of multipliers (ADMM) combining the centering steps used in the interior-point method. The first stage of the Centering ADMM updates the iterate so that it approaches the central path by incorporating a barrier function term into the objective function, as in the interior-point method. If the current iterate is sufficiently close to the central path with a sufficiently small value of the barrier parameter, the method switches to the Standard ADMM. To observe the effect of the centering steps, we conducted numerical experiments with SD relaxation problems of instances in the QAPLIB \cite{QAPLIB}. The results demonstrate that the centering steps are quite efficient for some classes of instances.

Keywords: Quadratic assignment problem; Semidefinite relaxation; Alternating direction method of multipliers (ADMM); Interior-point method; Centering step; Barrier function

Category 1: Linear, Cone and Semidefinite Programming

Citation: Peoceedings of NACA-ICOTA2019

Download: [PDF]

Entry Submitted: 01/15/2020
Entry Accepted: 01/15/2020
Entry Last Modified: 01/03/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society