Approximate Robust Optimization for the Connected Facility Location Problem
MetadataShow full item record
Type of Work30 pages
Citation of Original PublicationBardossy, M. G., & Raghavan, S. (2016). Approximate robust optimization for the Connected Facility Location problem. Discrete Applied Mathematics, 210(LAGOS'13: Seventh Latin-American Algorithms, Graphs, and Optimization Symposium, Playa del Carmen, Mexico - 2013), 246-260. doi:10.1016/j.dam.2015.10.011
Connected Facility Location problem
In this paper we consider the Robust Connected Facility Location (ConFL) problem within the robust discrete optimization framework introduced by Bertsimas and Sim (2003). We propose an Approximate Robust Optimization (ARO) method that uses a heuristic and a lower bounding mechanism to rapidly find high-quality solutions. The use of a heuristic and a lower bounding mechanism–as opposed to solving the robust optimization (RO) problem exactly–within this ARO approach significantly decreases its computational time. This enables one to obtain high quality solutions to large-scale robust optimization problems and thus broadens the scope and applicability of robust optimization (from a computational perspective) to other NP-hard problems. Our computational results attest to the efficacy of the approach.