The nestedness property of location problems on the line

Abstract

We prove the existence of a nestedness property for a family of common convex parametric tactical serving facility location problems defined on the line. The parameter t is the length of the serving facility (closed interval). The nestedness property means that, given any two facility lengths $t_1, t_2, 0 \le t_1<t_2$, there is an optimal solution with length $t_1$ which lies within some optimal solution with length $t_2$. The main idea of the proof is the representation of a serving facility as a point in ${\mathbb {R}}^2$ and the investigation of its geometrical properties. An intuitive graphical approach to the proof is given.

Appendix

This section contains two lemmas used in the paper. The lemmas are presented without the proofs. Detailed proofs of the lemmas can be found in Rozanov (2015).

1.1 Continuity of the optimal solution objective value of a parametrized LP problem

Lemma 6

Given a parametrized LP problem:

$$\begin{aligned} \begin{aligned}&\text{ Minimize } C^T\mathbf z \\&\text{ subject } \text{ to: }\\&A^T\mathbf z \le D, \\&E^T\mathbf z = G, \\&M^T\mathbf z \le R(t), \\&\mathbf z \ge 0,\\&\mathbf z \in {\mathbb {R}}^n,\;C \in {\mathbb {R}}^n,\; D \in {\mathbb {R}}^d,\;\\&A \in {\mathbb {R}}^{n \times d},\;G \in {\mathbb {R}}^g,\;E \in {\mathbb {R}}^{n \times g},\;M \in {\mathbb {R}}^{n \times m},\;\\&R(t) = \left( r_1(t),r_2(t),\ldots ,r_m(t)\right) ,\;\;\\&r_i(t): T \rightarrow {\mathbb {R}}^1,\; i = 1,\ldots ,m,\\&\text{ where } T \text{ is } \text{ a } \text{ finite } \text{ closed } \text{ connected } \text{ interval } \text{ on } {\mathbb {R}}. \end{aligned} \end{aligned}$$

(47)

Denote by H(t) the optimal objective value of (47). If (47) is feasible and bounded for all $t \in T$, and all functions $r_1(t),\ldots ,r_m(t)$ are continuous on T, then H(t) is a continuous function on T. Moreover, if $r_1(t),\ldots ,r_m(t)$ are concave, then H(t) is convex. In addition, if the functions $r_1(t),\ldots ,r_m(t)$ are linear, then H(t) is piecewise linear.

1.2 Monotonicity lemma

Lemma 7

Let $f(x):{\mathbb {R}}\rightarrow {\mathbb {R}}$ be a real-valued function defined on a closed interval $\hat{D} \in {\mathbb {R}}$, and suppose that the following property holds:

$$\begin{aligned} \begin{array}{l} \forall x\;\; \exists \epsilon >0\;s.t., \; f(x^-) \le f(x) \le f(x^+)\;\\ \forall x^- \in [x-\epsilon ,x) \cap \hat{D},\;\forall x^+\in (x,x+\epsilon ] \cap \hat{D},\\ \end{array} \end{aligned}$$

(48)

then, f(x) is a non-decreasing function of x.