Approximate Robust Optimization for the Connected Facility Location Problem

Abstract

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.