IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v63y2016i5p351-366.html
   My bibliography  Save this article

Column generation for stochastic green telecommunication network planning with switchable base stations

Author

Listed:
  • Jonas Christoffer Villumsen
  • Joe Naoum‐Sawaya

Abstract

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two‐stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig‐Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig‐Wolfe reformulation provides solutions with a tight LP‐gap eliminating the need for a full branch‐and‐price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 351–366, 2016

Suggested Citation

  • Jonas Christoffer Villumsen & Joe Naoum‐Sawaya, 2016. "Column generation for stochastic green telecommunication network planning with switchable base stations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(5), pages 351-366, August.
  • Handle: RePEc:wly:navres:v:63:y:2016:i:5:p:351-366
    DOI: 10.1002/nav.21701
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21701
    Download Restriction: no

    File URL: https://libkey.io/10.1002/nav.21701?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
    ---><---

    References listed on IDEAS

    as
    1. Joe Naoum‐Sawaya & Samir Elhedhli, 2010. "A nested benders decomposition approach for telecommunication network planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(6), pages 519-539, September.
    2. Villumsen, J.C. & Philpott, A.B., 2012. "Investment in electricity networks with transmission switching," European Journal of Operational Research, Elsevier, vol. 222(2), pages 377-385.
    3. Andreas Eisenblätter & Hans-Florian Geerdes & Thorsten Koch & Alexander Martin & Roland Wessäly, 2006. "UMTS radio network evaluation and optimization beyond snapshots," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(1), pages 1-29, February.
    4. Eli Olinick, 2011. "Mathematical Programming Models for Third Generation Wireless Network Design," International Series in Operations Research & Management Science, in: Jeff Kennington & Eli Olinick & Dinesh Rajan (ed.), Wireless Network Design, chapter 0, pages 101-125, Springer.
    5. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    6. Olinick, Eli V. & Rosenberger, Jay M., 2008. "Optimizing revenue in CDMA networks under demand uncertainty," European Journal of Operational Research, Elsevier, vol. 186(2), pages 812-825, April.
    7. Joakim Kalvenes & Jeffery Kennington & Eli Olinick, 2006. "Base Station Location and Service Assignments in W--CDMA Networks," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 366-376, August.
    8. Jay M. Rosenberger & Eli V. Olinick, 2007. "Robust tower location for code division multiple access networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 151-161, March.
    9. Kavinesh J. Singh & Andy B. Philpott & R. Kevin Wood, 2009. "Dantzig-Wolfe Decomposition for Solving Multistage Stochastic Capacity-Planning Problems," Operations Research, INFORMS, vol. 57(5), pages 1271-1286, October.
    10. Edoardo Amaldi & Pietro Belotti & Antonio Capone & Federico Malucelli, 2006. "Optimizing base station location and configuration in UMTS networks," Annals of Operations Research, Springer, vol. 146(1), pages 135-151, September.
    11. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Joe Naoum‐Sawaya & Samir Elhedhli, 2010. "A nested benders decomposition approach for telecommunication network planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(6), pages 519-539, September.
    2. Chen, Lei & Yuan, Di, 2010. "Solving a minimum-power covering problem with overlap constraint for cellular network design," European Journal of Operational Research, Elsevier, vol. 203(3), pages 714-723, June.
    3. Zhouchun Huang & Qipeng P. Zheng & Andrew L. Liu, 2022. "A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1919-1939, July.
    4. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    5. Thomas W. M. Vossen & R. Kevin Wood & Alexandra M. Newman, 2016. "Hierarchical Benders Decomposition for Open-Pit Mine Block Sequencing," Operations Research, INFORMS, vol. 64(4), pages 771-793, August.
    6. Allman, Andrew & Zhang, Qi, 2020. "Dynamic location of modular manufacturing facilities with relocation of individual modules," European Journal of Operational Research, Elsevier, vol. 286(2), pages 494-507.
    7. Yiting Xing & Ling Li & Zhuming Bi & Marzena Wilamowska‐Korsak & Li Zhang, 2013. "Operations Research (OR) in Service Industries: A Comprehensive Review," Systems Research and Behavioral Science, Wiley Blackwell, vol. 30(3), pages 300-353, May.
    8. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    9. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    10. Bani, Abderrahman & El Hallaoui, Issmail & Corréa, Ayoub Insa & Tahir, Adil, 2023. "Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints," European Journal of Operational Research, Elsevier, vol. 311(1), pages 154-172.
    11. Borgonjon, Tessa & Maenhout, Broos, 2022. "An exact approach for the personnel task rescheduling problem with task retiming," European Journal of Operational Research, Elsevier, vol. 296(2), pages 465-484.
    12. H. Fei & C. Chu & N. Meskens, 2009. "Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria," Annals of Operations Research, Springer, vol. 166(1), pages 91-108, February.
    13. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    14. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    15. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    16. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    17. Kristiansen, Simon & Sørensen, Matias & Stidsen, Thomas R., 2011. "Elective course planning," European Journal of Operational Research, Elsevier, vol. 215(3), pages 713-720, December.
    18. Panagiotis Andrianesis & Dimitris Bertsimas & Michael C. Caramanis & William W. Hogan, 2020. "Computation of Convex Hull Prices in Electricity Markets with Non-Convexities using Dantzig-Wolfe Decomposition," Papers 2012.13331, arXiv.org, revised Oct 2021.
    19. Brønmo, Geir & Nygreen, Bjørn & Lysgaard, Jens, 2006. "Column generation approaches to ship scheduling with flexible cargo sizes," CORAL Working Papers L-2006-07, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    20. Pereira Lopes, Manuel J. & de Carvalho, J.M. Valerio, 2007. "A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1508-1527, February.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:63:y:2016:i:5:p:351-366. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.