An inexact sample average approximation approach for the stochastic connected facility location problem. Issue 1 (28th April 2017)

• Record Type: Journal Article
• Authors: Bardossy, M. Gisela; Raghavan, S.
• Is Part Of: Networks. Volume 70:Issue 1(2017)
• Page Start: 19
• Page End: 33
• Publication Date: 2017-04-28
• Subjects: heuristics -- network design -- network optimization -- stochastic optimization -- connected facility location problem -- uncapacitated facility location problem -- sample average approximation; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21743
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : The sample average approximation (SAA) approach is a widely used technique, based on Monte‐Carlo simulation, often applied to large‐scale stochastic optimization problems. In this approach, a set of sample average problems with multiple copies of sampled scenarios are generated and solved exactly. In other words, there is an implicit assumption that the sample average problems are solvable to optimality. In some instances, however, the sample average problems might be NP‐hard problems, often difficult or impractical to solve to optimality. In this article, we broaden the scope of the SAA approach and show that even without solving the sample problems to optimality, by combining a heuristic and a lower bounding approach, high‐quality solutions with tight confidence bounds on the optimal solution value can be obtained. We demonstrate this "inexact SAA approach" on two problems. First, we apply it to the Stochastic Connected Facility Location (SConFL) problem, the motivating application for this article, that arises in the design of telecommunications networks. As an additional application, we also use it for the Stochastic Uncapacitated Facility Location (SUFL) problem. Our computational results demonstrate the effectiveness of the inexact SAA approach. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 19–33 2017