IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v40y1992i4p678-688.html
   My bibliography  Save this article

A Lagrangian Relaxation Technique for Optimizing Interconnection of Local Area Networks

Author

Listed:
  • Peter C. Fetterolf

    (Arthur D. Little, Incorporated, Cambridge, Massachusetts)

  • G. Anandalingam

    (University of Pennsylvania, Philadelphia, Pennsylvania)

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.

Suggested Citation

  • Peter C. Fetterolf & G. Anandalingam, 1992. "A Lagrangian Relaxation Technique for Optimizing Interconnection of Local Area Networks," Operations Research, INFORMS, vol. 40(4), pages 678-688, August.
    • Handle: RePEc:inm:oropre:v:40:y:1992:i:4:p:678-688
    DOI: 10.1287/opre.40.4.678
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.40.4.678
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.40.4.678?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sinha, Surabhi & Sinha, S. B., 2002. "KKT transformation approach for multi-objective multi-level linear programming problems," European Journal of Operational Research, Elsevier, vol. 143(1), pages 19-31, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:40:y:1992:i:4:p:678-688. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.