A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP

Naomi Graham (), Hao Hu (), Jiyoung Im (), Xinxin Li () and Henry Wolkowicz ()
Additional contact information
Naomi Graham: Department of Computer Science, The University of British Columbia, Vancouver, British Columbia V6T 1Z4, Canada
Hao Hu: School of Mathematical and Statistical Sciences, Clemson University, Clemson, South Carolina 29634
Jiyoung Im: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, N2L 3G1 Ontario, Canada
Xinxin Li: School of Mathematics, Jilin University, Changchun, Jilin 130012, China
Henry Wolkowicz: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, N2L 3G1 Ontario, Canada

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2125-2143

Abstract: Splitting methods in optimization arise when one can divide an optimization problem into two or more simpler subproblems. They have proven particularly successful for relaxations of problems involving discrete variables. We revisit and strengthen splitting methods for solving doubly nonnegative relaxations of the particularly difficult, NP-hard quadratic assignment problem. We use a modified restricted contractive splitting method approach. In particular, we show how to exploit redundant constraints in the subproblems. Our strengthened bounds exploit these new subproblems and new dual multiplier estimates to improve on the bounds and convergence results in the literature. Summary of Contribution: In our paper, we consider the quadratic assignment problem (QAP). It is one of the fundamental combinatorial optimization problems in the fields of optimization and operations research and includes many fundamental applications. We revisit and strengthen splitting methods for solving doubly nonnegative (DNN) relaxation of the QAP. We use a modified restricted contractive splitting method. We obtain strengthened bounds from improved lower and upper bounding techniques, and in fact, we solve many of these NP-hard problems to (provable) optimality, thus illustrating both the strength of the DNN relaxation and our new bounding techniques.

Keywords: quadratic assignment problem; semidefinite relaxation; doubly nonnegative relaxation; facial reduction; Peaceman-Rachford splitting method (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1161 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2125-2143

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().