Robust solutions to Euclidean facility location problems with uncertain data (Q620015)

Let \(b_{1},\dots ,b_{m}\in\mathbb R^{l}~(m\geq 2)\) be column vectors in the Euclidean \(l \)-space and \(A_{1},\dots ,A_{m}\in \mathbb R^{n\times l}~(m\geq 2)\) be \( n\)-by-\(l\) matrices with each having full column rank. The Euclidean facility location (EFL) problem is expressed as finding a point \(x\in\mathbb R^{n}\) such that the following sum of Euclidean norms is minimized: \[ \min_{x\in\mathbb R^{n}}\sum_{i=1}^{m}\| b_{i}-A_{i}^{T}x\| , \] where superscript \(^{T}\) is the transpose operator. In this paper the authors use the existing robust optimization methodology to obtain robust solutions of the EFL problem under the following four cases of uncertainty set: unknown-but-bounded uncertainty, an ellipsoidal uncertainty, \(\cap \)-ellipsoidal uncertainty, and box uncertainty. For the first two cases, they equivalently formulate the robust EFL problem as an second-order cone programming (SOCP) or an semidefinite programming (SDP) problem. For the latter two cases, the robust Euclidean facility location problem is shown to be NP-hard. They establish an explicit SDP to approximate the robust Euclidean facility location problem and estimate the quality of the approximation via the measure the level of conservativeness.