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

A Capacity Improvement Lower Bound for Fixed Charge Network Design Problems

Author

Listed:
  • Bruce W. Lamar

    (University of California, Irvine, California)

  • Yosef Sheffi

    (Massachusetts Institute of Technology, Cambridge, Massachusetts)

  • Warren B. Powell

    (Princeton University, Princeton, New Jersey)

Abstract

Network design problems concern flows over networks in which a fixed charge must be incurred before an arc becomes available for use. The uncapacitated, multicommodity network design problem is modeled with aggregate and disaggregate forcing constraints. (Forcing constraints ensure logical relationships between the fixed charge-related and the flow-related decision variables.) A new lower bound for this problem—referred to as the capacity improvement (CI) bound—is presented; and an efficient implementation scheme using shortest path and linearized knapsack programs is described. A key feature of the CI lower bound is that it is based on the LP relaxation of the aggregate version of the problem. A numerical example illustrates that the CI lower bound can converge to the optimal objective function value of the IP formulation.

Suggested Citation

  • Bruce W. Lamar & Yosef Sheffi & Warren B. Powell, 1990. "A Capacity Improvement Lower Bound for Fixed Charge Network Design Problems," Operations Research, INFORMS, vol. 38(4), pages 704-710, August.
    • Handle: RePEc:inm:oropre:v:38:y:1990:i:4:p:704-710
    DOI: 10.1287/opre.38.4.704
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.38.4.704
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.38.4.704?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. Gavin J. Bell & Bruce W. Lamar & Chris A. Wallace, 1999. "Capacity improvement, penalties, and the fixed charge transportation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(4), pages 341-355, June.
    2. Julie A. Ward, 1999. "Minimum-Aggregate-Concave-Cost Multicommodity Flows in Strong-Series-Parallel Networks," Mathematics of Operations Research, INFORMS, vol. 24(1), pages 106-129, February.
    3. Cynthia Barnhart & Hong Jin & Pamela H. Vance, 2000. "Railroad Blocking: A Network Design Application," Operations Research, INFORMS, vol. 48(4), pages 603-614, August.
    4. Kaj Holmberg & Di Yuan, 2000. "A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem," Operations Research, INFORMS, vol. 48(3), pages 461-481, June.
    5. Linos F. Frantzeskakis & Hanan Luss, 1999. "The network redesign problem for access telecommunications networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 487-506, August.
    6. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.
    7. Arnt-Gunnar Lium & Teodor Gabriel Crainic & Stein W. Wallace, 2009. "A Study of Demand Stochasticity in Service Network Design," Transportation Science, INFORMS, vol. 43(2), pages 144-157, May.
    8. Teodor Gabriel Crainic & Michel Gendreau & Judith M. Farvolden, 2000. "A Simplex-Based Tabu Search Method for Capacitated Network Design," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 223-236, August.
    9. Francesca Maggioni & Florian A. Potra & Marida Bertocchi, 2017. "A scenario-based framework for supply planning under uncertainty: stochastic programming versus robust optimization approaches," Computational Management Science, Springer, vol. 14(1), pages 5-44, January.
    10. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.

    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:38:y:1990:i:4:p:704-710. 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.