A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

In this note, we consider several polynomial optimization formulations of the max- imum 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.

Citation

Technical Report Polytechnique Montreal, 2020

Article

Download

View A note on the Lasserre hierarchy for different formulations of the maximum independent set problem