IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v42y1996i9p1277-1291.html
   My bibliography  Save this article

An Integer Programming Approach to the Bandwidth Packing Problem

Author

Listed:
  • Kyungchul Park

    (Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Taejon 305-701, Korea)

  • Seokhoon Kang

    (Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Taejon 305-701, Korea)

  • Sungsoo Park

    (Telecom Business Department, Ssangyong Computer Systems Co., Seoul 105-705, Korea)

Abstract

We consider the bandwidth packing problem arising from telecommunication networks. The problem is to determine the set of calls and an assignment of them to the paths in an arc-capacitated network to maximize profit. We propose an algorithm to solve the integer programming formulation of the problem. An efficient column generation technique to solve the linear programming relaxation is proposed, and a modified cover inequality is used to strengthen the IP formulation. The algorithm incorporates the column generation technique and the strong cutting plane approach into a branch-and-bound scheme. We test the proposed algorithm on some random problems. The results show that the algorithm can be used to solve the problems within reasonably small time limits.

Suggested Citation

  • Kyungchul Park & Seokhoon Kang & Sungsoo Park, 1996. "An Integer Programming Approach to the Bandwidth Packing Problem," Management Science, INFORMS, vol. 42(9), pages 1277-1291, September.
    • Handle: RePEc:inm:ormnsc:v:42:y:1996:i:9:p:1277-1291
    DOI: 10.1287/mnsc.42.9.1277
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.42.9.1277
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.42.9.1277?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. Changyong Zhang, 2017. "An origin-based model for unique shortest path routing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 935-951, August.
    2. Fortz, Bernard & Gouveia, Luís & Joyce-Moniz, Martim, 2017. "Models for the piecewise linear unsplittable multicommodity flow problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 30-42.
    3. Jinil Han & Kyungsik Lee & Chungmok Lee & Sungsoo Park, 2013. "Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 585-596, August.
    4. C S Sung & S H Song, 2003. "Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(1), pages 72-82, January.
    5. Kyungchul Park & Kyungsik Lee & Sungsoo Park & Heesang Lee, 2000. "Telecommunication Node Clustering with Node Compatibility and Network Survivability Requirements," Management Science, INFORMS, vol. 46(3), pages 363-374, March.
    6. Vidyarthi, Navneet & Jayaswal, Sachin & Chetty, Vikranth Babu Tirumala, 2013. "Exact Solution to Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2013-11-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    7. Baris Yildiz & Martin Savelsbergh, 2019. "Provably High-Quality Solutions for the Meal Delivery Routing Problem," Transportation Science, INFORMS, vol. 53(5), pages 1372-1388, September.
    8. Amiri, Ali, 2005. "The selection and scheduling of telecommunication calls with time windows," European Journal of Operational Research, Elsevier, vol. 167(1), pages 243-256, November.
    9. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    10. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2009. "Optimal multicast route packing," European Journal of Operational Research, Elsevier, vol. 196(1), pages 351-359, July.
    11. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2004. "ATM VP-based network design," European Journal of Operational Research, Elsevier, vol. 158(3), pages 555-569, November.
    12. Kurt DeMaagd & Johannes M. Bauer, 2011. "Modeling the dynamic interactions of agents in the provision of network infrastructure," Information Systems Frontiers, Springer, vol. 13(5), pages 669-680, November.
    13. Amiri, Ali & Rolland, Erik & Barkhi, Reza, 1999. "Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures," European Journal of Operational Research, Elsevier, vol. 112(3), pages 635-645, February.
    14. Navneet Vidyarthi & Sachin Jayaswal & Vikranth Babu Tirumala Chetty, 2016. "Bandwidth packing problem with queueing delays: modelling and exact solution approach," Journal of Global Optimization, Springer, vol. 65(4), pages 745-776, August.
    15. François Lamothe & Emmanuel Rachelson & Alain Haït & Cedric Baudoin & Jean-Baptiste Dupé, 2021. "Randomized rounding algorithms for large scale unsplittable flow problems," Journal of Heuristics, Springer, vol. 27(6), pages 1081-1110, December.
    16. Seohee Kim & Chungmok Lee, 2021. "A branch and price approach for the robust bandwidth packing problem with queuing delays," Annals of Operations Research, Springer, vol. 307(1), pages 251-275, December.
    17. Barış Yıldız & Oya Ekin Karaşan, 2017. "Regenerator Location Problem in Flexible Optical Networks," Operations Research, INFORMS, vol. 65(3), pages 595-620, June.
    18. Jayaswal, Sachin & Vidyarthi, Navneet & Das, Sagnik, 2014. "An Efficient Solution Approach for Combinatorial Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2014-12-05, Indian Institute of Management Ahmedabad, Research and Publication Department.
    19. Amiri, Ali & Barkhi, Reza, 2011. "The combinatorial bandwidth packing problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 37-45, January.
    20. Bose, Indranil, 2009. "Bandwidth packing with priority classes," European Journal of Operational Research, Elsevier, vol. 192(1), pages 313-325, January.

    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:ormnsc:v:42:y:1996:i:9:p:1277-1291. 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.