Facility Location Problem (I)

This problem is given as follows:

$$\begin{array}{rcl} \mbox{min} &\sum_{i=1}^m w_it_i \cr \mbox{... ..._{j=1}^d(x_j-a_{ij})^2}\leq t_i,\mbox{ for } i=1:m, \end{array}$$ (3-4)

where $d$ is the dimension, $m$ is the number of existing facilities, $(a_{i1},a_{i2})$ are the coordinates of the existing facility (if $d=2$), and $w_i$ is the weight associated with the old-new facility. The model describes that one plans to build a new facility among existing facilities and chooses the location which minimizes the weights associated with the Euclidean distance between the new and existing locations. For simplicity, we consider $d=2$. It is trivial to extend to higher dimensions. Let

$$u_{ij}=x_j-a_{ij},$$ for $$i=1:m,$$ and $$j=1:2.$$

We then introduce new linear constraints

$$u_{11}+a_{11}=u_{i1}+a_{i1},$$  $$u_{12}+a_{12}=u_{i2}+a_{i2},$$    for $$i=2:m.$$

Therefore, the problem becomes

$$\begin{array}{rcl} \mbox{min}& \sum_{i=1}^m w_it_i\cr \mbox{s... ... \sum_{j=1}^2 u_{ij}^2\leq t_i^2, t_i\geq 0, i=1:m. \end{array}$$ (3-5)

We denote

$$x^i=\begin{pmatrix}t_i\cr u_{i1}\cr u_{i2}\end{pmatrix}, c^i=\beg... ...ts \cr a_{m1}-a_{11}\cr a_{22}-a_{12} \cr \vdots \cr a_{m2}-a_{22}\end{pmatrix}$$

and $x=\begin{pmatrix}x^1\cr \vdots \cr x^m\end{pmatrix}, c=\begin{pmatrix}c^1\cr \vdots \cr c^m\end{pmatrix}.$ Hence, one obtains the SOCP formulation.

Example 2. The coordinates of the existing facilities and the weight associated with each existing facility are both generated by a uniform random number generator. We use $m=50,100,150,200$ to create four problems.