Continuous location under the effect of ‘refraction’

Abstract

In this paper we address the problem of locating a new facility on a d-dimensional space when the distance measure ($\ell _p$- or polyhedral-norms) is different at each one of the sides of a given hyperplane $\mathcal {H}$. We relate this problem with the physical phenomenon of refraction, and extend it to any finite dimensional space and different distances at each one of the sides of any hyperplane. An application to this problem is the location of a facility within or outside an urban area where different distance measures must be used. We provide a new second order cone programming formulation, based on the $\ell _p$-norm representation given in Blanco et al. (Comput Optim Appl 58(3):563–595, 2014) that allows to solve the problem in any finite dimensional space with second order cone or semidefinite programming tools. We also extend the problem to the case where the hyperplane is considered as a rapid transit media (a different third norm is also considered over $\mathcal {H}$) that allows the demand to travel, whenever it is convenient, through $\mathcal {H}$ to reach the new facility. Extensive computational experiments run in Gurobi are reported in order to show the effectiveness of the approach. Some extensions of these models are also presented.

1 Introduction

In the literature of transportation research it is frequent to address routing or distribution problems where the movement between points is modeled by the combination of different transportation modes, as for instance a standard displacement combined with several high speed lines. Similar approaches have been also applied in some location problems [9] considering that movements can be performed in a continuous framework or taking advantage of a rapid transit line modeled by an embedded network; and different applications of these models are mentioned in the location literature. For instance, the location of a facility within or outside an urban area where, due to the layout of the streets within the city boundary, the movement is slow, while outside this boundary in the rural area movement is fast. Another possible application, mentioned by Brimberg et al. [6] could be in a region where, due to the configuration of natural barriers or borders, there is a distinct change in the orientation of the transportation network, as for instance in the southern area of Ontario.

Location problems are among the most important applications of Operation Research. Continuous location problems appear very often in economic models of distribution or logistics, in statistics when one tries to find an estimator from a data set or in pure optimization problems where one looks for the optimizer of a certain function. For a comprehensive overview of Location Theory, the reader is referred to [10] or [21]. Most of the papers in the literature devoted to continuous facility location consider that the decision space is $\mathbb {R}^d$, endowed with a unique distance. We consider here the problem where $\mathbb {R}^d$ is split by a hyperplane $\mathcal {H}=\{x \in \mathbb {R}^d: \alpha ^t x = \beta \}$ for some $\alpha \in \mathbb {R}^d$ and $\beta \in \mathbb {R}$, into two regions ${\mathrm{H}}_A$ and ${\mathrm{H}}_B$, with sets of demand points A and B, respectively. Each one of these regions is endowed with a (possibly different) norm $\Vert \cdot \Vert _{A}$ and $\Vert \cdot \Vert _{B}$, respectively, to measure the distance within the corresponding region. For the ease of presentation we will restrict ourselves to consider that the involved norms are $\ell _p$, $p>1$, or polyhedral. Recall that a polyhedral (or block) norm is characterized by a unit ball being a polytope symmetric with respect to the origin and with non empty interior. The only $\ell _p$-norms that are polyhedral are the well-known $\ell _1$- and $\ell _{\infty }$-norm. Therefore, we deal with the problem of finding the location of a new facility such that the overall sum of the weighted distances from the demand points is minimized. This setting induces a transportation pattern where, in each side of the hyperplane, the motion goes at a different speed. This problem is not new and we can find antecedents in the literature in the papers by Parlar [18], Brimberg et al. [6, 7], Fathaly [14], among others, and it can be seen as a natural generalization of the classical Weber’s problem (see [13, 20]). Note that the distances between two points, depending on the region where they are located, may be measured with different norms. Hence, the distance between two points x and y is $\Vert x-y\Vert _{A}$ (resp. $\Vert x-y\Vert _{B}$) if they belong to ${\mathrm{H}}_A$ (resp. to ${\mathrm{H}}_B$), or the length of the shortest weighted path between them otherwise. We point out that in this setting if two points x and y are in the same half-space, it is not allowed to traverse the hyperplane on paths connecting them. The reader is referred to Sect. 6.2 for the analysis of this latter case. Related problems have been analyzed in [1, 3, 5, 8, 22, 23, 25], among others. In order to address this location problem, first we have to solve the question of computing the shortest path between points in different regions since our goal is to optimize a globalizing function of the length of those paths. We note in passing that some partial answers in the plane and particular choices of distances can be found in [15].

This problem is closely related with the physical phenomenon of refraction. Refraction describes the process that occurs when the light changes the medium, and then the phase velocity of a wave is changed. This effect is also observed when sound waves pass from one medium into another, when water waves move into water of a different depth or, as in our case, when a traveler moves between opposite sides of the separating hyperplane. Snell’s law states that for a given pair of media and a planar wave with a single frequency, there is a ratio relationship between the sines of the angle of incidence $\theta _A$ and the angle of refraction $\theta _B$ and the indices of refraction $n_A$ and $n_B$ of the media: $n_A \sin \theta _A = n_B \sin \theta _B$ (see Fig. 1). This law is based on Fermat’s principle that states that the path followed by a light ray between two points is the one that takes the least time. As a by-product of the results in this paper, we shall find an extension of this law that also applies to transportation problems when more than one transportation mode is present in the model.

Our goal in this paper is to design an approach to solve the above mentioned family of location problems, for any combination of norms and in any dimension. Moreover, we show an explicit formulation of these problems as second order cone programming (SOCP) problems (see [2] for further details) which enables the usage of standard commercial solvers to solve them.

Fig. 1

Illustration of Snell’s law on the plane

The paper is organized in seven sections. In Sect. 2 we analyze the problem of computing shortest paths between pairs of points separated by a hyperplane ${\mathcal {H}}$ when the distance measure is different in each one of the half-spaces defined by ${\mathcal {H}}$. We characterize the crossing (gate) points where a shortest path intersects the hyperplane, generalizing the well-known refraction principle (Snell’s Law) for any dimension and any combination of $\ell _p$-norms. Section 3 analyzes location problems with distance measures induced by the above shortest paths. We provide a compact mixed-integer second order cone formulation for this problem and a transformation of that formulation into two continuous SOCP problems. In Sect. 4 the problem is extended to the case where the hyperplane is endowed with a third norm and thus, it can be used to reduce the length of the shortest paths between regions. Section 5 is devoted to the computational experiments. We report results for different instances. We begin comparing our approach for the first model, with those presented (on the plane and for $\ell _1$- and $\ell _2$-norms) in [18] and [27] by using the data sets given there; then we test our methodology using the 50-points data set in [12] (on the plane and different combinations of $\ell _p$-norms, both for the first and the second model); and finally we run a randomly generated set of larger instances (5000, 10,000 and 50,000 demand points) for different dimension (2, 3 and 5) and different combinations of $\ell _p$-norms. Section 6 is devoted to some extensions of the previous model. The paper ends, in Sect. 7, with some conclusions and an outlook for further research.

2 Shortest paths between points separated by a hyperplane

Let us assume that ${\mathbb {R}}^d$ is endowed with two $\ell _{p_i}$-norms each one in the corresponding half-space ${\mathrm{H}}_{i}$, $i\in \{A,B\}$ induced by the hyperplane $\mathcal {H}=\{x \in \mathbb {R}^d: \alpha ^t x = \beta \}$. Let us write $\alpha ^t=(\alpha _1,\ldots ,\alpha _d)$ and assume further that $p_i=r_i/s_i$ with $r_i, s_i \in \mathbb {N}\!{\setminus }\!\{0\}$ and $\gcd (r_i,s_i)=1$, $i\in \{A,B\}$. Here, $\Vert z\Vert _{p}$ stands for the $\ell _p$ norm of $z \in \mathbb {R}^d$.

We are given two points $a, b\in {\mathbb {R}}^d$ such that $\alpha ^t a<\beta$ and $\alpha ^t b >\beta$, with weights $\omega _a$, $\omega _b$ respectively and a generic (but fixed) point $x^*=(x^*_{1},\ldots ,x^*_d)^t$ such that $\alpha ^t x^*=\beta$.

The following result characterizes the point $x^*$ that provides the shortest weighted path between a with weight $\omega _a>0$ and b with weight $\omega _b >0$ using their corresponding norms in each side of $\mathcal {H}$.

Lemma 1

If $1<p_A,p_B<+\infty$, the length $d_{p_Ap_B}(a,b)$ of the shortest weighted path between a and b is

$$\begin{aligned} d_{p_Ap_B}(a,b)= \omega _a \Vert x^*-a\Vert _{p_A} +\omega _b \Vert x^*-b\Vert _{p_B}, \end{aligned}$$

where $x^*=(x^*_1,\ldots ,x^*_d)^t$, $\alpha ^tx^*=\beta$ must satisfy the following conditions:

• 1. For all j such that $\alpha _j= 0$:

  $$\begin{aligned} \omega _a\left[ \frac{|x^*_j-a_j|}{\Vert x^*-a\Vert _{p_A}}\right] ^{p_A-1} \mathrm {sign}(x^*_j-a_j)+ \omega _b\left[ \frac{|x^*_j-b_j|}{\Vert x^*-b\Vert _{p_B}}\right] ^{p_B-1} \mathrm {sign}(x^*_j-b_j) =0. \end{aligned}$$

• 2. For all i, j such that $\alpha _i \alpha _j\ne 0$.

  $$\begin{aligned}&\omega _a\left[ \frac{|x^*_i-a_i|}{\Vert x^*-a\Vert _{p_A}}\right] ^{p_A-1} \frac{\mathrm {sign}(x^*_i-a_i)}{\alpha _i}+ \omega _b\left[ \frac{|x^*_i-b_i|}{\Vert x^*-b\Vert _{p_B}}\right] ^{p_B-1} \frac{\mathrm {sign}(x^*_i-b_i)}{\alpha _i} \\&\quad =\omega _a\left[ \frac{|x^*_j-a_j|}{\Vert x^*-a\Vert _{p_A}}\right] ^{p_A-1} \frac{\mathrm {sign}(x^*_j-a_j)}{\alpha _j}+ \omega _b\left[ \frac{|x^*_j-b_j|}{\Vert x^*-b\Vert _{p_B}}\right] ^{p_B-1} \frac{\mathrm {sign}(x^*_j-b_j)}{\alpha _j}. \end{aligned}$$

Proof

Computing $d_{p_Ap_B}(a,b)$ reduces to solving the following problem:

$$\begin{aligned} \displaystyle \min _{x: \alpha ^tx=\beta } \omega _a\Vert x-a\Vert _{p_A}+\omega _b\Vert x-b\Vert _{p_B}. \end{aligned}$$

The above problem is a convex minimization problem with a linear constraint. Consider the Lagrangian function $L(x,\lambda )=\omega _a\Vert x-a\Vert _{p_A}+\omega _b\Vert x-b\Vert _{p_B}+\lambda (\alpha ^t x-\beta )$. Then necessary and sufficient optimality conditions read as:

$$\begin{aligned}&\omega _a\left[ \frac{|x_j-a_j|}{\Vert x-a\Vert _{p_A}}\right] ^{p_A-1} \mathrm {sign}(x_j-a_j) + \omega _b\left[ \frac{|x_j-b_j|}{\Vert x-b\Vert _{p_B}}\right] ^{p_B-1}\\&\quad \times \, \mathrm {sign}(x_j-a_j) +\lambda \alpha _j =0, \; j=1,\ldots ,d\\&\qquad \alpha ^t x-\beta =0. \end{aligned}$$

First of all, if $\alpha _j=0$ we obtain condition 1 from the first set of equations. Next, if $\lambda \alpha _j\ne 0$ the above system gives rise to condition 2. $\square$

In the case where one of the two norms involved is not strict, i.e. $p_A$ or $p_B\in \{1,+\infty \}$ there are non-differentiable points besides the origin and the optimality condition is obtained using subdifferential calculus. Let us denote by $\partial f(x)$ the subdifferential set of f at x.

Lemma 2

If $p_A=+\infty$ or $p_B=1$, the length $d_{p_Ap_B}(a,b)$ of the shortest weighted path between a and b is

$$\begin{aligned} d_{p_Ap_B}(a,b)= \omega _a \Vert x^*-a\Vert _{p_A} +\omega _b \Vert x^*-b\Vert _{p_B}, \end{aligned}$$

where $x^*=(x^*_1,\ldots ,x^*_d)^t$, $\alpha ^tx^*=\beta$ must satisfy:

$$\begin{aligned} \lambda \alpha \in \omega _a \partial \Vert x^*-a\Vert _{p_A}+\omega _b \partial \Vert x^*-b\Vert _{p_B}, \; \hbox { for some } \lambda \in {\mathbb {R}}. \end{aligned}$$

Proof

The result follows from applying the rules of subdifferential calculus (see [24]) to the shortest path problem between a and b with the distance measure $d_{p_Ap_B}$. $\square$

We note in passing that the optimality condition in Lemma 2 gives rise, whenever $p_A$ or $p_B$ are specified, to usable expressions. In particular, if both $p_A$ and $p_B\in \{1,+\infty \}$ the resulting problem is linear and the condition is very easy to handle. Lemmas 1 and 2 extend the results in [15] to the case of general norms and any finite dimension greater than 2.

Next consider the following embedding $\pi : \mathbb {R}^d \rightarrow \mathbb {R}^{d+1}$, $\pi (x) = (x,\alpha ^tx-\beta )$, for $x \in \mathbb {R}^d$. Take any point $x^*$ such that $\alpha ^tx^*=\beta$. Clearly, $\pi (a) = (a,\alpha ^t a-\beta )$, $\pi (x^*) = (x^*,0)$ and $\pi (\mathcal {H}) = \mathcal {H} \times \{0\}$. Then, let us denote by $\gamma _a$ the angle between the vectors $\pi (a-x^*)=(a-x^*,0)$ and $(a-x^*,\alpha ^ta-\beta )$. Now, we can interpret $\frac{|\alpha ^ta-\beta |}{\Vert a-x^*\Vert _{p_A}}$ as a generalized sine of the angle $\gamma _a$ (see Fig. 2). The reader may note that in general this ratio is not a trigonometric function, unless $p_i=2$, $i\in \{A,B\}$. This way we define by abusing of notation

$$\begin{aligned} \sin _{p_A}\gamma _a=\frac{|\alpha ^ta-\beta |}{\Vert a-x^*\Vert _{p_A}} \quad \left( \hbox {analogously } \sin _{p_B}\gamma _b=\frac{|\alpha ^tb-\beta |}{\Vert b-x^*\Vert _{p_B}}\right) . \end{aligned}$$

The above expression can be written by components, namely:

$$\begin{aligned} \sin _{p_A}\gamma _a=\left| \sum _{j=1}^d \frac{\alpha _j a_j-\alpha _j x^*_j}{\Vert a-x^*\Vert _{p_A}}\right| , \quad (\hbox {observe that } \alpha ^t x^*=\beta ). \end{aligned}$$

(1)

Finally, by similarity we shall denote the non-negative value of each component in the previous sum as

$$\begin{aligned} \sin _{p_A}\gamma _{a_j}:=\frac{|\alpha _j a_j-\alpha _jx^*_j|}{\Vert a-x^*\Vert _{p_A}}, \; j=1,\ldots ,d. \end{aligned}$$

With the above convention we can state a result that extends the well-known Snell’s Law to this framework. It relates the gate point $x^*$ in the hyperplane $\alpha ^t x=\beta$ between two points a and b in terms of the generalized sine (1) of the angles $\gamma _a$ and $\gamma _b$.

Fig. 2

Illustrative example of the generalized sines

Corollary 3

(Snell’s-like result) The point $x^*=(x^*_1,\ldots ,x^*_d)^t$, $\alpha ^tx^*=\beta$ that defines the shortest weighted path between a and b is determined by the following necessary and sufficient conditions:

• 1. For all j such that $\alpha _j=0$:

  $$\begin{aligned} \omega _a\left[ \frac{|x^*_j-a_j|}{\Vert x^*-a\Vert _{p_A}}\right] ^{p_A-1} \mathrm {sign}(x^*_j-a_j)+ \omega _b\left[ \frac{|x^*_j-b_j|}{\Vert x^*-b\Vert _{p_B}}\right] ^{p_B-1} \mathrm {sign}(x^*_j-b_j) =0. \end{aligned}$$

• 2. For all $i,j,\; \alpha _i\alpha _j\ne 0$.

  $$\begin{aligned}&\omega _a\left[ \frac{\sin _{p_A} \gamma _{a_i}}{|\alpha _i|}\right] ^{p_A-1} \frac{\mathrm {sign}(x^*_i-a_i)}{\alpha _i}+ \omega _b\left[ \frac{\sin _{p_B} \gamma _{b_i}}{|\alpha _i|}\right] ^{p_B-1} \frac{\mathrm {sign}(x^*_i-b_i)}{\alpha _i}\\&\quad =\omega _a\left[ \frac{\sin _{p_A} \gamma _{a_j}}{|\alpha _j|}\right] ^{p_A-1} \frac{\mathrm {sign}(x^*_j-a_j)}{\alpha _j}+ \omega _b\left[ \frac{\sin _{p_B} \gamma _{b_j}}{|\alpha _j|}\right] ^{p_B-1} \frac{\mathrm {sign}(x^*_j-b_j)}{\alpha _j}, \end{aligned}$$

Corollary 4

(Snell’s Law) If $d=2$, $p_A=p_B=2$ and $\mathcal {H}=\{(x_1, x_2) \in \mathbb {R}^2: \alpha _1x_1 + \alpha _2 x_2 = \beta \}$ with $\alpha _1, \alpha _2, \beta \in \mathbb {R}$, the point $x^*$ satisfies that

$$\begin{aligned} \omega _a \sin \theta _a = \omega _b \sin \theta _b, \end{aligned}$$

where $\theta _a$ and $\theta _b$ are: 1) if $\alpha _1\le \alpha _2$, the angles between the vectors $a-x^*$ and $(-\alpha _2,\alpha _1)^t$, and $b-x^*$ and $(\alpha _2, -\alpha _1)^t$, or 2) if $\alpha _1 > \alpha _2$, the angles between the vectors $a-x^*$ and $(\alpha _2,-\alpha _1)^t$, and $b-x^*$ and $(-\alpha _2, \alpha _1)^t$.

Proof

Since for $d=2$ the $\ell _2$-norm is isotropic, we can assume w.l.o.g. that the separating line is $x_2=0$. Thus, after a change of variable $x^*$ can be taken as the origin of coordinates and $a=(a_1,a_2)$ such that $a_1\ge 0$, $a_2<0$, $b=(b_1,b_2)$ such that $b_1\le 0$, $b_2>0$.

Next, the optimality condition using Lemma 1 is $\omega _a \frac{|a_1|}{\Vert a\Vert _2}-\omega _b \frac{|b_1|}{\Vert b\Vert _2}=0$. The result follows since $\sin \theta _a=\frac{|a_1|}{\Vert a\Vert _2}$ and $\sin \theta _b=\frac{|b_1|}{\Vert b\Vert _2}$. $\square$

3 Location problems with demand points in two media separated by a hyperplane

In this section we analyze the problem of locating a new facility to serve a set of given demand points which are classified into two classes, based on a separating hyperplane. The peculiarity of the model is that different norms to measure distances may be considered within each one of the half-spaces induced by the hyperplane.

Let A and B be two finite sets of given demand points in $\mathbb {R}^d$, and $\omega _a$ and $\omega _b$ be the weights of the demand points $a \in A$ and $b \in B$, respectively. Consider $\mathcal {H}=\{x \in \mathbb {R}^d: \alpha ^t x = \beta \}$ to be the separating hyperplane in $\mathbb {R}^d$ with $\alpha \in \mathbb {R}^d$ and $\beta \in \mathbb {R}$, and

$$\begin{aligned} {\mathrm{H}}_A = \{x \in \mathbb {R}^d: \alpha ^t x \le \beta \} \quad \text {and} \quad {\mathrm{H}}_B = \{x \in \mathbb {R}^d: \quad \alpha ^t x > \beta \}. \end{aligned}$$

We assume that $\mathbb {R}^d$ is endowed with a mixed norm such that the distance measure in ${\mathrm{H}}_A$ is induced by a norm $\Vert \cdot \Vert _{p_A}$, the distance measure in ${\mathrm{H}}_B$ is induced by the norm $\Vert \cdot \Vert _{p_B}$ and $p_A\ge p_B$. We assume further that $p_i=r_i/s_i$, with $r_i, s_i \in \mathbb {N}\!{\setminus }\!\{0\}$ and $\gcd (r_i,s_i)=1$, $i\in \{A,B\}$ and that the distance between two points inside ${\mathrm{H}}_A$ (resp. ${\mathrm{H}}_B$) is measured with the norm in ${\mathrm{H}}_A$ (resp. ${\mathrm{H}}_B$).

Observe that the hypothesis that $p_A\ge p_B$ ensures that moving through ${\mathrm{H}}_A$ is at least as fast as moving within ${\mathrm{H}}_B$.

The goal is to find the location of a single new facility in $\mathbb {R}^d$ so that the sum of the distances from the demand points to the new facility is minimized. The problem can be stated as:

where for two points $x, y \in \mathbb {R}^d$, $d_{p_A,p_B}(x,y)$ is the length of the shortest path between x and y, as determined by Lemmas 1 and 2.

Note that the shortest paths can be explicitly described by distinguishing whether the new location is in ${\mathrm{H}}_A$ or ${\mathrm{H}}_B$. Let $x \in \mathbb {R}^d$ and $z \in A \cup B$, then:

$$\begin{aligned} d_{p_A,p_B}(x, z) = \left\{ \begin{array}{l@{\quad }l} \Vert x-z\Vert _{p_i} &{} x, z \in {{\mathrm{H}}}_i, i \in \{A, B\}\\ \displaystyle \min _{y\in \mathcal {H}} \Vert y-z\Vert _{p_i} + \Vert x-y\Vert _{p_j} &{} \hbox {if } x\in {\mathrm{H}}_j, z \in {\mathrm{H}}_{i}, i,j\; \in \{A, B\},\; i \ne j . \end{array}\right. \end{aligned}$$

Theorem 5

Assume that $\min \{|A|,|B|\}>2$. If the points in A or B are not collinear and $p_A<+\infty$, $p_B>1$ then Problem (P) always has a unique optimal solution.

Proof

Let us define the function $f(x,y):{\mathbb {R}}^{d\times (|A| +|B|) d} \rightarrow {\mathbb {R}}$ as:

$$\begin{aligned} f(x,y)=\left\{ \begin{array}{l@{\quad }l} \displaystyle f_{\le } (x,y):=\sum _{a\in A} \omega _a\Vert x-a\Vert _{p_A} +\sum _{b\in B} \omega _b \Vert x-y_b\Vert _{p_A} + \sum _{b\in B} \omega _b \Vert y_b-b\Vert _{p_B} &{} \hbox { if } \alpha ^t x \le \beta \\ \displaystyle f_{>} (x,y):=\sum _{a\in A} \omega _a\Vert y_a-a\Vert _{p_A} +\sum _{a\in A} \omega _a \Vert x-y_a\Vert _{p_B} + \sum _{b\in B} \omega _b \Vert x-b\Vert _{p_B} &{} \hbox { if } \alpha ^t x > \beta . \end{array} \right. \end{aligned}$$

It is clear that

$$\begin{aligned} f^*= \min \{ \mathop {\overbrace{\inf _{\alpha ^t x\le \beta , \alpha ^t y_b=\beta , \forall b\in B} f_{\le }(x,y)}}\limits ^{({\mathrm{SP}}_{\le })}, \mathop {\overbrace{\inf _{\alpha ^t x> \beta , \alpha ^t y_a=\beta , \forall a\in A} f_{>}(x,y)}}\limits ^{({\mathrm{SP}}_>)}\}. \end{aligned}$$

We observe that both functions, namely $f_{\le }$ and $f_{>}$ are continuous and coercive. This implies that $\inf \nolimits _{\alpha ^t x\le \beta , \alpha ^t y_b=\beta , \forall b\in B} f_{\le }(x,y)$ is attained since the domain is closed and bounded from below. Thus a solution for this subproblem always exists. Moreover, we prove that $f_{\le }$ is strictly convex which in turn implies that the solution of the first subproblem $({\mathrm{SP}}_\le )$ is unique.

Indeed, let $(x,y),\; (x',y')$ be two points in the domain of $f_{\le }$ and $0<\lambda <1$.

$$\begin{aligned}&f_{\le }(\lambda x +(1-\lambda ) x',\lambda y +(1-\lambda )y')\nonumber \\&\quad = \sum _{a\in A} \omega _a\Vert \lambda x +(1-\lambda ) x'-a\Vert _{p_A} \\&\qquad + \sum _{b\in B} \omega _b \Vert \lambda x +(1-\lambda ) x'-\lambda y_b -(1-\lambda )y'_b\Vert _{p_A} \\&\qquad + \sum _{b\in B} \omega _b \Vert \lambda y_b +(1-\lambda )y'_b-b \Vert _{p_B}\\&(A \hbox { not collinear and } p_A>1)\\&\quad < \sum _{a\in A} \omega _a(\lambda \Vert x - a\Vert _{p_A} +(1-\lambda )\Vert x' - a\Vert _{p_A}) \\&\qquad + \sum _{b\in B} \omega _b (\lambda \Vert x - y_b \Vert _{p_A} + (1-\lambda )\Vert x' -y'_b \Vert _{p_A})\\&\qquad + \sum _{b\in B} \omega _b (\lambda \Vert y_b- b \Vert _{p_B} +(1-\lambda ) \Vert y'_b- b \Vert _{p_B})\\&\quad = \lambda f_{\le }(x,y) +(1-\lambda ) f_{\le }(x',y'). \end{aligned}$$

The analysis of the second subproblem is different since the domain is not closed. First, analogously to the above proof it follows that $f_{>}$ is strictly convex in its domain, namely $\alpha ^t x> \beta ,\; \alpha ^t y_a=\beta ,\; \forall a\in A$. Therefore, if the infimum is attained (in the interior of ${\mathrm{H}}_B$) the solution must be unique. Next, we will prove that if the $\inf$ of the second subproblem is not attained then it cannot be an optimal solution of Problem (P) since there exists another point in $\alpha ^t x\le \beta ,\; \alpha ^t y_b=\beta ,\; \forall b\in B$ with a smaller objective value.

Let us assume that no optimal solution of $({\mathrm{SP}}_>)$ exists. This implies that the infimum is attained at the boundary of ${\mathrm{H}}_B$ and therefore there exists $(\bar{x}, \bar{y})$, $\alpha ^t \bar{x}=\beta$ such that

$$\begin{aligned} \inf _{\alpha ^t x> \beta , \alpha ^t y_a=\beta , \forall a} f_{>}(x,y)= f_{>}(\bar{x},\bar{y}). \end{aligned}$$

Next,

Now, since $\bar{x} \in \mathcal {H}$, let $B_1:=\{b\in B: \omega _b \Vert \bar{x}-b\Vert _{p_B}\ge \omega _b \Vert b-\bar{y}_b\Vert _{p_B}+\omega _b \Vert \bar{x} -\bar{y}_b\Vert _{p_A}\}$ and $B_2=B\!{\setminus }\!B_1$. (Observe that $\bar{y}_b=\bar{x}$ for all $b\in B_2$ and then $\sum _{b\in B_2} \omega _b \Vert \bar{x}-\bar{y}_b\Vert _{p_A} = 0$.) This allows us to bound from below ($*$) as follows:

$$\begin{aligned} (*)\ge & {} \sum _{a\in A} \omega _a\Vert \bar{x}-a\Vert _{p_A}+ \sum _{b\in B_1} \omega _b \Vert \bar{x}-\bar{y}_b\Vert _{p_A} +\sum _{b\in B_1} \omega _b \Vert b -\bar{y}_b\Vert _{p_B}\\&+\sum _{b\in B_2} \omega _b \Vert \bar{x} -b\Vert _{p_B} \\= & {} \sum _{a\in A} \omega _a\Vert \bar{x}-a\Vert _{p_A}+ \sum _{b\in B} \omega _b \Vert \bar{x}-\bar{y}_b\Vert _{p_A}\\&+\sum _{b\in B_1} \omega _b \Vert b -\bar{y}_b\Vert _{p_B}+\sum _{b\in B_2} \omega _b\Vert \bar{y}_b-b\Vert _{p_B} \\= & {} \sum _{a\in A} \omega _a\Vert \bar{x}-a\Vert _{p_A}+ \sum _{b\in B} \omega _b \Vert \bar{x}-\bar{y}_b\Vert _{p_A} + \sum _{b\in B} \omega _b \Vert b-\bar{y}_b\Vert _{p_B}\\= & {} f_{\le }(\bar{x},\bar{y}). \end{aligned}$$

Hence, $(\bar{x}, \bar{y})$ provides a smaller or equal objective value evaluated in $({\mathrm{SP}}_\le )$ which concludes the proof.$\square$

The above description of the distances allows us to formulate Problem (P) as a mixed integer nonlinear programming problem by introducing an auxiliary variable $\gamma \in \{0,1\}$ that identifies whether the new facility belongs to ${\mathrm{H}}_A$, which in fact is equal to ${\overline{\mathrm{H}}}_A$, or ${\overline{\mathrm{H}}}_B$.

Theorem 6

Problem (P) is equivalent to the following problem:

$$\begin{aligned} \min&\displaystyle \sum _{a\in A} \omega _a Z_a + \displaystyle \sum _{b\in B} \omega _b Z_b \end{aligned}$$

(2)

$$\begin{aligned} \hbox {s.t. }&\; z_a - Z_a \le M_a(1-\gamma ),&\forall a\in A,\end{aligned}$$

(3)

$$\begin{aligned}&\theta _a + u_a - Z_a \le M_a\,\gamma , \quad \quad \quad&\forall a\in A,\end{aligned}$$

(4)

$$\begin{aligned}&z_b- Z_b \le M_b\;\gamma , \quad \quad \quad&\forall b\in B,\end{aligned}$$

(5)

$$\begin{aligned}&\theta _b + u_b - Z_b \le M_b\,(1-\gamma ), \quad \quad \quad&\forall b\in B,\end{aligned}$$

(6)

$$\begin{aligned}&z_a \ge \Vert x-a\Vert _{p_A}, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(7)

$$\begin{aligned}&\theta _a \ge \Vert x-y_a\Vert _{p_B}, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(8)

$$\begin{aligned}&u_a \ge \Vert a - y_a\Vert _{p_A}, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(9)

$$\begin{aligned}&z_b \ge \Vert x-b\Vert _{p_B},\quad \quad \quad&\forall b\in B,\end{aligned}$$

(10)

$$\begin{aligned}&\theta _b \ge \Vert x-y_b\Vert _{p_A},\quad \quad \quad&\forall b\in B,\end{aligned}$$

(11)

$$\begin{aligned}&u_b \ge \Vert b- y_b\Vert _{p_B},\quad \quad \quad&\forall b\in B,\end{aligned}$$

(12)

$$\begin{aligned}&\alpha ^t x - \beta \le M (1-\gamma ),\end{aligned}$$

(13)

$$\begin{aligned}&\alpha ^t x - \beta \ge -M \gamma ,\end{aligned}$$

(14)

$$\begin{aligned}&\alpha ^t y_a = \beta , \quad \quad \quad&\forall a\in A, \end{aligned}$$

(15)

$$\begin{aligned}&\alpha ^t y_b = \beta , \quad \quad \quad&\forall b\in B, \end{aligned}$$

(16)

$$\begin{aligned}&Z_a, z_a, \theta _a, u_a \ge 0, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(17)

$$\begin{aligned}&Z_b, z_b, \theta _b, u_b \ge 0, \quad \quad \quad&\forall b\in B,\end{aligned}$$

(18)

$$\begin{aligned}&y_a, y_b \in \mathbb {R}^d,&\forall a \in A, b\in B,\end{aligned}$$

(19)

$$\begin{aligned}&\gamma \in \{0,1\}. \end{aligned}$$

(20)

with $M, M_a, M_b >0$ sufficiently large constants for all $a \in A, b\in B$.

Proof

Let us introduce the auxiliary variable $\gamma = \left\{ \begin{array}{c@{\quad }l} 1 &{} \hbox {if } x\in {\mathrm{H}}_A,\\ 0 &{} \hbox {if } x \in \overline{{\mathrm{H}}}_B, \end{array}\right.$ that models whether the location of the new facility x is in ${\mathrm{H}}_A$ or in the closure of ${\mathrm{H}}_B$. (Observe that if $x\in {\mathrm{H}}_A\cap \overline{\mathrm{H}}_B = \mathcal {H}$, $\gamma$ can assume both values.) Note that constraints (13),(14) and (20) assure the correct definition of this variable. Next, we define the auxiliary variables $Z_a$ $\forall a\in A$ and $Z_b$ $\forall b\in B$ that represent the shortest path length from the new location at x to $a\in A$ and $b\in B$, respectively. Similarly, with $z_a$ and $z_b$ we shall model $\Vert x-a\Vert _{p_A}$ and $\Vert x-b\Vert _{p_B}$, respectively.

We shall prove the case $x\in {\mathrm{H}}_A$, since the case $x \in \overline{{\mathrm{H}}}_B$ follows analogously when $\gamma =0$. In case $x \in {\mathrm{H}}_A$ (being then $\gamma =1$), let us denote with $\theta _b$ the distance between x and the gate point, $y_b$, of b on $\mathcal {H}$, namely $\theta _b=\Vert x-y_b\Vert _{p_A}$; and with $u_b$ the distance between $y_b$ and b, $u_b=\Vert b-y_b\Vert _{p_B}$ for all $b\in B$ (16). Since $\gamma =1$, the minimization of the objective function and constraints (3)–(6) and (7), (11) and (12) assure that the variables are well-defined and that:

$$\begin{aligned} Z_a = z_a = \Vert x-a\Vert _{p_A} \quad \text {and} \quad Z_b = \theta _b + u_b = \Vert x-y_b\Vert _{p_A} + \Vert b-y_b\Vert _{p_B}. \end{aligned}$$

Hence, the minimum value of $\sum \nolimits _{a \in A} \omega _a Z_a + \sum \nolimits _{b \in B} \omega _b Z_b$ is the overall sum of the shortest paths distances between x and the points in $A \cup B$. $\square$

The reader may note that valid choices of the $M,\; M_a,\; M_b$ constants that appear in the formulation (2)–(20) can be easily obtained. Indeed, by standard arguments one can prove that it suffices to take the big-M constants, in the above formulation, as $M_{c}= 4\max \nolimits _{a\in A,\; b\in B} \{ \Vert a\Vert _{p_A},\Vert b\Vert _{p_B} \}$ $\forall \; {c}\in A\cup B$ and $M= 2\max \nolimits _{p\in \{p_A,p_B\}} \Vert \alpha \Vert _p \max \nolimits _{a\in A,\; b\in B} \{ \Vert a\Vert _{p_A},\Vert b\Vert _{p_B} \} +\beta$. (We note in passing that the proposed values are valid upper bounds although some smaller values may also work.) In spite of that, the above formulation may not be the more appropriate way to solve Problem (P) since one can take advantage of the following fact.

Observe that the hyperplane $\mathcal {H}$ induces the decomposition of $\mathbb {R}^d$ into $\mathbb {R}^d = {\mathrm{H}}_A \cup {\mathrm{H}}_B$, and such that ${\mathrm{H}}_A \cap \overline{\mathrm{H}}_B = \mathcal {H}$. Moreover, using the result in Theorem 5, Problem (P) is equivalent to solve two problems, restricting the solution x to be in ${\mathrm{H}}_A$ and in $\overline{{\mathrm{H}}}_B$.

Theorem 7

Let $x^*\in \mathbb {R}^d$ be the optimal solution of (P). Then, $x^*$ is the solution of one of the following two problems, $(\mathrm{P}_A)$ or $(\mathrm{P}_B)$:

$$\begin{aligned} \hbox {s.t. } \;&(7), (11),(12), (16), \nonumber \\&\alpha ^tx \le \beta , \\&z_a \ge 0,\; \forall a \in A,\nonumber \\&\theta _b, u_b \ge 0,\; \forall b \in B,\nonumber \\&x, y_b \in \mathbb {R}^d.\nonumber \end{aligned}$$

(21)

$$\begin{aligned} \hbox {s.t. } \; \;&(8), (9), (10), (15), \nonumber \\&\alpha ^t x \ge \beta ,\\&z_b \ge 0,\; \forall b \in B,\nonumber \\&\theta _a, u_a \ge 0,\; \forall a \in A,\nonumber \\&x, y_a \in \mathbb {R}^d.\nonumber \end{aligned}$$

(22)

Proof

Let $x^*$ be the optimal solution of (P). By Theorem 6, $x^*$ must be the optimal solution of (2)–(20). Hence, we can distinguish two cases: (a) $x^* \in {\mathrm{H}}_A$; or (b) $x^* \in \overline{\mathrm{H}}_B$. First, let us analyze case (a). Since $x^* \in {\mathrm{H}}_A$, then $\gamma ^*=1$. Hence, the non-redundant constraints in (P) are (16), (21), (7), (11) and (12), and the variables $Z_a$ and $Z_b$ in (P) reduce to $z_a$ and $\theta _b+u_b$, respectively. The above simplification results in the formulation of Problem ($\mathrm{P}_A$).

For case (b), the proof follows in the same manner. The reader may note that the hyperplane $\mathcal {H}$ is considered in both problems. However, by the proof of Theorem 5, if $x^*$ is in $\mathcal {H}$, since we assume that $p_A \ge p_B$, the optimal value of ($\mathrm{P}_A$) is not greater than the optimal value of ($\mathrm{P}_B$) and the solution can be considered to belong to ${\mathrm{H}}_A$.

$\square$

From theorems 5 and 7 we get the following result that gives an interesting localization property about the solutions of the problem [($\mathrm{P}_A$) or ($\mathrm{P}_B$)] whichever one has the best objective value.

Theorem 8

Let $(x^*, y^*)\in {\mathbb {R}}^{d\times |B|d}$ be the optimal solution of ($\mathrm{P}_A$) and $(\hat{x}, \hat{y})\in {\mathbb {R}}^{d\times |A|d}$ be the optimal solution of ($\mathrm{P}_B$), with objective values $f^*$ and $\hat{f}$, respectively. If $f^* > \hat{f}$ (resp. $f^* < \hat{f}$), $y^*_b= y^*_{b'}=x^*$, for all $b,b' \in B$ (resp. $\hat{y}_a= \hat{y}_{a'}=\hat{x}$, for all $a,a' \in A$). Moreover, if $f^*=\hat{f}$, $y^*_b= y^*_{a}=x^*=\hat{x}$, $\forall a \in A$, $b\in B$.

As we mentioned before, the cases where the norms used to measure distances are $\ell _{p}$-norms, $p\in \mathbb {Q},\; 1<p<+\infty$, are very important and their corresponding models simplify further. In what follows, we give explicit formulations for these problems.

Theorem 9

Let $\Vert \cdot \Vert _{p_i}$ be an $\ell _{p_i}$-norm with $p_i=\frac{r_i}{s_i}> 1$, $r_i,s_i\in \mathbb {N}\!{\setminus }\!\{0\}$, and $\gcd (r_i,s_i)=1$ for $i\in \{A, B\}$. Then, ($\mathrm{P}_A$) is equivalent to

$$\begin{aligned} \min \; \displaystyle \sum _{a\in A} \omega _a z_a + \displaystyle \sum _{b\in B} \omega _b \theta _b + \displaystyle \sum _{b\in B} \omega _b u_b \end{aligned}$$

(23)

$$\begin{aligned} \hbox {s.t. }&\; (21), (16),&\nonumber \\ t_{ak}-x_k+a_{k}\ge 0,&\forall a \in A,\; k=1, \ldots ,d, \end{aligned}$$

(24)

$$\begin{aligned} t_{ak}+x_k-a_{k}\ge 0,&\forall a \in A,\; k=1, \ldots ,d, \end{aligned}$$

(25)

$$\begin{aligned} v_{bk}+x_k-y_{bk}\ge 0,&\forall b \in B,\; k=1, \ldots ,d, \end{aligned}$$

(26)

$$\begin{aligned} v_{bk}-x_k+y_{bk}\ge 0,&\forall b \in B,\; k=1, \ldots ,d, \end{aligned}$$

(27)

$$\begin{aligned} g_{bk}-y_{bk}+b_{k}\ge 0,&\forall b \in B,\; k=1, \ldots ,d, \end{aligned}$$

(28)

$$\begin{aligned} g_{bk}+y_{bk}-b_{k}\ge 0,&\forall b \in B,\; k=1, \ldots ,d, \end{aligned}$$

(29)

$$\begin{aligned} t_{ak}^{r_A} \le \xi _{ak}^{s_A} z_{a}^{r_A-s_A},&\forall a\in A,\; k=1, \ldots ,d, \end{aligned}$$

(30)

$$\begin{aligned} v_{bk}^{r_A} \le \rho _{bk}^{s_A} \theta _{b}^{r_A-s_A},&\forall b \in B,\; k=1, \ldots ,d, \end{aligned}$$

(31)

$$\begin{aligned} g_{bk}^{r_B} \le \psi _{bk}^{s_B} u_{b}^{r_B-s_B},&\forall b \in B,\; k=1, \ldots ,d,&\end{aligned}$$

(32)

$$\begin{aligned} \sum _{k=1}^d \xi _{ak} \le z_a,&\forall a \in A,&\end{aligned}$$

(33)

$$\begin{aligned} \sum _{k=1}^d \rho _{bk} \le \theta _b,&\forall b \in B,&\end{aligned}$$

(34)

$$\begin{aligned} \sum _{k=1}^d \psi _{bk} \le u_b,&\forall b \in B,&\end{aligned}$$

(35)

$$\begin{aligned} z_{a}, \xi _{ak}, t_{ak}, \ge 0,&\forall a\in A,\; k=1,\ldots ,d,&\end{aligned}$$

(36)

$$\begin{aligned} \theta _{b}, u_b, \rho _{bk}, v_{bk} \ge 0,&\forall b\in B\; k=1,\ldots ,d,&\end{aligned}$$

(37)

$$\begin{aligned} \psi _{bk}, g_{bk} \ge 0,&\forall b\in B\; k=1,\ldots ,d,&\end{aligned}$$

(38)

$$\begin{aligned} x, y_b \in \mathbb {R}^d,&\forall b\in B.&\end{aligned}$$

(39)

Proof

Note that the difference between ($\mathrm{P}_A$) and the formulation (23)–(39) stems in the constraints that represent the norms [(7), (11) and (12)] in ($\mathrm{P}_A$) that are now rewritten as (24)–(35). This equivalence follows from the observation that any constraint in the form $Z \ge \Vert X-Y\Vert _{p}$, for any $p = \frac{r}{s}$ with $r, s\in \mathbb {N}{\setminus } \{0\}$, $r>s$ and $\gcd (r,s)=1$, and X, Y variables in $\mathbb {R}^d$, can be equivalently written as the following set of constraints:

$$\begin{aligned} \left. \begin{array}{ll} Q_{k} + X_k - Y_{k}\ge 0,&{}\; k=1, \ldots , d, \\ Q_{k} - X_k + Y_{k}\ge 0,&{} \; k=1, \ldots , d,\\ Q_{k}^{r} \le R_{k}^{s} Z^{r-s},&{} k=1, \ldots , d,\\ \displaystyle \sum _{k=1}^d R_{k} \le Z,&{} \\ R_k \ge 0, &{} \forall k=1, \ldots , d. \end{array}\right\} \end{aligned}$$

(40)

This result can be obtained from [4], although it is detailed here for the sake of readability. Indeed, let $\rho =\frac{r}{r-s}$, then $\frac{1}{\rho }+\frac{s}{r}=1$. Let (Z, X, Y) fulfill the inequality $Z\ge \Vert X-Y\Vert _{p}$. Then we have

$$\begin{aligned} \Vert X-Y\Vert _{p}\le Z\Longleftrightarrow & {} \left( \sum _{k=1}^{d}|X_k-Y_k|^{\frac{r}{s}}\right) ^{\frac{s}{r}}\le Z^{\frac{s}{r}} Z^{\frac{1}{\rho }}\nonumber \\\Longleftrightarrow & {} \left( \sum _{k=1}^{d}| X_k-Y_k|^{\frac{r}{s}} Z^{\frac{r}{s}(-\frac{r-s}{r})}\right) ^{\frac{s}{r}}\le Z^{\frac{s}{r}},\nonumber \\\Longleftrightarrow & {} \sum _{k=1}^{d}| X_k-Y_k|^{\frac{r}{s}} Z^{-\frac{r-s}{s}}\le Z. \end{aligned}$$

(41)

Then (41) holds if and only if $\exists R \in \mathbb {R}^d$, $R_{k}\ge 0,\; \forall k=1, \ldots , d$ such that $|X_k-Y_k|^{\frac{r}{s}} Z^{-\frac{r-s}{s}}\le R_k$, satisfying $\sum _{k=1}^{d} R_{k}\le Z$, or equivalently, $|X_k-Y_k|^{r}\le R_{k}^{s} Z^{r-s} \hbox { and } \sum _{k=1}^{d} R_k \le Z.$

Set $Q_k =|X_k - Y_k|$ and $R_k=|X_k-Y_k|^{p} Z^{-1/\rho }$. Then, clearly (Z, X, Y, Q, R) satisfies (40).

Conversely, let (Z, X, Y, Q, R) be a feasible solution of (40). Then, $Q_k \ge |X_k-Y_k|$ and $R_k \ge Q_j^{(\frac{r}{s})} Z^{-\frac{r-s}{s}}\ge |X_k-Y_k|^{\frac{r}{s}} Z^{-\frac{r-s}{s}}$. Thus, $\sum _{k=1}^d |X_k-Y_k|^{\frac{r}{s}} Z^{-\frac{r-s}{s}} \le \sum _{k=1}^d R_k \le Z,$ which in turn implies that $\sum \nolimits _{k=1}^d |X_k-Y_k|^{\frac{r}{s}} \le Z \, Z^{\frac{r-s}{s}}$ and hence, $\Vert X-Y\Vert _p \le Z$. $\square$

Remark 1

(Polyhedral Norms) Note that when the norms in ${\mathrm{H}}_A$ or ${\mathrm{H}}_B$ are polyhedral norms, as the well-known $\ell _1$ or $\ell _\infty$ norms, a much simpler (linear) representation than the one given in Theorem 9 is possible. Actually, it is well-known (see for instance [21, 22, 26]) that if $\Vert \cdot \Vert$ is a polyhedral norm, such that $B^*$, the unit ball of its dual norm, has ${\mathrm{Ext}}(B^*)$ as set of extreme points, the constraint $Z \ge \Vert X-Y\Vert$ is equivalent to the following set of linear inequalities:

$$\begin{aligned} Z \ge e^t (X-Y), \; \forall e \in {\mathrm{Ext}}(B^*). \end{aligned}$$

Corollary 10

Problem ($\mathrm{P}_A$) (resp. ($\mathrm{P}_B$)) can be represented as a semidefinite programming problem with $|A|(2d+1) + |B|(4d+3) + 1$ (resp. $|B|(2d+1) + |A|(4d+3) + 1$) linear constraints and at most $4d (|A| \log r_A + |B| \log r_A + |B| \log r_B)$ (resp. $4d (|B| \log r_B + |A| \log r_B + |A| \log r_A)$ positive semidefinite constraints.

Proof

By Theorem 9, Problem ($\mathrm{P}_A$) is equivalent to Problem (23)–(39). Then, using [4, Lemma 3], we represent each one of the nonlinear inequalities, as a system of at most $2\log r_A$ or $2\log r_B$ inequalities of the form $X^2\le YZ$, involving 3 variables, X, Y, Z with Y, Z non negative. Hence, by Schur complement, it follows that

$$\begin{aligned} X^2\le YZ \quad \Leftrightarrow \left( \begin{array}{ccc} Y+Z &{}\quad 0 &{} \quad 2X \\ 0 &{}\quad Y+Z &{}\quad Y-Z \\ 2X &{}\quad Y-Z &{}\quad Y+Z \end{array} \right) \succeq 0, \; Y+Z\ge 0. \end{aligned}$$

(42)

Hence, Problem ($\mathrm{P}_A$) is a semidefinite programming problem because it has a linear objective function, $|A|(2d+1) + |B|(4d+3) + 1$ linear inequalities and at most $4d (|A| \log r_A + |B| \log r_A + |B| \log r_B)$ linear matrix inequalities. $\square$

The reader may note that by similar arguments and since the left-hand representation of (42) is a second order cone constraint, Problem ($\mathrm{P}_A$) can also be seen as a second order cone program.

The following example illustrates this model with the 18-points data set from Parlar [18].

Example 11

Let $\mathcal {H}=\{x \in \mathbb {R}^d: 1.5x - y = 0\}$ and consider the set of 18-demand points in [18]. We consider that the distance measure in ${\mathrm{H}}_A$ is the $\ell _2$-norm while in ${\mathrm{H}}_B$ is the $\ell _3$-norm. The solution of Problem (P) is $x^* = (9.23792, 6.435661)$ with objective value $f^*=103.934734$.

Figure 3 shows the demand points A and B, the hyperplane $\mathcal {H}$, the solution $x^*$, as well as the shortest paths between $x^*$ and the points in A and B.

Fig. 3

Demand points and optimal solution of Example 11

Finally, to conclude this section we address a restricted case of Problem (P). Let $\{g_{1}, \ldots , g_l\} \subset {\mathbb {R}}[X]$ be real polynomials and $\mathbf {K}:=\{x\in {\mathbb {R}}^{d}: g_{j}(x)\ge 0,\, j=1,\ldots ,l \}$ a basic closed, compact semialgebraic set with nonempty interior satisfying that for some $M>0$ the quadratic polynomial $u(x)=M-\sum _{k=1}^d x_k^2$ has a representation on $\mathbf {K}$ as $u\,=\,\sigma _{0}+\sum _{j=1}^{\ell }\sigma _{j}\,g_{j}$, for some $\{\sigma _0, \ldots , \sigma _l\}\subset {\mathbb {R}}[X]$ being each $\sigma _j$ sum of squares (Archimedean property [16]). We remark that the assumption on the Archimedean property is not restrictive at all, since any semialgebraic set $\mathbf {K}\subseteq \mathbb {R}^d$ for which it is known that $\sum _{k=1}^d x_k^2 \le M$ holds for some $M>0$ and for all $x\in \mathbf {K}$, admits a new representation $\mathbf {K'} = \mathbf {K} \cup \{x\in {\mathbb {R}}^{d}: g_{l+1}(x):=M-\sum _{k=1}^d x_k^2\ge 0\}$ that trivially verifies the Archimedean property.

For the sake of simplicity, we assume that the domain $\mathbf {K}$ is compact and has nonempty interior, as it is usual in Location Analysis. We observe that we can extend the results in Sect. 3 to a broader class of convex constrained problems.

Remark 2

Let $\mathbf {K}:=\{x\in {\mathbb {R}}^{d}: g_{j}(x)\ge 0,\, j=1,\ldots ,l \}$ be a basic closed, compact semialgebraic set with nonempty interior, and consider the restricted problem:

$$\begin{aligned} \displaystyle \min _{x\in \mathbf {K}}\sum _{a\in A} \omega _a \; d(x,a)+\sum _{b\in B} \omega _b \;d(x,b). \end{aligned}$$

(43)

Assume that $\mathbf {K}$ satisfies the Archimedean property and further that any of the following conditions hold:

• 1. $g_i(x)$ are concave for $i=1,\ldots , l$ and $-\sum _{i=1}^{ l} \nu _i \nabla ^2 g_i(x) \succ 0$ for each dual pair $(x,\nu )$ of the problem of minimizing any linear functional $c^tx$ on $\mathbf {K}$ (Positive Definite Lagrange Hessian (PDLH)).

• 2. $g_i(x)$ are sos-concave on $\mathbf {K}$ for $i=1,\ldots , l$ or $g_i(x)$ are concave on $\mathbf {K}$ and strictly concave on the boundary of $\mathbf {K}$ where they vanish, i.e. $\partial \mathbf {K}\cap \partial \{x\in {\mathbb {R}}^d: g_i(x)=0\}$, for all $i=1,\dots , l$.

• 3. $g_i(x)$ are strictly quasi-concave on $\mathbf {K}$ for $i=1,\ldots , l$.

Then, there exists a constructive finite dimensional embedding, which only depends on $p_A$, $p_B$ and $g_i$, $i=1,\ldots , l$, such that the solution of (43) can be obtained by solving two semidefinite programming problems.

The validity of the above statement follows from the fact that the unconstrained version of Problem (43) can be equivalently written as two SDP problems using the result in Theorem 7 and Corollary 10. Therefore, it remains to prove that under the conditions 1, 2 or 3 the constraint set $x\in \mathbf {K}$ is also exactly represented as a finite number of semidefinite constraints or equivalently that it is semidefinite representable (SDr). The discussion that the three above mentioned cases are SDr is similar to that in [4, Theorem 8] and thus it is omitted here. $\square$

4 Location problems in two media divided by a hyperplane endowed with a different norm

In this section we consider an extension of the location problem in the previous section where the separating hyperplane is endowed with a third norm, namely $\Vert \cdot \Vert _{p_\mathcal {H}}$, and it may be used to travel in shortest paths crossing it. Thus, the new problem consists of locating a new facility to minimize the weighted sum of the distances to the demand points, but where, if it is convenient, a shortest path from the facility to a demand point that crosses the hyperplane may travel through it. This way the hyperplane can be seen as a rapid transit boundary for displacements between different media.

We define the shortest path distance between two points a and b in $\mathbb {R}^d$ by

and x, y represent the access and the exit (gate) points where the shortest path from a to b crosses through the hyperplane.

As in Sect. 2 we can also give a general result about the optimal gate points of the shortest weighted path between points in this framework. In this case we must resort to subdifferential calculus to avoid nondifferentiability situations due to the possible coincidence of $x^*$ and $y^*$. Let us denote by $\partial _x f(x^*,y^*)$ (resp. $\partial _y f(x^*,y^*)$) the subdifferential set of the function f as a function of its first (resp. second) set of variables, i.e. y is fixed (resp. x is fixed), at $y^*$ (resp. $x^*$).

Lemma 12

The distance $d_{t}(a,b)$ of the shortest weighted path between a and b is

$$\begin{aligned} \omega _a \Vert x^*-a\Vert _{p_A} +\omega _\mathcal {H} \Vert x^*-y^*\Vert _{p_\mathcal {H}} + \omega _b \Vert y^*-b\Vert _{p_B}, \end{aligned}$$

where $x^*=(x^*_1,\ldots ,x^*_d)^t$, and $y^*= (y^*_1, \ldots , y^*_d)^t$, $\alpha ^tx^*=\beta$, $\alpha ^ty^*=\beta$ must satisfy:

$$\begin{aligned} \lambda _a \alpha \in \omega _a \partial \Vert x^*-a\Vert _{p_A}+\omega _\mathcal {H} \partial _x d_\mathcal {H}(x^*,y^*), \; \hbox { for some } \lambda _a \in {\mathbb {R}},\\ \lambda _b \alpha \in \omega _b \partial \Vert y^*-b\Vert _{p_B}+\omega _\mathcal {H} \partial _y d_\mathcal {H}(x^*,y^*), \; \hbox { for some } \lambda _b \in {\mathbb {R}}, \end{aligned}$$

being $d_\mathcal {H}(x,y)=\Vert x-y\Vert _{p_\mathcal {H}}$.

Now, we consider again the embedding defined in Sect. 2: $x\in {\mathbb {R}}^d\rightarrow (x,\alpha ^tx-\beta ) \in {\mathbb {R}}^{d+1}$. Denote by $\gamma _a$ the angle between the vectors $(a-x^*,0)$ and $(a-x^*,\alpha ^ta-\beta )$ and by $\gamma _b$ the angle between $(b-y^*, 0)$ and $(a-y^*, \alpha ^t b -\beta )$. Then, we can interpret $\frac{|\alpha ^ta-\beta |}{\Vert a-x^*\Vert _{p_A}}$ and $\frac{|\alpha ^tb-\beta |}{\Vert b-y^*\Vert _{p_B}}$ as generalized sines of the angles $\gamma _a$ and $\gamma _b$, respectively (see Fig. 4). The reader may again note that in general these ratios are not trigonometric functions, unless $p_A=p_B=2$. We define the generalized sines as:

$$\begin{aligned} \sin _{p_A}\gamma _a=\frac{|\alpha ^ta-\beta |}{\Vert x^*-a\Vert _{p_A}} \quad \hbox {and} \quad \sin _{p_B}\gamma _b=\frac{|\alpha ^tb-\beta |}{\Vert y^*-b\Vert _{p_B}}. \end{aligned}$$

These expressions can be written by components as:

$$\begin{aligned} \sin _{p_A}\gamma _a=\left| \sum _{j=1}^d \frac{\alpha _j a_j-\alpha _j x^*_j}{\Vert a-x^*\Vert _{p_A}}\right| , \quad \sin _{p_B}\gamma _b=\left| \sum _{j=1}^d \frac{\alpha _j b_j-\alpha _j y^*_j}{\Vert b-y^*\Vert _{p_B}}\right| . \end{aligned}$$

Finally, by similarity we shall denote the non-negative value of each component in the previous sums as

$$\begin{aligned} \sin _{p_A}\gamma _{a_j}:=\frac{|\alpha _j a_j-\alpha _jx^*_j|}{\Vert a-x^*\Vert _{p_A}} \quad \hbox {and} \quad \sin _{p_B}\gamma _{b_j}:=\frac{|\alpha _j b_j-\alpha _jy^*_j|}{\Vert b-y^*\Vert _{p_B}}, \; j=1,\ldots ,d. \end{aligned}$$

Fig. 4

Illustrative example of the generalized sines when traversing $\mathcal {H}$

With the above notation, we state the following results derived from Lemma 12.

Corollary 13

(Snell’s-like result) Assume that $\Vert \cdot \Vert _{p_A},\; \Vert \cdot \Vert _{p_B},\; \Vert \cdot \Vert _{p_\mathcal {H}}$ are $\ell _p$-norms with $1<p<+\infty$. Let $x^*, y^*\in \mathbb {R}^d$, $\alpha ^tx^*=\alpha ^t y^*= \beta$. Then, $x^*$ and $y^*$ define the shortest weighted path between a and b when traversing the hyperplane is allowed if and only if the following conditions are satisfied:

• 1. For all j such that $\alpha _j=0$:

  $$\begin{aligned}&\omega _a\left[ \frac{|x^*_j-a_j|}{\Vert x^*-a\Vert _{p_A}}\right] ^{p_A-1} \mathrm {sign}(x^*_j-a_j)+ \omega _\mathcal {H} \left[ \frac{|x^*_j-y^*_j|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}\right] ^{p_\mathcal {H}-1} \mathrm {sign}(x^*_j-y^*_j) =0,\\&\quad \omega _b\left[ \frac{|y^*_j-b_j|}{\Vert y^*-b\Vert _{p_B}}\right] ^{p_B-1} \mathrm {sign}(y^*_j-b_j)- \omega _\mathcal {H}\left[ \frac{|x^*_j-y^*_j|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}\right] ^{p_\mathcal {H}-1} \mathrm {sign}(x^*_j-y^*_j) =0. \end{aligned}$$

• 2. For all i, j, such that $\alpha _i\alpha _j\ne 0$:

  $$\begin{aligned}&\omega _a\left[ \frac{\sin \gamma _{a_i}}{|\alpha _i|}\right] ^{p_A-1} \frac{\mathrm {sign}(x^*_i-a_i)}{\alpha _i}+ \omega _\mathcal {H}\left[ \frac{|x^*_i-y^*_i|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}\right] ^{p_\mathcal {H}-1} \frac{\mathrm {sign}(x^*_i-y^*_i)}{\alpha _i}\\&\quad =\omega _a\left[ \frac{\sin \gamma _{a_j}}{|\alpha _j|}\right] ^{p_A-1} \frac{\mathrm {sign}(x^*_j-a_j)}{ \alpha _j }+ \omega _\mathcal {H}\left[ \frac{|x^*_j-y^*_j|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}\right] ^{p_\mathcal {H}-1} \frac{\mathrm {sign}(x^*_j-y^*_j)}{\alpha _j}, \end{aligned}$$

  and

  $$\begin{aligned}&\omega _a\left[ \frac{\sin \gamma _{b_i}}{|\alpha _i|}\right] ^{p_B-1} \frac{\mathrm {sign}(y^*_i-b_i)}{\alpha _i}- \omega _\mathcal {H}\left[ \frac{|x^*_i-y^*_i|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}\right] ^{p_\mathcal {H}-1} \frac{\mathrm {sign}(x^*_i-y^*_i)}{\alpha _i}\\&\quad =\omega _a\left[ \frac{\sin \gamma _{b_j}}{|\alpha _j|}\right] ^{p_B-1} \frac{\mathrm {sign}(y^*_j-b_j)}{ \alpha _j}- \omega _\mathcal {H}\left[ \frac{|x^*_j-y^*_j|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}\right] ^{p_\mathcal {H}-1} \frac{\mathrm {sign}(x^*_j-y^*_j)}{\alpha _j}. \end{aligned}$$

Corollary 14

If $d=2$, $p_A=p_B=p_\mathcal {H}=2$ and $\mathcal {H}=\{(x_1, x_2) \in \mathbb {R}^2: x_2=0\}$, the points $x^*$, $y^*$ satisfy one of the following conditions:

• 1. $\omega _a \sin \theta _a = \omega _b \sin \theta _b = \omega _\mathcal {H} \frac{|y^*_1|}{\Vert x^*-y^*\Vert _{p_\mathcal {H}}}$ and $x^* \ne y^*$, or

• 2. $\omega _a \sin \theta _a = \omega _b \sin \theta _b$ and $x^*=y^*$,

where $\theta _a$ is the angle between the vectors $a-x^*$ and $(0,-1)$ and $\theta _b$ the angle between $b-y^*$ and (0, 1) (see Fig. 5).

Proof

To prove 1), since the Euclidean norm is isotropic, we can assume w.l.o.g. that after a change of variable $x^*$ and $y^*$ can be taken such that $x^*_1=0$, $y^*_1\ge 0$ and $a=(a_1,a_2)$ such that $a_1\ge 0$, $a_2<0$, $b=(b_1,b_2)$ such that $b_1\le 0$, $b_2>0$.

The optimality condition using Lemma 12, assuming $x^*\ne y^*$, is:

$$\begin{aligned} \omega _a \frac{|a_1|}{\Vert x^*-a\Vert _2}-\omega _\mathcal {H} \frac{|y^*_1|}{\Vert x^*-y\Vert _{2}}= & {} 0, \nonumber \\ -\omega _b \frac{|y^*_1 -b_1|}{\Vert y^*-b\Vert _2}+\omega _\mathcal {H}\frac{|y^*_1|}{\Vert x^*-y^*\Vert _{2}}= & {} 0. \end{aligned}$$

(44)

The result follows since $\sin \theta _a=\frac{|a_1|}{\Vert x^*-a\Vert _2}$, $\sin \theta _b=\frac{|y^*_1-b_1|}{\Vert y^*-b\Vert _2}$.

If $x^*=y^*$ the result for condition 2) follows from Corollary 4. $\square$

Note that in Corollary 14 one can make w.l.o.g. the assumption that the separating line is $x_2=0$ due to the isotropy of the Euclidean norm.

Corollary 15

If $d=2$, $p_A=p_B=p_\mathcal {H}=2$ and $\mathcal {H}=\{(x_1, x_2) \in \mathbb {R}^2: x_2=0\}$ then the following assertions hold:

• 1. If $\omega _a=\omega _b=\omega _\mathcal {H}\ne 0$, then $\theta _a = \theta _b$.

• 2. If $\omega _\mathcal {H}=0$ and $\omega _a \omega _b \ne 0$, then $\theta _a=\theta _b=0$.

Proof

The proof follows observing that if $y_1^*>0$ from Eq. (44) in Corollary 14 we get that $|y^*_1-b_1|=\Vert y^*-b\Vert _2$ which is impossible unless $b_2=0$, contradicting the hypotheses in the proof. Therefore, $y^*_1$ cannot be greater than zero. Hence, in this case the condition reduces to $x^*=y^*$ and $\omega _a \frac{|a_1|}{\Vert x^*-a\Vert _2}=\omega _b \frac{|b_1|}{\Vert y^*-b\Vert _2}$. Thus, $\sin \theta _a = \sin \theta _b$.

Next, the case when $\omega _\mathcal {H}=0$ and $\omega _a \omega _b \ne 0$, reduces to compute the projections onto $\mathcal {H}$, of each one of the points a and b. Indeed by condition 1) in Corollary 14, $\sin \theta _a = \sin \theta _b =0$, being $\theta _a=\theta _b=0$ (see Fig. 6). $\square$

Fig. 5

Snell’s law when traversing $\mathcal {H}$

Fig. 6

Snell’s law when traversing $\mathcal {H}$ and $\omega _\mathcal {H}=0$

Lemma 16

Let $a \in {\mathrm{H}}_A$ and $b \in {\mathrm{H}}_B$. Then,

• 1. If $\max \{p_A,p_B\}\ge p_\mathcal {H}$ the shortest path distance $d_t(a,b)=\displaystyle \min \nolimits _{x:\alpha ^t x=\beta } \Vert x-a\Vert _{p_A}+\Vert x-b\Vert _{p_B}$, i.e. it crosses $\mathcal {H}$ at a unique point.

• 2. If $p_\mathcal {H}\ge \max \{p_A,p_B\}$ then the shortest path from a to b may contain a non-degenerated segment on $\mathcal {H}$.

Proof

Let us consider the general form of the solution to determine $d_{t}(a,b)$, namely

$$\begin{aligned} d_{t}(a,b)= \displaystyle \min _{x, y \in \mathcal {H}} \Vert x-a\Vert _{p_A}+\Vert x-y\Vert _{p_\mathcal {H}}+\Vert y-b\Vert _{p_B}. \end{aligned}$$

Clearly, if $p_A\ge p_\mathcal {H}$, we have

$$\begin{aligned} \Vert x-a\Vert _{p_A}+\Vert x-y\Vert _{p_\mathcal {H}}+\Vert y-b\Vert _{p_B}\ge & {} \Vert x-a\Vert _{p_A}+\Vert x-y\Vert _{p_A}+\Vert y-b\Vert _{p_B};\\ \hbox {(by the triangular inequality)}\ge & {} \Vert y-a\Vert _{p_A}+\Vert y-b\Vert _{p_B}. \end{aligned}$$

$\square$

Definition 17

We say that the norms $\ell _{p_A}$, $\ell _{p_B}$ and $\ell _{p_\mathcal {H}}$ satisfy the Rapid Enough Transit Media Condition (RETM) for $a \in A$ and $b\in B$ if:

• 1. For $y^*\in \arg \displaystyle \min _{y \in \mathcal {H}} \Vert y-a\Vert _{p_A}$, $\Vert a-y^*\Vert _{p_A} + \Vert x-y^*\Vert _{p_\mathcal {H}} \le \Vert x-a\Vert _{p_A}$, for all $x \in \mathcal {H}$, and

• 2. For $x^*\in \arg \displaystyle \min _{x \in \mathcal {H}} \Vert x-b\Vert _{p_B}$, $\Vert b-x^*\Vert _{p_B} + \Vert x^*- y\Vert _{p_\mathcal {H}} \le \Vert y-b\Vert _{p_B}$, for all $y \in \mathcal {H}$.

Note that the above definition states that a triplet of norms $(\ell _{p_A}, \ell _{p_B}, \ell _{p_\mathcal {H}})$ satisfies the condition if the norm defined over the hyperplane $\mathcal {H}$ is ‘fast enough’ to reverse the triangle inequality when mixing the norms, i.e., when the shortest path from a point outside the hyperplane to another point in the hyperplane benefits from traveling throughout the hyperplane.

Lemma 18

Let $a \in {\mathrm{H}}_A$ and $b \in {\mathrm{H}}_B$. Then, if $\infty > p_\mathcal {H} \ge p_A \ge p_B\ge 1$ and the corresponding norms satisfy the RETM condition for a and b, the shortest path from a to b crosses throughout $\mathcal {H}$ in the following two points:

$$\begin{aligned} x^*= a - \dfrac{\alpha ^t a -\beta }{\Vert \alpha \Vert _{p_A}^*} \, \delta ^A_\alpha \quad \text {and} \quad y^*= b - \dfrac{\alpha ^t b -\beta }{\Vert \alpha \Vert _{p_B}^*} \, \delta ^B_\alpha \end{aligned}$$

where $\Vert \cdot \Vert _{p_A}^*$ and $\Vert \cdot \Vert _{p_B}^*$ are the dual norms to $\Vert \cdot \Vert _{p_A}$ and $\Vert \cdot \Vert _{p_B}$, respectively, and $\delta ^A_\alpha \in \arg \max _{\Vert \delta \Vert _{p_A}=1} \alpha ^t \delta$, $\delta ^B_\alpha \in \arg \max _{\Vert \delta \Vert _{p_B}=1} \alpha ^t \delta$.

Proof

First, note that $x^*$ and $y^*$ correspond with the projections of a and b onto $\mathcal {H}$, respectively (see [17]). Let $x, y \in \mathcal {H}$ be alternative gate points in a path from a to b. Then

$$\begin{aligned}&\Vert b-y\Vert _{p_B} + \Vert x-y\Vert _{p_\mathcal {H}} + \Vert a-x\Vert _{p_A} \mathop {\ge }\limits ^{RETM} \Vert b-y^*\Vert _{p_B} \\&\quad + \Vert y^*-y\Vert _{p_\mathcal {H}} + \Vert x-y\Vert _{p_\mathcal {H}} + \Vert a-x^*\Vert _{p_A} \\&\quad + \Vert x^*-x\Vert _{p_\mathcal {H}}\\&\quad \ge \Vert b-y^*\Vert _{p_B} + \Vert a-x^*\Vert _{p_A} + \Vert y^*-x\Vert _{p_\mathcal {H}} + \Vert x^*-x\Vert _{p_\mathcal {H}}\\&\quad \ge \Vert b- y^*\Vert _{p_B} + \Vert a-x^*\Vert _{p_A} + \Vert y^*-x^*\Vert _{p_\mathcal {H}}. \end{aligned}$$

$\square$

Example 19

Let $\mathcal {H}=\{(x,y) \in \mathbb {R}^2: y=x\}$ and $a=(4, 5)^t \in {\mathrm{H}}_A$, $b=(12,11)^t \in {\mathrm{H}}_B$ with $p_A=p_B=1$ and $p_\mathcal {H}=+\infty$. We observe that these norms satisfy the RETM condition for a and b. First of all, we realize that the closest $\ell _1$-points to a and b, $x^*$ and $y^*$, respectively, on $\mathcal {H}$ must belong to $x^*\in [(4,4), (5,5)]$ and $y^*\in [(11,11), (12,12)]$, respectively.

• 1. Let $(y,y) \in \mathcal {H}$. $\Vert a-x^*\Vert _1 + \Vert x^*-(y,y)\Vert _\infty = 1 + \min \{|4-y|, |5-y|\}$ and $\Vert a-(y,y)\Vert _1 = |4-y| +|5-y|$. Then, for $y\ge 5$, we get that $1 + (y-5) = y-4 \le (y-4) + (y-5) =2y - 9$, which is always true for $y \ge 5$. Otherwise, if $y \le 4$, $1 + (4-y) = 5-y \le (4-y) + (5-y) = 9-2y$, which is always true for $y \le 4$.

• 2. Let $(x,x) \in \mathcal {H}$. $\Vert b-y^*\Vert _1 + \Vert y^*-(x,x)\Vert _\infty = 1 + \min \{|11-x|, |12-x|\}$ and $\Vert a-(x,x)\Vert _1 = |12-x| +|11-x|$. Then, for $x\ge 12$, we get that $1 + (x-12) = x-11 \le (x-12) + (x-11) =2x - 23$, which is always true for $x \ge 12$. Otherwise, if $x \le 11$, $1 + (11-x) = 12-x\le (12-x) + (11-x) = 23-2x$, which is always true for $x \le 11$.

Hence, the RETM condition is satisfied, and the shortest path from a to b crosses in $\mathcal {H}$ through their projections:

$$\begin{aligned} x^*= (5,5) \quad \text {and} \quad y^*= (11,11). \end{aligned}$$

The overall length of this path is $\Vert a-x^*\Vert _1+\Vert x^*-y^*\Vert _\infty + \Vert b-y^*\Vert _1 = 1 + 6 + 1 = 8$ (see Fig. 7).

Note that the RETM condition is defined for any triplet of norms ($\ell _{p_A}, \ell _{p_B}, \ell _{p_\mathcal {H}}$) and for any pairs of points a and b. Hence, unless the condition is fulfilled for all pairs of points $a \in A$ and $b\in B$, we cannot extend Lemma 18 to the location of all the points in A and B. Actually, even for the slowest $\ell _p$-norm in ${\mathrm{H}}_A$ and ${\mathrm{H}}_B$, namely $\ell _1$, and the fastest one in $\mathcal {H}$, namely $\ell _\infty$, it is easy to check that such a condition is not verified for every pair of points.

Once we have analyzed shortest paths between points in the framework of the location problem to be solved, we come back to the original goal of this section: the location of a new facility to minimize the weighted sum of shortest path distances from the demand points. Thus, the problem that we wish to analyze in this section can be stated similarly as in (P).

Note that Problem (P), analyzed in Sect. 3, is a particular case of Problem (PT) when the two crossing points $y^1$ and $y^2$ are enforced to be equal, i.e. whenever it is not allowed to move traversing the hyperplane when computing shortest paths between the different media.

Fig. 7

Shortest distance from a to b in Example 19

By similar arguments to those used in Theorem 5 we can also state an existence and uniqueness result for Problem (PT).

Theorem 20

Assume that $\min \{|A|,|B|\}>2$. If the points in A or B are not collinear $1<p_\mathcal {H}<+\infty$ and $1<p_B \le p_A<+\infty$ then Problem (PT) always has a unique optimal solution.

It is also possible to give sufficient conditions so that Problem (PT) reduces to (P). The following proposition clearly follows from Lemma 16.

Proposition 21

Let $A, B \subseteq \mathbb {R}^d$ and $\mathcal {H}=\{x\in \mathbb {R}^d: \alpha ^tx = \beta \}$. Then, if $p_A \ge p_B \ge p_\mathcal {H}$, Problem (PT) reduces to Problem (P).

The description of the shortest path distances in (DT), allows us to formulate Problem (PT) as a mixed integer nonlinear programming problem in a similar manner as we did in Theorem 6 for (P).

Theorem 22

Problem (PT) is equivalent to the following problem:

$$\begin{aligned} \min&\displaystyle \sum _{a\in A} \omega _a Z_a + \displaystyle \sum _{b\in B} \omega _b Z_b \end{aligned}$$

(45a)

$$\begin{aligned} \hbox {s.t. }&(3), (5), (7), (10), (13),(14), \nonumber \\&\theta _a + u_a + t_a - Z_a \le \hat{M}_a\,\gamma , \quad \quad \quad&\forall a\in A,\end{aligned}$$

(45b)

$$\begin{aligned}&\theta _b + u_b +t_b- Z_b \le \hat{M}_b\,(1-\gamma ),\quad \quad \quad&\forall b\in B,\end{aligned}$$

(45c)

$$\begin{aligned}&\theta _a \ge \Vert x-y^1_a\Vert _{p_B}, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(45d)

$$\begin{aligned}&u_a \ge \Vert a - y^2_a\Vert _{p_A}, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(45e)

$$\begin{aligned}&t_a \ge \Vert y^1_a - y^2_a\Vert _{p_\mathcal {H}}, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(45f)

$$\begin{aligned}&\theta _b \ge \Vert x-y^1_b\Vert _{p_A},\quad \quad \quad&\forall b\in B,\end{aligned}$$

(45g)

$$\begin{aligned}&u_b \ge \Vert b- y_b^2\Vert _{p_B},\quad \quad \quad&\forall b\in B,\end{aligned}$$

(45h)

$$\begin{aligned}&t_b \ge \Vert y^1_b - y^2_b\Vert _{p_\mathcal {H}}, \quad \quad \quad&\forall b\in B,\end{aligned}$$

(45i)

$$\begin{aligned}&\alpha ^t y^i_a = \beta , \quad \quad \quad&\forall a\in A, i=1, 2, \end{aligned}$$

(45j)

$$\begin{aligned}&\alpha ^t y^i_b = \beta , \quad \quad \quad&\forall b\in B, i=1, 2, \end{aligned}$$

(45k)

$$\begin{aligned}&Z_a, z_a, \theta _a, u_a, t_a, \ge 0, \quad \quad \quad&\forall a\in A,\end{aligned}$$

(45l)

$$\begin{aligned}&Z_b, z_b, \theta _b, u_b, t_b, \ge 0 \quad \quad \quad&\forall b\in B,\end{aligned}$$

(45m)

$$\begin{aligned}&y^1_a, y^2_a, y^1_b, y^2_b \in \mathbb {R}^d,&\forall a\in A, \; b\in B\end{aligned}$$

(45n)

$$\begin{aligned}&\gamma \in \{0,1\}. \end{aligned}$$

(45o)

with $\hat{M}_a, \hat{M}_b > 0$ sufficiently large constants for all $a\in A, b\in B$.

The reader may note that appropriate values of the constants $\hat{M}_a,\, \hat{M}_b$ can be easily derived which results in values similar to those described at the end of Theorem 6. Moreover, one can have a much better solution approach based on a simple geometrical observation.

The following result states that the solution of Problem (45) can also be reached by solving two simpler problems when restricting the solution to belong to ${\mathrm{H}}_A$ or ${\mathrm{H}}_B$.

Theorem 23

Let $x^*\in \mathbb {R}^d$ be the optimal solution of (PT). Then, $x^*$ is the solution of one of the following two problems:

A similar proof to the one of Corollary 10 would allow us to give an equivalent SOCP formulation for problems ($\mathrm{PT}_A$) and ($\mathrm{PT}_B$).

Fig. 8

Points and optimal solution of Example 24

Fig. 9

Shortest path from $x^*$ to (2, 8)

We illustrate Problem (PT) with an instance of the 18 points data set in [18].

Example 24

Consider the 18 points in [18] and the separating line $\mathcal {H}=\{x \in \mathbb {R}^d: 1.5x - y = 0\}$. Assume that in ${\mathrm{H}}_A$ the distance is measured with the $\ell _2$-norm, in ${\mathrm{H}}_B$ the distance is induced by the $\ell _3$-norm and on $\mathcal {H}$ the norm is $\frac{1}{4} \ell _\infty$. Figure 8 shows the demand points A and B, the hyperplane $\mathcal {H}$ and the solution $x^*$. The optimal solution is $x^* = (9.133220, 6.897760)$ with objective value $f^*= 100.442353$.

Note that the difference between this model and the one above is that the shortest path distance from the new facility to a demand point may not cross the hyperplane $\mathcal {H}$ at a unique point. Comparing the results with those obtained in Example 11 for the same data set, but not allowing the use of $\mathcal {H}$ as a high speed media, we get savings in the overall transportation cost of 3.492381 units. In Fig. 9, we can observe that the shortest path from the new facility $x^*$ and the demand point (2, 8) consists of traveling from $x^*$ to $y^1=(5.918243, 8.877364)$ in ${\mathrm{H}}_B$ (using the $\ell _3$-norm), then traveling within the hyperplane $\mathcal {H}$ from $y^1$ to $y^2=(4.635013, 6.952519)$ (using the $1/4-\ell _{\infty }$-norm) and finally to (2, 8) in ${\mathrm{H}}_A$ (using $\ell _2$-norm). Actually, the overall length of the path is:

$$\begin{aligned} d_3(x^*, y^1) + \dfrac{1}{4} d_\infty (y^1, y^2) + d_2(y^2, (2,8))= & {} 3.447879 + 0.4812115 + 2.835578\\= & {} 6.7646685. \end{aligned}$$

Finally, we state, for the sake of completeness, the following remark whose proof is similar to the one for Remark 2 and that extends the second order cone formulations in Theorem 23 to the constrained case.

Remark 3

Let $\{g_{1}, \ldots , g_l\} \subset {\mathbb {R}}[X]$ be real polynomials and $\mathbf {K}:=\{x\in {\mathbb {R}}^{d}: g_{j}(x)\ge 0,\, j=1,\ldots ,l \}$ a basic closed, compact semialgebraic set with nonempty interior satisfying the Archimedean property, and consider the following problem

$$\begin{aligned} \displaystyle \min _{x\in \mathbf {K}} \; \sum _{a\in A} \omega _a d_t(x,a)+\sum _{b\in B} \omega _b d_t(x,b). \end{aligned}$$

(46)

with $d_t(x, y)$ as defined in (DT). Assume that any of the following conditions hold:

• 1. $g_i(x)$ are concave for $i=1,\ldots ,\ell$ and $-\sum _{i=1}^{l} \nu _i \nabla ^2 g_i(x) \succ 0$ for each dual pair $(x,\nu )$ of the problem of minimizing any linear functional $c^tx$ on $\mathbf {K}$ (Positive Definite Lagrange Hessian (PDLH)).

• 2. $g_i(x)$ are sos-concave on $\mathbf {K}$ for $i=1,\ldots ,\ell$ or $g_i(x)$ are concave on $\mathbf {K}$ and strictly concave on the boundary of $\mathbf {K}$ where they vanish, i.e. $\partial \mathbf {K}\cap \partial \{x\in {\mathbb {R}}^d: g_i(x)=0\}$, for all $i=1,\ldots , l$.

• 3. $g_i(x)$ are strictly quasi-concave on $\mathbf {K}$ for $i=1,\ldots , l$.

Then, there exists a constructive finite dimension embedding, which only depends on $p_A, p_B, p_\mathcal {H}$ and $g_i$, $i=1,\ldots ,\ell$, such that (46) is equivalent to two semidefinite programming problems. $\square$

5 Computational experiments

We have performed a series of computational experiments to show the efficiency of the proposed formulations to solve problems (P) and (PT). Our SOCP formulations have been coded in Gurobi 5.6 and executed in a PC with an Intel Core i7 processor at 2x 2.40 GHz and 4 GB of RAM. We fixed the barrier convergence tolerance for QCP in Gurobi to $10^{-10}$.

Our computational experiments have been organized in three blocks because the goal is different in each one of them. First, we report on the data sets already considered in Parlar [18] and Zaferanieh et al. [27]. These data are sets of 4, 18 (in [18]), 30 and 50 (in [27]) demand points in the plane and separating hyperplanes $y=0.5x,\; y=x,\; y=1.5x$. Second, we consider the well-known 50-points data set in Eilon et. al [12] with different separating hyperplanes and norms in each one of the corresponding half-spaces. Finally, we also report on some randomly generated instances with 5,000, 10,000 and 50,000 demand points in dimension 2, 3 and 5 and different combinations of norms.

The results of the first block are included in Tables 1 and 2. Table 1 shows in columns CPUTime ([18, 27]), $f^*$ ([18, 27]) and $x^*$([18, 27]) the results reported in [18] (for the 4 and 18 points data sets) and [27] (for the 30 and 50 points data sets), and in columns CPUTime(P), $f^*$(P) and $x^*$ (P) the results obtained with our approach. (The reader may observe that the CPU times are not directly comparable since results in [27] were obtained in a machine with a single processor at 2.80 GHz). In this table N is the number of demand points, $\mathcal {H}$ is the equation of the separating hyperplane (line), CPUTime is the CPU-time and $f^*$ and $x^*$ are the objective value and coordinates of the optimal solution reported with the corresponding approach, respectively. In order to compare our objective values and those obtained in [18] or [27], we have evaluated such values by using the solution obtained in those papers, where the authors provided a precision of two decimal places. This evaluation was motivated because we found several typos in the values reported in the papers. The goal of this block of data is to compare the quality of solutions obtained by the different methods. Comparing with our method, we point out that our solutions are superior since we always obtain better objective values than those in [18] or [27]. These results are not surprising since both [18] and [27] apply approximate methods whereas our algorithm is exact. Furthermore, the approach in [27] is much more computationally costly than ours. Additionally, in order to check whether a rapid transit line can improve the transportation costs from the demand points to the new facility, we report in Table 2 the results obtained for the same data sets applied to Problem (PT) taking $\Vert \cdot \Vert _\mathcal {H} = \frac{1}{4} \ell _\infty$. We observe that in this case the overall saving in distance traveled ranges in $5\%$ to $24\%$.

Table 1 Comparison of results from Parlar [18] and Zafaranieh et al. [27] and our approach (P)

Table 2 Results of model (PT) with $\Vert \cdot \Vert _\mathcal {H} = \frac{1}{4} \ell _\infty$ for the data sets in [18] and [27]

Table 3 reports the results of the second block of experiments. In this block, we test the implementation of our SOCP algorithm over the 50-points data sets in [12]. The goals are: (1) to check the efficiency of our methodology for a well-known data set in location theory, considering different norms in the different media, over the models (P) and (PT) (Note that in [18] and [27] only (P) is solved using $\ell _1$ and $\ell _2$-norms); and (2) to provide some benchmark instances to compare current and future methodologies for solving (P) and (PT). To this end, we report CPU times and objective values for different combination of $\ell _p$-norms ($\ell _2$, $\ell _3$ and $\ell _{1.5}$) and polyhedral norms ($\ell _1$, $\ell _\infty$) fulfilling the conditions $p_A > p_B$ for Problem (P) and $p_\mathcal {H} > p_A \ge p_B$ for Problem (PT) and different slopes for the separating hyperplane $\mathcal {H}=\{x \in \mathbb {R}^2: y=\lambda x\}$ with $\lambda \in \{1.5, 1, 0.5\}$ to classify the demand points.

Finally, Table 4 shows the results of our computational test for the third block of experiments. The goal of this block is to explore the limits in: (1) number of demand points, (2) dimension of the framework space; and (3) combination of norms, that can be adequately handled by our algorithm for solving problems (P) and (PT). For this purpose, we consider randomly generated instances with $N \in \{ 5000, 10{,}000, 50{,}000\}$ demand points in $[0,1]^d$, for $d=2, 3$ and 5. The separating hyperplane was taken as $\mathcal {H}=\{x \in \mathbb {R}^d: x_d=0.5\}$ and the different norms to measure the distances in each region ($\ell _1$, $\ell _2$, $\ell _{1.5}$, $\ell _3$ and $\ell _\infty$) combined adequately to fulfill the conditions (see Lemma 16 and Proposition 21) to assure that the problems are well-defined and that the different instances of Problem (PT) do not reduce to (P). From Table 3, we conclude that our method is rather robust so that it can efficiently solve instances with more than 50,000 demand points in high dimensional spaces ($d=2, 3 , 5$) and different combinations of norms in a few seconds. We have observed that instances with polyhedral norms, in particular $\ell _1$, are in general harder to solve than those with smooth norms. This behavior is explained because the representation of polyhedral norms requires to add constraints depending on the number of extreme points of their unit balls. This figure grows exponentially with the dimension and for instance, for 50,000 points in dimension $d=5$, our formulation needs $50{,}000 \times 5 \times 32 = 8{,}000{,}000$ linear inequalities in order to represent the norm $\ell _1$. This results in an average CPU time of 1019.48 s (with a maximum of 3945.82 s) for those problems where either $\ell _{p_A}$ or $\ell _{p_B}$ equals $\ell _1$, whereas the CPU time for the remaining problems in dimension $d=5$ is 215.69 s (with a maximum of 697.50 s).

Table 3 Results for the 50-points data set in [12]

Table 4 CPU Times in seconds for randomly generated data sets

6 Extensions

In this section we state some additional results for some variations of the problems that we addressed in previous sections: (1) each demand point $a\in A$ ($b\in B$) has associated two different norms, which are different from those associated to other points, to measure distances at each side of the separating hyperplane: and (2) the shortest length path between two points in the same half-space is allowed to be computed using, if convenient, some displacement throughout the hyperplane. Observe that the first case is the natural extension to this framework of the so called location problems with “mixed” norms; whereas the second case extends the applicability of the separating media as a general rapid transit space in the transportation problem.

6.1 Location problems with mixed norms

Location problems with mixed norms are those where each demand point is allowed to measure distances with a different distance measure. The interpretation is that each demand point may be using a different transportation mode so that its velocity is different from one another. This framework can also be applied to the location problems considered in this paper. Indeed, it suffices to endow each single demand point with two norms one on each side of the separating hyperplane.

Let us assume that each demand point $a \in {\mathrm{H}}_A$ (resp. $b \in {\mathrm{H}}_B$) has associated two norms $\Vert \cdot \Vert _{p_a^A}$ and $\Vert \cdot \Vert _{p_a^B}$ (resp. $\Vert \cdot \Vert _{p_b^A}$ and $\Vert \cdot \Vert _{p_b^B}$) such that each one of them is used to measure distances with respect to the points in ${\mathrm{H}}_A$ or in ${\mathrm{H}}_B$.

This way, for any $x \in \mathbb {R}^d$ the distance between x and $z\in A \cup B$ can be computed as:

$$\begin{aligned} d(z, x) = \left\{ \begin{array}{ll} \Vert z-x\Vert _{p_z^i} &{}\quad \forall x,z \in H_i, i \in \{A, B\}\\ \min _{y \in \mathcal {H}} \Vert z- y\Vert _{p_z^i} \!+\! \Vert y-x\Vert _{p_z^j}&{}\quad \forall x\in H_j, z \in H_{i}, i,j \in \{A, B\}, i \!\ne \! j \\ \end{array}\right. \end{aligned}$$

(47)

With this generalized framework for measuring distances from the different demand points, we can consider the following location problem: Let A and B be two finite sets of given demand points in $\mathbb {R}^d$, and $\omega _a$ and $\omega _b$ be the weights of the demand points $a \in A$ and $b \in B$, respectively. Consider $\mathcal {H}=\{x \in \mathbb {R}^d: \alpha ^t x = \beta \}$ to be the separating hyperplane in $\mathbb {R}^d$ with $\alpha \in \mathbb {R}^d$ and $\beta \in \mathbb {R}$, and

$$\begin{aligned} {\mathrm{H}}_A = \{x \in \mathbb {R}^d: \alpha ^t x \le \beta \} \quad \text {and} \quad {\mathrm{H}}_B = \{x \in \mathbb {R}^d: \quad \alpha ^t x > \beta \}. \end{aligned}$$

The goal is to find the new facility $x \in \mathbb {R}^d$ minimizing the overall distance (47) to all the demand points, i.e.,

$$\begin{aligned} \displaystyle \min _{x\in \mathbb {R}^d} \; \displaystyle \sum _{a \in A} \omega _a d (x, a) + \displaystyle \sum _{b\in B} \omega _b \,d(x, b). \end{aligned}$$

(48)

A similar proof to the one for Theorem 6, allows us to write the following valid formulation for Problem (48).

Corollary 25

Let $x^*\in \mathbb {R}^d$ be the optimal solution of (48). Then, $x^*$ is the solution of one of the following two problems:

$$\begin{aligned} \min&\displaystyle \sum _{a \in A} \omega _a z_a + \displaystyle \sum _{b \in B} \omega _b \theta _b + \displaystyle \sum _{b \in B} \omega _b u_b\\ \hbox {s.t. } \;&z_a \ge \Vert x-a\Vert _{p_a^A}, \; \forall a\in A,\\&\theta _b \ge \Vert x-y_b\Vert _{p_b^A}, \; \forall b\in B,\\&u_b \ge \Vert b- y_b\Vert _{p_b^B}, \; \forall b\in B,\\&\alpha ^t y_b = \beta , \; \forall b\in B, \\&\alpha ^tx \le \beta ,\\&z_a \ge 0,\; \forall a \in A,\\&\theta _b, u_b \ge 0,\; \forall b \in B,\\&x, y_b \in \mathbb {R}^d. \end{aligned}$$

$$\begin{aligned} \min&\displaystyle \sum _{b\in B} \omega _b z_b + \displaystyle \sum _{a \in A} \omega _a \theta _a + \displaystyle \sum _{a \in A} \omega _a u_a\\ \hbox {s.t. } \; \;&\theta _a \ge \Vert x-y_a\Vert _{p_a^B}, \; \forall a\in A,\\&u_a \ge \Vert a - y_a\Vert _{p_a^A}, \; \forall a\in A,\\&z_b \ge \Vert x-b\Vert _{p_b^B}, \; \forall b\in B,\\&\alpha ^t y_a = \beta , \; \forall a\in A, \\&\alpha ^t x \ge \beta ,\\&z_b \ge 0,\; \forall b \in B,\\&\theta _a, u_a \ge 0,\; \forall a \in A,\\&x, y_a \in \mathbb {R}^d. \end{aligned}$$

Once again, if we assume that all the considered norms are $\ell _p$ or polyhedral then the above problems admit reformulations as second order cone or linear programs that can be solved efficiently with good computational results as shown in the previous sections. The reader may note that the extension of the location problems with mixed norms to the framework in the Sect. 4 is similar and thus the details are not included here.

6.2 Location problems and critical reflection

Motivated by some practical situations in transportation systems using rapid transit lines and critical reflection in Physics, here we consider another extension of the location problem addressed in the previous sections. Depending on the nature of the media separating the space it may be advantageous not only to use it to determine the shortest path between points in different regions but also between points in the same half-space. In these cases, a shortest path between a and b in the same half-space may also consist of three legs: the first one from a to the hyperplane, the second one within the hyperplane and the last one from the hyperplane to b. Indeed, it is not difficult to realize that this type of pattern may induce distance measures with smaller length than those where displacements on the separating media are not allowed for points in the same region. We illustrate this behavior with the following example.

Example 26

Let us consider the hyperplane $\mathcal {H}=\{(x, y) \in \mathbb {R}^2: x-y=0\}$, $a=(4,3) \in H_B$ and $b=(8,7) \in H_B$. Assume that the norm in $H_B$ is $\ell _1$ while the norm in H is $\ell _{\infty }$. The shortest path length with the framework described in the previous sections is $d_1(b, a) = \Vert b-a\Vert _1 = |8-4| + |7-3| = 8$. However, using the alternative approach previously described, the shortest path from b to a goes through the hyperplane $\mathcal {H}$ and thus $d(b, a) = d_{1} (b, (7,7)) + d_\infty ((7,7), (4,4)) + d_1((4,4), a) = 1 + 3 + 1 = 5$. Figure 10 shows the difference between both paths: with a dashed line the direct path with the $\ell _1$-norm and with a bold line the three legs of the path throughout the hyperplane.

Let $\mathcal {H} = \{x \in \mathbb {R}^d: \alpha ^t x = \beta \}$ be a hyperplane that separates $\mathbb {R}^d$ in two half spaces ${\mathrm{H}}_A = \{x \in \mathbb {R}^d: \alpha ^t x \le \beta \}$ and ${\mathrm{H}}_B = \{x \in \mathbb {R}^d: \quad \alpha ^t x > \beta \}$; and assume that these regions are endowed with three distance measures $\Vert \cdot \Vert _{p_\mathcal {H}}$, $\Vert \cdot \Vert _{p_A}$ and $\Vert \cdot \Vert _{p_B}$, respectively. Furthermore, we are given two finite sets of demand points $A \subset {\mathrm{H}}_A$ and $B \subset {\mathrm{H}}_B$.

Fig. 10

Shortest paths from (4, 3) to (8, 7) with the different frameworks

First of all, we define the shortest path distance in the new framework.

$$\begin{aligned} d_{ex}(x,z)=\left\{ \begin{array}{l} \min \{ \Vert x-z\Vert _{i}, \min _{y_1, y_2 \in \mathcal {H}} \Vert x-y_1\Vert _{p_i} +\Vert y_1- y_2\Vert _{p_\mathcal {H}} + \Vert y_2- z\Vert _{p_i}\},\\ \quad \forall x,z \in H_i, \; i\in \{A,B\},\\ \min _{y_1, y_2 \in \mathcal {H}} \Vert x- y_1\Vert _{p_i} + \Vert y_1- y_2\Vert _{p_\mathcal {H}} + \Vert y_2- z\Vert _{p_j},\\ \quad \forall x \in H_{i}, \; z\in H_{j},\; i,j\; \in \{A,B\}, \; i\ne j. \end{array}\right. \end{aligned}$$

Next, the new location problem that appears in this extended framework is:

The following result gives a valid mixed integer nonlinear programming formulation for ($\mathrm{P}_\mathrm{EX}$).

Theorem 27

Let $x^*\in \mathbb {R}^d$ be the optimal solution of ($\mathrm{P}_\mathrm{EX}$) and $M_a, M_b >0$ sufficiently large constants for all $a \in A, b\in B$. Then, $x^*$ is the solution of one of the following two problems:

$$\begin{aligned}&\alpha ^ty^j_a = \beta ,\; \forall a \in A, \forall j=1, 2, \\&\alpha ^t y^j_b = \beta , \; \forall b \in B,\forall j=1, 2, \\&\delta _a \in \{0,1\}, \; \forall a \in A, \\&x, y^1_a, y^2_a, y_b^1, y_b^2\in \mathbb {R}^d,\\ \end{aligned}$$

Proof

The proof of this theorem is similar to the one in Theorem 7 once binary variables $\delta _a$ ($\delta _b$) are introduced to model the minimum that appears in the expression of $d_{ex}$ defined above.$\square$

The reader may observe that unlike the problems in the previous sections, the above reformulation falls within the field of mixed integer nonlinear programming and therefore, one cannot expect to solve these problems easily. In spite of that, if the norms considered in the different regions are either $\ell _p$ or polyhedral these problems are still solvable for medium size instances using nowadays available mixed integer second order cone programming solvers. Furthermore, we note in passing that valid values of the constants $M_a,\; M_b$ can be easily derived which result in values similar to those described at the end of Theorem 6.

Next, we illustrate Problem ($\mathrm{P}_\mathrm{EX}$) with an instance taken from [18].

Example 28

Consider the 18 points data set in [18]. Take as the separating line $\mathcal {H}=\{x \in \mathbb {R}^d: 1.5x - y = 0\}$. Assume that in ${\mathrm{H}}_A$ and ${\mathrm{H}}_B$ the distance is measured with the $\ell _1$-norm and that $\mathcal {H}$ is endowed with the $\ell _\infty$-norm. Figure 11 shows the demand points A and B, the hyperplane $\mathcal {H}$ and the solutions of problems ($\mathrm{P}_\mathrm{EX}$) and (PT), $x^*=(3.3333, 5)$ and $x^\prime =(9,8)$, respectively. The optimal value of ($\mathrm{P}_\mathrm{EX}$) is $f^*=128.00$ while the one for (PT), $f^\prime =132.9166$. In Fig. 12 we illustrate one of the shortest paths between the demand point (6, 1) and the optimal facility $x^*$, both in the same half-space, that travels through the hyperplane: $d((6,1), x^*) = 5.3333 + \frac{1}{4} \,4 = 6.3333$. This distance is smaller than the $\ell _1$ distance between them: $d_1 ((6,1), x^*) = 6.66666$.

Fig. 11

Points and optimal solution of Example 28

Fig. 12

Shortest paths from $x^*$ to (6, 1)

We have implemented this new formulation in Gurobi 5.6 in order to compare the results obtained with this approach and the one proposed in Sect. 4 for the data sets in [18, 27] and [12]. We have used very different distance measures in the half-spaces and the hyperplane, namely $\ell _1$ in ${\mathrm{H}}_A$ and ${\mathrm{H}}_B$ and $\frac{1}{4} \,\ell _{\infty }$ in $\mathcal {H} = \{(x,y) \in \mathbb {R}^2: y=\alpha _1 x\}$ with $\alpha _1 \in \{0.5, 1, 1.5\}$. (The reader may observe that this choice corresponds to the most extreme cases within the $\ell _p$-norms, namely $\ell _1$ and $\ell _{\infty }$.) The results are presented in Table 5. This table summarizes by rows the three different choices of $\alpha _1 \in \{0.5, 1, 1.5\}$. The table has three blocks, one per each $\alpha _1$. Each of these blocks shows the results for problems with different number of demand points $N \in \{4, 18, 30, 50\}$. For each model, namely (PT) and ($\mathrm{P}_\mathrm{EX}$), we report by columns the same information: coordinates of optimal solutions, optimal values and CPU time to get the solutions.

The CPU time was limited to two hours for solving the problem. In some problems the optimal facility is the same using the different approaches, although, as expected, the optimal value for ($\mathrm{P}_\mathrm{EX}$) is at least as good as for (PT). In some of the largest problems (those with 50 demand points) optimality could not be proven with this time limit, but the suboptimal solution already improves the one obtained when the “reflection” is not allowed. In those problems the CPU time was indicated as $>$7200 and we write in parenthesis the gap between such a solution and the best lower bound found when the time limit was reached. In general, the CPU times for these data sets are tiny when (PT) is run, and increase considerably when Problem ($\mathrm{P}_\mathrm{EX}$) is solved, due to the binary variables that appear in the model.

Table 5 Results of models (PT) and ($\mathrm{P}_\mathrm{EX}$)

7 Conclusions

This paper addresses the problem of locating a new facility in a d-dimensional space when the distance measures ($\ell _p$ or polyhedral norms) are different at each one of the sides of a given hyperplane $\mathcal {H}$. This problem generalizes the classical Weber problem, which becomes a particular case when the same norm is considered on both sides of the hyperplane. We relate this problem with the physical phenomenon of refraction and obtain an extension of the law of Snell with application to transportation models with several transportation modes. We also extend the problem to the case where the hyperplane is considered as a rapid transit media that allows the demand points to travel faster through $\mathcal {H}$ to reach the new facility. Extensive computational experiments run in Gurobi are reported in order to show the effectiveness of the approach.

Several extensions of the results in this paper are possible applying similar tools to those used here. Among them we may consider a broader family of location problems, namely Ordered median problems [19–21], with framework space separated by a hyperplane. Similar results to the ones in this paper can be obtained assuming that the sequence of lambda weights is non-decreasing monotone, inducing a convex objective function. Another interesting extension is the consideration of a framework space subdivided by an arrangement of hyperplanes. In this case, the problem can still be solved using an enumerative approach based on the subdivision of the space induced by the hyperplanes although it will be necessary to elaborate further on the computation of shortest length paths traversing several regions. Note that the subdivision induced by an arrangement of hyperplanes can be efficiently computed [11], although its complexity is exponential in the dimension of the space. This topic will be the subject of a follow up paper.