IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v44y1998i11-part-2ps101-s110.html
   My bibliography  Save this article

Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty

Author

Listed:
  • Manuel Laguna

    (Graduate School of Business, University of Colorado, Campus Box 419, Boulder, Colorado 80309)

Abstract

The problem of expanding the capacity of a single facility in telecommunications network planning is addressed. This problem can be formulated as a time-dependent knapsack, when relevant information is assumed to be known. We introduce the use of scenarios to model uncertainty in key data. The problem is formulated within the robust optimization framework and solved exactly in two phases. The first phase consists of a dynamic programming recursion and the second one of a shortest path procedure. Experiments show that a large number of scenarios can be handled with this technique, because computational times are more sensitive to the maximum demand across all scenarios than to the number of scenarios considered. A user-interface based on Microsoft Excel is developed as a decision support system for network planners.

Suggested Citation

  • Manuel Laguna, 1998. "Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty," Management Science, INFORMS, vol. 44(11-Part-2), pages 101-110, November.
    • Handle: RePEc:inm:ormnsc:v:44:y:1998:i:11-part-2:p:s101-s110
    DOI: 10.1287/mnsc.44.11.S101
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.44.11.S101
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.44.11.S101?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. Iraj Saniee, 1995. "An Efficient Algorithm for the Multiperiod Capacity Expansion of One Location in Telecommunications," Operations Research, INFORMS, vol. 43(1), pages 187-190, February.
    2. Manuel Laguna & Fred Glover, 1993. "Bandwidth Packing: A Tabu Search Approach," Management Science, INFORMS, vol. 39(4), pages 492-500, April.
    3. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    4. P. C. Gilmore & R. E. Gomory, 1966. "The Theory and Computation of Knapsack Functions," Operations Research, INFORMS, vol. 14(6), pages 1045-1074, December.
    5. John M. Mulvey & Andrzej Ruszczyński, 1995. "A New Scenario Decomposition Method for Large-Scale Stochastic Optimization," Operations Research, INFORMS, vol. 43(3), pages 477-490, June.
    6. Manuel Laguna, 1994. "Clustering for the Design of SONET Rings in Interoffice Telecommunications," Management Science, INFORMS, vol. 40(11), pages 1533-1541, November.
    7. Dimitris Paraskevopoulos & Elias Karakitsos & Berc Rustem, 1991. "Robust Capacity Planning Under Uncertainty," Management Science, INFORMS, vol. 37(7), pages 787-800, July.
    8. Jonsson, Henrik & Jornsten, Kurt & Silver, Edward A., 1993. "Application of the scenario aggregation approach to a two-stage, stochastic, common component, inventory problem with a budget constraint," European Journal of Operational Research, Elsevier, vol. 68(2), pages 196-211, July.
    9. John M. Mulvey & Robert J. Vanderbei & Stavros A. Zenios, 1995. "Robust Optimization of Large-Scale Systems," Operations Research, INFORMS, vol. 43(2), pages 264-281, April.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Francisco Barahona & Stuart Bermon & Oktay Günlük & Sarah Hood, 2005. "Robust capacity planning in semiconductor manufacturing," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(5), pages 459-468, August.
    2. Chen, Andrew N.K. & Goes, Paulo B. & Gupta, Alok & Marsden, James R., 2006. "Heuristics for selecting robust database structures with dynamic query patterns," European Journal of Operational Research, Elsevier, vol. 168(1), pages 200-220, January.
    3. Yin, Yafeng & Madanat, Samer M. & Lu, Xiao-Yun, 2009. "Robust improvement schemes for road networks under demand uncertainty," European Journal of Operational Research, Elsevier, vol. 198(2), pages 470-479, October.
    4. Jimenez, Charlotte & Dauzère-Pérès, Stéphane & Feuillebois, Christian & Pauly, Eric, 2013. "Optimizing the positioning and technological choices of RFID elements for aircraft part identification," European Journal of Operational Research, Elsevier, vol. 227(2), pages 350-357.
    5. Chao Lu & Jie Tao & Qiuxian An & Xiaodong Lai, 2020. "A second-order cone programming based robust data envelopment analysis model for the new-energy vehicle industry," Annals of Operations Research, Springer, vol. 292(1), pages 321-339, September.
    6. Kennington, Jeffery L. & Olinick, Eli V. & Spiride, Gheorghe, 2007. "Basic mathematical programming models for capacity allocation in mesh-based survivable networks," Omega, Elsevier, vol. 35(6), pages 629-644, December.
    7. ZhenFang Liu & GuoHe Huang, 2009. "Dual-Interval Two-Stage Optimization for Flood Management and Risk Analyses," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 23(11), pages 2141-2162, September.
    8. Chen, Andrew N.K., 2006. "Robust optimization for performance tuning of modern database systems," European Journal of Operational Research, Elsevier, vol. 171(2), pages 412-429, June.
    9. Qiang Fu & Tianxiao Li & Song Cui & Dong Liu & Xueping Lu, 2018. "Agricultural Multi-Water Source Allocation Model Based on Interval Two-Stage Stochastic Robust Programming under Uncertainty," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 32(4), pages 1261-1274, March.
    10. S Mudchanatongsuk & F Ordóñez & J Liu, 2008. "Robust solutions for network design under transportation cost and demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 652-662, May.
    11. 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.
    12. Michel Minoux, 2011. "On 2-stage robust LP with RHS uncertainty: complexity results and applications," Journal of Global Optimization, Springer, vol. 49(3), pages 521-537, March.
    13. Yin, Yafeng, 2008. "Robust optimal traffic signal timing," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 911-924, December.
    14. Emmanuel Kwasi Mensah, 2020. "Robust data envelopment analysis via ellipsoidal uncertainty sets with application to the Italian banking industry," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 43(2), pages 491-518, December.
    15. Machado, Bruno & Pimentel, Carina & Sousa, Amaro de, 2023. "Integration planning of freight deliveries into passenger bus networks: Exact and heuristic algorithms," Transportation Research Part A: Policy and Practice, Elsevier, vol. 171(C).
    16. Jitamitra Desai & Shalinee Kishore, 2017. "A global optimization framework for distributed antenna location in CDMA cellular networks," Annals of Operations Research, Springer, vol. 253(1), pages 169-191, June.
    17. Mac Cawley, Alejandro & Maturana, Sergio & Pascual, Rodrigo & Tortorella, Guilherme Luz, 2022. "Scheduling wine bottling operations with multiple lines and sequence-dependent set-up times: Robust formulation and a decomposition solution approach," European Journal of Operational Research, Elsevier, vol. 303(2), pages 819-839.
    18. Shabbir Ahmed & Nikolaos V. Sahinidis, 2003. "An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion," Operations Research, INFORMS, vol. 51(3), pages 461-471, June.
    19. Zhenfang Liu & Yang Zhou & Gordon Huang & Bin Luo, 2019. "Risk Aversion Based Inexact Stochastic Dynamic Programming Approach for Water Resources Management Planning under Uncertainty," Sustainability, MDPI, vol. 11(24), pages 1-22, December.
    20. C A Poojari & C Lucas & G Mitra, 2008. "Robust solutions and risk measures for a supply chain planning problem under uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(1), pages 2-12, January.
    21. 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.

    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. Yan, Shangyao & Tang, Ching-Hui, 2009. "Inter-city bus scheduling under variable market share and uncertain market demands," Omega, Elsevier, vol. 37(1), pages 178-192, February.
    2. Yan, Shangyao & Tang, Ching-Hui, 2007. "A heuristic approach for airport gate assignments for stochastic flight delays," European Journal of Operational Research, Elsevier, vol. 180(2), pages 547-567, July.
    3. Shangyao Yan & Ching-Hui Tang, 2008. "An Integrated Framework for Intercity Bus Scheduling Under Stochastic Bus Travel Times," Transportation Science, INFORMS, vol. 42(3), pages 318-335, August.
    4. Hashem Omrani & Farzane Adabi & Narges Adabi, 2017. "Designing an efficient supply chain network with uncertain data: a robust optimization—data envelopment analysis approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 816-828, July.
    5. V.I. Norkin & G.C. Pflug & A. Ruszczynski, 1996. "A Branch and Bound Method for Stochastic Global Optimization," Working Papers wp96065, International Institute for Applied Systems Analysis.
    6. Cooper, W. W. & Hemphill, H. & Huang, Z. & Li, S. & Lelas, V. & Sullivan, D. W., 1997. "Survey of mathematical programming models in air pollution management," European Journal of Operational Research, Elsevier, vol. 96(1), pages 1-35, January.
    7. Jesús Latorre & Santiago Cerisola & Andrés Ramos & Rafael Palacios, 2009. "Analysis of stochastic problem decomposition algorithms in computational grids," Annals of Operations Research, Springer, vol. 166(1), pages 355-373, February.
    8. Xu, Y. & Huang, G.H. & Qin, X.S. & Cao, M.F., 2009. "SRCCP: A stochastic robust chance-constrained programming model for municipal solid waste management under uncertainty," Resources, Conservation & Recycling, Elsevier, vol. 53(6), pages 352-363.
    9. Darlington, J. & Pantelides, C. C. & Rustem, B. & Tanyi, B. A., 2000. "Decreasing the sensitivity of open-loop optimal solutions in decision making under uncertainty," European Journal of Operational Research, Elsevier, vol. 121(2), pages 343-362, March.
    10. Julia Higle & Suvrajeet Sen, 2006. "Multistage stochastic convex programs: Duality and its implications," Annals of Operations Research, Springer, vol. 142(1), pages 129-146, February.
    11. Og[caron]uzsoy, Cemal Berk & Güven, Sibel, 2007. "Robust portfolio planning in the presence of market anomalies," Omega, Elsevier, vol. 35(1), pages 1-6, February.
    12. Sodhi, ManMohan S. & Tang, Christopher S., 2009. "Modeling supply-chain planning under demand uncertainty using stochastic programming: A survey motivated by asset-liability management," International Journal of Production Economics, Elsevier, vol. 121(2), pages 728-738, October.
    13. Panos Parpas & Berç Rustem, 2007. "Computational Assessment of Nested Benders and Augmented Lagrangian Decomposition for Mean-Variance Multistage Stochastic Problems," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 239-247, May.
    14. Geun-Cheol Lee & Martin Höhenrieder & Jean-Paul Watson & David Woodruff, 2015. "Chance and service level constraints for stochastic generation expansion planning," Netnomics, Springer, vol. 16(3), pages 169-191, December.
    15. Shabbir Ahmed & Nikolaos V. Sahinidis, 2003. "An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion," Operations Research, INFORMS, vol. 51(3), pages 461-471, June.
    16. Jie Sun & Xinwei Liu, 2006. "Scenario Formulation of Stochastic Linear Programs and the Homogeneous Self-Dual Interior-Point Method," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 444-454, November.
    17. Ratanakuakangwan, Sudlop & Morita, Hiroshi, 2021. "Hybrid stochastic robust optimization and robust optimization for energy planning – A social impact-constrained case study," Applied Energy, Elsevier, vol. 298(C).
    18. Jabbarzadeh, Armin & Fahimnia, Behnam & Seuring, Stefan, 2014. "Dynamic supply chain network design for the supply of blood in disasters: A robust model with real world application," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 225-244.
    19. Pereira, Daniel Filipe & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "Design of a sales plan in a hybrid contractual and non-contractual context in a setting of limited capacity: A robust approach," International Journal of Production Economics, Elsevier, vol. 260(C).
    20. Mohammaddust, Faeghe & Rezapour, Shabnam & Farahani, Reza Zanjirani & Mofidfar, Mohammad & Hill, Alex, 2017. "Developing lean and responsive supply chains: A robust model for alternative risk mitigation strategies in supply chain designs," International Journal of Production Economics, Elsevier, vol. 183(PC), pages 632-653.

    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:44:y:1998:i:11-part-2:p:s101-s110. 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: 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.