ROBUST SOLUTIONS TO EUCLIDEAN FACILITY LOCATION PROBLEMS WITH UNCERTAIN DATA

摘要

We consider uncertainty Euclidean facility location problems. Using the existing robust optimization methodology, we certainly obtain robust optimal solution of the Euclidean facility location problem with unknown-but-bounded uncertainty or with an ellipsoidal uncertainty by solving an SOCP or an SDP. In addition, we show that the robust counterpart of the Euclidean facility location problem with fl-ellipsoidal uncertainty is NP-hard. We give an explicit SDP to approximate the NP-hard problem and estimate the quality of the approximation via the level of conservativeness.