Applying robust optimization to capacity expansion of one location in telecommunications with demand uncertainty

• 成果类型: Article
• 署名作者: Laguna, M
• 署名单位: University of Colorado System; University of Colorado Boulder
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.44.11.S101
• 发表日期: 1998
• 页码: S101-S110
• 关键词: capacity expansion; robust optimization; time-dependent knapsack problem

摘要

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.