The semimetric polytope is an important polyhedral structure lying at the heart of hard combinatorial problems. Therefore, linear optimization over the semimetric polytope is crucial for a number of relevant applications. Building on some recent polyhedral and algorithmic results about a related polyhedron, the rooted semimetric polytope, we develop and test several approaches, mainly based over Lagrangian relaxation and application of Non Differentiable Optimization algorithms, for linear optimization over the semimetric polytope. We show that some of these approaches can obtain very accurate primal and dual solutions in a small fraction of the time required for the same task by state-of-the-art general purpose linear programming technology. In some cases, good estimates of the dual optimal solution (but not of the primal solution) can be obtained even quicker.

New approaches for optimizing over the semimetric polytope

FRANGIONI, ANTONIO;
2005-01-01

Abstract

The semimetric polytope is an important polyhedral structure lying at the heart of hard combinatorial problems. Therefore, linear optimization over the semimetric polytope is crucial for a number of relevant applications. Building on some recent polyhedral and algorithmic results about a related polyhedron, the rooted semimetric polytope, we develop and test several approaches, mainly based over Lagrangian relaxation and application of Non Differentiable Optimization algorithms, for linear optimization over the semimetric polytope. We show that some of these approaches can obtain very accurate primal and dual solutions in a small fraction of the time required for the same task by state-of-the-art general purpose linear programming technology. In some cases, good estimates of the dual optimal solution (but not of the primal solution) can be obtained even quicker.
2005
Frangioni, Antonio; A., Lodi; G., Rinaldi
File in questo prodotto:
File Dimensione Formato  
Lagr4SemiMetric.pdf

accesso aperto

Descrizione: Documento in Post-print
Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 267.78 kB
Formato Adobe PDF
267.78 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/11568/98357
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 18
social impact