SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908402113839104 |
|---|---|
| author | Sinjorgo, Lennart Sotirov, Renata Vera, Juan C. |
| author_facet | Sinjorgo, Lennart Sotirov, Renata Vera, Juan C. |
| contents | We consider the Lasserre hierarchy for computing bounds on the stability number of graphs. The semidefinite programs (SDPs) arising from this hierarchy involve large matrix variables and many linear constraints, which makes them difficult to solve using interior-point methods. We propose solving these SDPs using the alternating direction method of multipliers (ADMM). When the second level of the Lasserre hierarchy for a given graph is intractable for the ADMM, we consider an intermediate-level relaxation of the hierarchy. To warm-start the ADMM, we use an optimal solution from the first level of the Lasserre hierarchy, which is equivalent to the well-known Lovász theta function. Additionally, we use this solution to determine which degree two monomials to add in the Lasserre hierarchy relaxation to obtain an intermediate level between 1 and 2. Computational results demonstrate that our approach yields strong bounds on the stability number, which are computable within reasonable running times. We provide the best-known bounds on the stability number of various graphs from the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08648 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy Sinjorgo, Lennart Sotirov, Renata Vera, Juan C. Optimization and Control 90C22, 90C27 We consider the Lasserre hierarchy for computing bounds on the stability number of graphs. The semidefinite programs (SDPs) arising from this hierarchy involve large matrix variables and many linear constraints, which makes them difficult to solve using interior-point methods. We propose solving these SDPs using the alternating direction method of multipliers (ADMM). When the second level of the Lasserre hierarchy for a given graph is intractable for the ADMM, we consider an intermediate-level relaxation of the hierarchy. To warm-start the ADMM, we use an optimal solution from the first level of the Lasserre hierarchy, which is equivalent to the well-known Lovász theta function. Additionally, we use this solution to determine which degree two monomials to add in the Lasserre hierarchy relaxation to obtain an intermediate level between 1 and 2. Computational results demonstrate that our approach yields strong bounds on the stability number, which are computable within reasonable running times. We provide the best-known bounds on the stability number of various graphs from the literature. |
| title | SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy |
| topic | Optimization and Control 90C22, 90C27 |
| url | https://arxiv.org/abs/2506.08648 |