A Lagrangian Relaxation Technique for Optimizing Interconnection of Local Area Networks

Peter C. Fetterolf and G. Anandalingam
Additional contact information
Peter C. Fetterolf: Arthur D. Little, Incorporated, Cambridge, Massachusetts
G. Anandalingam: University of Pennsylvania, Philadelphia, Pennsylvania

Operations Research, 1992, vol. 40, issue 4, 678-688

Abstract: This paper addresses the problem of interconnecting a group of Local Area Networks (LANs) with bridges. The network designer would like to minimize the cost of connecting the LANs while maintaining acceptable traffic intensity levels on each of the LANs and the bridges. This problem belongs to the class of fixed charge network flow problems. A Lagrangian relaxation algorithm is proposed that incorporates two sets of constraints into the objective function. The relaxed problem has a special structure and can be solved as a minimum spanning tree problem and a set of shortest path problems. The subgradient algorithm is then used to maximize the Lagrangian dual. A Lagrangian heuristic algorithm is also proposed to find good primal feasible solutions. For problems with five LANs, the heuristic solutions are normally within 1% of the optimum. For larger problems the heuristic solutions are close to the lower bounds generated by the Lagrangian relaxation algorithm. This suggests that the quality of the heuristic solutions does not deteriorate as the dimension of the problem grows.

Keywords: facilities/equipment planning: designing LAN internetworks; networks/graphs: modeling an LAN-internetwork as a graph; programming; integer: Lagrangian relaxation heuristic algorithm (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.4.678 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:4:p:678-688

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().