Metric inequalities and the Network Loading Problem |
| |
Authors: | Pasquale Avella Sara Mattia Antonio Sassano |
| |
Affiliation: | aResearch Center on Software Technology, Università del Sannio, Viale Traiano, 82100 Benevento, Italy;bDipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Via Buonarroti, 12, 00185 Roma, Italy |
| |
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. |
| |
Keywords: | Network loading Metric inequalities Cutting planes |
本文献已被 ScienceDirect 等数据库收录! |
|