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 the traffic demands. In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of the 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 / Pasquale, Avella; Sara, Mattia; Sassano, Antonio. - 3064:(2004), pp. 16-32. (Intervento presentato al convegno 10th International Integer Programming and Combinatorial Optimization Conference tenutosi a New York, NY; USA) [10.1007/978-3-540-25960-2_2].
Metric inequalities and the network loading problem
SASSANO, Antonio
2004
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 the traffic demands. In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of the 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
