In this note, we consider several polynomial optimization formulations of the maximum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior.
A note on the Lasserre hierarchy for different formulations of the maximum independent set problem / Anjos M.F.; Emine Y.; Lodi A.; Sun Z.. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 49:1(2021), pp. 30-34. [10.1016/j.orl.2020.10.009]
A note on the Lasserre hierarchy for different formulations of the maximum independent set problem
Lodi A.;
2021
Abstract
In this note, we consider several polynomial optimization formulations of the maximum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
