The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation (Articolo in rivista) (literal)

Anno

• 2007-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1287/moor.1060.0244 (literal)

Alternative label

• Naddef, D.; Rinaldi, G. (2007)
  The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
  in Mathematics of operations research
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Naddef, D.; Rinaldi, G. (literal)

Pagina inizio

• 233 (literal)

Pagina fine

• 256 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 32 (literal)

Rivista

• Mathematics of operations research (Rivista)

Note

• Google Scholar (literal)
• ISI Web of Science (WOS) (literal)
• Mathematical Reviews on the web (MathSciNet) (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• Naddef, D; Laboratoire G-SCOP, Institut National Polytechnique de Grenoble, 46, avenue Félix-Viallet, 38031 Grenoble, France (literal)

Titolo

• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation (literal)

Abstract

• The path, the wheelbarrow, and the bicycle inequalities have been shown by Cornuéjols, Fonlupt, and Naddef to be facet-defining for the graphical relaxation of STSP(n), the polytope of the symmetric traveling salesman problem on an n-node complete graph. We show that these inequalities, and some generalizations of them, define facets also for STSP(n). In conclusion, we characterize a large family of facet-defining inequalities for STSP(n) that include, as special cases, most of the inequalities currently known to have this property as the comb, the clique tree, and the chain inequalities. Most of the results given here come from a strong relationship of STSP(n) with its graphical relaxation that we have pointed out in another paper, where the basic proof techniques are also described. (literal)

Prodotto di

• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)
• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)

Autore CNR

• GIOVANNI RINALDI (Unità di personale interno)

Insieme di parole chiave

• Keywords of "The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation" (Insieme di parole chiave)

Incoming links:

Autore CNR di

• GIOVANNI RINALDI (Unità di personale interno)

Prodotto

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Mathematics of operations research (Rivista)

Insieme di parole chiave di

• Keywords of "The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation" (Insieme di parole chiave)