Metric inequalities and the Network Loading Problem

Metric inequalities and the Network Loading Problem

0.00 Avg rating0 Votes
Article ID: iaor20073114
Country: Netherlands
Volume: 4
Issue: 1
Start Page Number: 103
End Page Number: 114
Publication Date: Mar 2007
Journal: Discrete Optimization
Authors: , ,
Keywords: networks
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.

Reviews

Required fields are marked *. Your email address will not be published.