The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance.

The stable set problem: Clique and nodal inequalities revisited

Rossi F.;Smriglio S.
2020

Abstract

The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance.
File in questo prodotto:
File Dimensione Formato  
preprint.pdf

embargo fino al 30/06/2023

Descrizione: Articolo
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 815.39 kB
Formato Adobe PDF
815.39 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/160402
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact