Facility Location Problem (II)

The second facility location problem we present has the following model:

$$\sum_{i=1}^m\sum_{j=1}^n w_{ij}\sqrt{\sum_{k=1}^2(x_{jk}-a_{ik})^2}+\sum_{j=1}^n\sum_{jj=1}^j v_{j,jj}\sqrt{\sum_{k=1}^2(x_{j,k}-x_{jj,k})^2},$$ (3-6)

where the definitions for $m$, $a$, and $w$ are the same as in the previous case, $n$ is the number of new facilities, and $v_{j,jj}$ are the weights of the new-new connections. In a AMPL model, emfl.mod in [16], $v$ is defined as constant and $w$ is decided by the initial guess. The way of defining $v$ and $w$ does not seem realistic; however, they are still reasonable if one has a good a initial guess. We now convert this problem to SOCP format. First, we introduce $s_{ij}\geq 0,i=1:m,j=1:n$, and $t_{j,jj}\geq 0, j=1:n,jj<j$. Similarly, we need some additional variables to replace $x_{jk}-a_{jk}$, and $x_{j,k}-x_{jj,k}$. By rewriting $w$ and $v$ appropriately, we obtain the SOCP formulation.

Example 3. To consider a simplified problem, we take an AMPL model, emfl.mod, from [16]. In this model, the coordinates of the existing facilities are generated randomly, the weight associated with the new-new connections is fixed at $.2$, and the weight associated with the old-new connection is fixed by the distance between the old facilities and the initial guesses. We use the following four cases, (i) $m=10,n=4,$ (ii) $m=20,n=4,$ (iii) $m=30, n=9,$ and (iv) $m=40,n=9.$