Experiments with a hybrid interior point/combinatorial approach for network flow problems (Articolo in rivista)

Type

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

Label

• Experiments with a hybrid interior point/combinatorial approach for network flow problems (Articolo in rivista) (literal)

Anno

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

Alternative label

• Frangioni, A.; Gentile, C. (2007)
  Experiments with a hybrid interior point/combinatorial approach for network flow problems
  in Optimization methods & software (Print)
  (literal)

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

• Frangioni, A.; Gentile, C. (literal)

Pagina inizio

• 573 (literal)

Pagina fine

• 585 (literal)

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

• 22 (literal)

Rivista

• Optimization methods & software (Rivista)

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

• n. 4 ISSN 1055-6788 (literal)

Note

• ISI Web of Science (WOS) (literal)

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

• Frangioni Antonio, Università di Pisa, Dipartimento di Informatica, associato presso IASI (literal)

Titolo

• Experiments with a hybrid interior point/combinatorial approach for network flow problems (literal)

Abstract

• Interior Point (IP) algorithms for Min Cost Flow (MCF) problems have been shown to be competitive with combinatorial approaches, at least on some problem classes and for very large instances. This is in part due to availability of specialized crossover routines for MCF; these allow early termination of the IP approach, sparing it with the final iterations where the KKT systems become more difficult to solve. As the crossover procedures are nothing but combinatorial approaches to MCF that are only allowed to perform few iterations, the IP algorithm can be seen as a complex ``multiple crash start'' routine for the combinatorial ones. We report our experiments about allowing one primal-dual combinatorial algorithm to MCF to perform as many iterations as required to solve the problem after being warm-started by an IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the original combinatorial algorithm, at least on some ``difficult'' instances. (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

• ANTONIO FRANGIONI (Unità di personale esterno)
• CLAUDIO GENTILE (Persona)

Insieme di parole chiave

• Keywords of "Experiments with a hybrid interior point/combinatorial approach for network flow problems" (Insieme di parole chiave)

Incoming links:

Autore CNR di

• CLAUDIO GENTILE (Persona)
• ANTONIO FRANGIONI (Unità di personale esterno)

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

• Optimization methods & software (Rivista)

Insieme di parole chiave di

• Keywords of "Experiments with a hybrid interior point/combinatorial approach for network flow problems" (Insieme di parole chiave)