Given a simple graph G (V, E) and a set of traffic demands between the nodes of G, the Network Loading Problem consists of installing minimum cost integer capacities on the edges of G allowing routing of traffic demands. In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of Tight Metric Inequalities, that completely characterize the convex hull of the integer feasible solutions of the problem. We present separation algorithms for Tight Metric Inequalities and a cutting plane algorithm, reporting on computational experience.

Metric Inequalities and the Network Loading Problem

AVELLA P;
2007

Abstract

Given a simple graph G (V, E) and a set of traffic demands between the nodes of G, the Network Loading Problem consists of installing minimum cost integer capacities on the edges of G allowing routing of traffic demands. In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of Tight Metric Inequalities, that completely characterize the convex hull of the integer feasible solutions of the problem. We present separation algorithms for Tight Metric Inequalities and a cutting plane algorithm, reporting on computational experience.
File in questo prodotto:
File Dimensione Formato  
DO_2007.pdf

non disponibili

Licenza: Non specificato
Dimensione 347.42 kB
Formato Adobe PDF
347.42 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/20.500.12070/2869
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 49
  • ???jsp.display-item.citation.isi??? ND
social impact