Boolean quadratic optimization problems occur in a number of applications. Their mixed integer-continuous nature is challenging, since it is inherently NP-hard. For this motivation, semidefinite programming relaxations (SDR’s) are proposed in the literature to approximate the solution, which recasts the problem into convex optimization. Nevertheless, SDR’s do not guarantee the extraction of the correct binary minimizer. In this paper, we present a novel approach to enhance the binary solution recovery. The key of the proposed method is the exploitation of known information on the eigenvalues of the desired solution. As the proposed approach yields a non-convex program, we develop and analyze an iterative descent strategy, whose practical effectiveness is shown via numerical results.
Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems / Cerone, Vito; Fosson, Sophie; Regruto Tomalino, Diego. - ELETTRONICO. - vol. 53 n.2:(2020), pp. 1894-1899. ((Intervento presentato al convegno 21th IFAC World Congress tenutosi a Berlin, Germany (Virtual) nel July 12-17, 2020 [10.1016/j.ifacol.2020.12.2578].
Titolo: | Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems | |
Autori: | ||
Data di pubblicazione: | 2020 | |
Abstract: | Boolean quadratic optimization problems occur in a number of applications. Their mixed integer-co...ntinuous nature is challenging, since it is inherently NP-hard. For this motivation, semidefinite programming relaxations (SDR’s) are proposed in the literature to approximate the solution, which recasts the problem into convex optimization. Nevertheless, SDR’s do not guarantee the extraction of the correct binary minimizer. In this paper, we present a novel approach to enhance the binary solution recovery. The key of the proposed method is the exploitation of known information on the eigenvalues of the desired solution. As the proposed approach yields a non-convex program, we develop and analyze an iterative descent strategy, whose practical effectiveness is shown via numerical results. | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
1-s2.0-S2405896320333309-main.pdf | 2a Post-print versione editoriale / Version of Record | ![]() | Visibile a tuttiVisualizza/Apri |
http://hdl.handle.net/11583/2847109