Partial lasserre relaxation for sparse max-cut
File(s)
Published version
Author(s)
Campos, Juan S
Misener, Ruth
Parpas, Panos
Type
Journal Article
Abstract
A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints from the second order Lasserre hierarchy. We explore a variety of approaches for adding a subset of the positive semidefinite constraints of the second order sparse relaxation obtained by using the maximum cliques of the graph’s chordal extension. We apply this idea to sparse graphs of different sizes and densities, and provide evidence of its strengths and limitations when compared to the state-of-the-art Max-Cut solver BiqCrunch and the alternative sparse relaxation CS-TSSOS.
Date Issued
2023-09-01
Date Acceptance
2022-08-08
Citation
Optimization and Engineering, 2023, 24, pp.1983-2004
ISSN
1389-4420
Publisher
Springer
Start Page
1983
End Page
2004
Journal / Book Title
Optimization and Engineering
Volume
24
Copyright Statement
© The Author(s) 2022. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
License URL
Identifier
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000842585800001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Engineering
Engineering, Multidisciplinary
Global optimization
HIERARCHY
Mathematics
Mathematics, Interdisciplinary Applications
Max-Cut
Operations Research & Management Science
Physical Sciences
Polynomial optimization
POLYNOMIAL OPTIMIZATION
PROGRAM
Science & Technology
Semidefinite programming
SEMIDEFINITE RELAXATIONS
Technology
Publication Status
Published
Date Publish Online
2022-08-17