Optimization Online


A Restricted Dual Peaceman-Rachford Splitting Method for QAP

Naomi Graham(n6graham***at***uwaterloo.ca)
Hao Hu(h92hu***at***uwaterloo.ca)
Haesol Im(haesol42***at***gmail.com)
Xinxin Li(xinxinli***at***jlu.edu.cn)
Henry Wolkowicz(henry.wolkowicz***at***uwaterloo.ca)

Abstract: We revisit and strengthen splitting methods for solving doubly nonnegative, DNN, relaxations of the quadratic assignment problem, QAP. We use a modified restricted contractive splitting method, rPRSM, approach. Our strengthened bounds and new dual multiplier estimates improve on the bounds and convergence results in the literature.

Keywords: semidefinite relaxation, doubly nonnegative relaxation, quadratic assignment problem, Peaceman-Rachford splitting method, facial reduction

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: Department of Combinatorics & Optimization, University of Waterloo, Canada,06/2019

Download: [PDF]

Entry Submitted: 06/02/2020
Entry Accepted: 06/02/2020
Entry Last Modified: 06/02/2020

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