We describe a general method for deriving new inequalities for integer programming formulations of combinatorial optimization problems. The inequalities, motivated by local search algorithms, are valid for all optimal solutions but not necessarily for all feasible solutions. These local search inequalities can help in either pruning the search tree at some nodes or in improving the bound of the LP relaxations.

Local search inequalities

LANCIA, Giuseppe;RINALDI, Franca;SERAFINI, Paolo
2015-01-01

Abstract

We describe a general method for deriving new inequalities for integer programming formulations of combinatorial optimization problems. The inequalities, motivated by local search algorithms, are valid for all optimal solutions but not necessarily for all feasible solutions. These local search inequalities can help in either pruning the search tree at some nodes or in improving the bound of the LP relaxations.
File in questo prodotto:
File Dimensione Formato  
final_published.pdf

accesso aperto

Descrizione: editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 462.71 kB
Formato Adobe PDF
462.71 kB Adobe PDF Visualizza/Apri

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