Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.

Computational study of separation algorithms for clique inequalities

Marzi F.;Rossi F.;Smriglio S.
2019-01-01

Abstract

Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.
File in questo prodotto:
File Dimensione Formato  
Revised1_0.pdf

solo utenti autorizzati

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

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/142946
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact