A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
Author
Abstract
Suggested Citation
DOI: 10.1287/ijoc.2022.1161
Download full text from publisher
References listed on IDEAS
- Deren Han & Defeng Sun & Liwei Zhang, 2018. "Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 622-637, May.
- Xinxin Li & Ting Kei Pong & Hao Sun & Henry Wolkowicz, 2021. "A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem," Computational Optimization and Applications, Springer, vol. 78(3), pages 853-891, April.
- Rendl, F. & Sotirov, R., 2007. "Bounds for the quadratic assignment problem using the bundle method," Other publications TiSEM b6d298bc-77c9-4a6d-a043-5, Tilburg University, School of Economics and Management.
- Alexander Barvinok & Tamon Stephen, 2003. "The Distribution of Values in the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 64-91, February.
- José F. S. Bravo Ferreira & Yuehaw Khoo & Amit Singer, 2018. "Semidefinite programming approach for the quadratic assignment problem with a sparse graph," Computational Optimization and Applications, Springer, vol. 69(3), pages 677-712, April.
- Burkard, R. E. & Karisch, S. & Rendl, F., 1991. "QAPLIB-A quadratic assignment problem library," European Journal of Operational Research, Elsevier, vol. 55(1), pages 115-119, November.
- Damek Davis & Wotao Yin, 2017. "Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 783-805, August.
- A. M. Geoffrion & G. W. Graves, 1976. "Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/ LP Approach," Operations Research, INFORMS, vol. 24(4), pages 595-610, August.
- Qing Zhao & Stefan E. Karisch & Franz Rendl & Henry Wolkowicz, 1998. "Semidefinite Programming Relaxations for the Quadratic Assignment Problem," Journal of Combinatorial Optimization, Springer, vol. 2(1), pages 71-109, March.
- Zvi Drezner, 2003. "A New Genetic Algorithm for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 320-330, August.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Lennart Sinjorgo & Renata Sotirov, 2024. "On Solving MAX-SAT Using Sum of Squares," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 417-433, March.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
- Yichuan Ding & Henry Wolkowicz, 2009. "A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 1008-1022, November.
- Zamani, Moslem & Abbaszadehpeivasti, Hadi & de Klerk, Etienne, 2024. "The exact worst-case convergence rate of the alternating direction method of multipliers," Other publications TiSEM f30ae9e6-ed19-423f-bd1e-0, Tilburg University, School of Economics and Management.
- E. R. van Dam & R. Sotirov, 2015.
"On Bounding the Bandwidth of Graphs with Symmetry,"
INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 75-88, February.
- van Dam, E.R. & Sotirov, R., 2015. "On bounding the bandwidth of graphs with symmetry," Other publications TiSEM 180849f1-e7d3-44d9-8424-5, Tilburg University, School of Economics and Management.
- Jiming Peng & Tao Zhu & Hezhi Luo & Kim-Chuan Toh, 2015. "Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting," Computational Optimization and Applications, Springer, vol. 60(1), pages 171-198, January.
- de Klerk, E. & Sotirov, R., 2007.
"Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem,"
Other publications TiSEM
87a5d126-86e5-4863-8ea5-1, Tilburg University, School of Economics and Management.
- de Klerk, E. & Sotirov, R., 2007. "Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem," Discussion Paper 2007-44, Tilburg University, Center for Economic Research.
- de Klerk, E. & Sotirov, R., 2010. "Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem," Other publications TiSEM 73287c80-3bc2-40c4-b02d-4, Tilburg University, School of Economics and Management.
- Zhuoxuan Jiang & Xinyuan Zhao & Chao Ding, 2021. "A proximal DC approach for quadratic assignment problem," Computational Optimization and Applications, Springer, vol. 78(3), pages 825-851, April.
- Hu, Hao & Sotirov, Renata & Wolkowicz, Henry, 2023. "Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs," Other publications TiSEM 8dd3dbae-58fd-4238-b786-e, Tilburg University, School of Economics and Management.
- Dobre, C., 2011. "Semidefinite programming approaches for structured combinatorial optimization problems," Other publications TiSEM e1ec09bd-b024-4dec-acad-7, Tilburg University, School of Economics and Management.
- Abbaszadehpeivasti, Hadi, 2024. "Performance analysis of optimization methods for machine learning," Other publications TiSEM 3050a62d-1a1f-494e-99ef-7, Tilburg University, School of Economics and Management.
- F. Rendl, 2016. "Semidefinite relaxations for partitioning, assignment and ordering problems," Annals of Operations Research, Springer, vol. 240(1), pages 119-140, May.
- Zakir Hussain Ahmed, 2016. "Experimental analysis of crossover and mutation operators on the quadratic assignment problem," Annals of Operations Research, Springer, vol. 247(2), pages 833-851, December.
- Torki, Abdolhamid & Yajima, Yatsutoshi & Enkawa, Takao, 1996. "A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 384-391, October.
- Ernest K. Ryu & Yanli Liu & Wotao Yin, 2019. "Douglas–Rachford splitting and ADMM for pathological convex optimization," Computational Optimization and Applications, Springer, vol. 74(3), pages 747-778, December.
- Pawel Kalczynski & Jack Brimberg & Zvi Drezner, 2022. "Less is more: discrete starting solutions in the planar p-median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 34-59, April.
- Becker, Christian & Scholl, Armin, 2006.
"A survey on problems and methods in generalized assembly line balancing,"
European Journal of Operational Research, Elsevier, vol. 168(3), pages 694-715, February.
- Armin Scholl & Christian Becker, 2003. "A survey on problems and methods in generalized assembly line balancing," Jenaer Schriften zur Wirtschaftswissenschaft (Expired!) 21/2003, Friedrich-Schiller-Universität Jena, Wirtschaftswissenschaftliche Fakultät.
- Jean-François Cordeau & Manlio Gaudioso & Gilbert Laporte & Luigi Moccia, 2006. "A Memetic Heuristic for the Generalized Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 433-443, November.
- Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
- Hungerländer, Philipp & Anjos, Miguel F., 2015. "A semidefinite optimization-based approach for global optimization of multi-row facility layout," European Journal of Operational Research, Elsevier, vol. 245(1), pages 46-61.
- William W. Hager & Hongchao Zhang, 2020. "Convergence rates for an inexact ADMM applied to separable convex optimization," Computational Optimization and Applications, Springer, vol. 77(3), pages 729-754, December.
More about this item
Keywords
quadratic assignment problem; semidefinite relaxation; doubly nonnegative relaxation; facial reduction; Peaceman-Rachford splitting method;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2125-2143. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.