The circle packing problem: a theoretical comparison of various convexification techniques
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911827500204032 |
|---|---|
| author | Khajavirad, Aida |
| author_facet | Khajavirad, Aida |
| contents | We consider the problem of packing congruent circles with the maximum radius in a unit square as a mathematical optimization problem. Due to the presence of non-overlapping constraints, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem, which possesses many local optima. We consider several popular convexification techniques, giving rise to linear programming relaxations and semidefinite programming relaxations for the circle packing problem. We compare the strength of these relaxations theoretically, thereby proving the conjectures by Anstreicher (JOGO, 2009). Our results serve as a theoretical justification for the ineffectiveness of existing machinery for convexification of non-overlapping constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03091 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The circle packing problem: a theoretical comparison of various convexification techniques Khajavirad, Aida Optimization and Control We consider the problem of packing congruent circles with the maximum radius in a unit square as a mathematical optimization problem. Due to the presence of non-overlapping constraints, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem, which possesses many local optima. We consider several popular convexification techniques, giving rise to linear programming relaxations and semidefinite programming relaxations for the circle packing problem. We compare the strength of these relaxations theoretically, thereby proving the conjectures by Anstreicher (JOGO, 2009). Our results serve as a theoretical justification for the ineffectiveness of existing machinery for convexification of non-overlapping constraints. |
| title | The circle packing problem: a theoretical comparison of various convexification techniques |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2404.03091 |