Nested-solution facility location models

Abstract

Classical facility location models can generate solutions that do not maintain consistency in the set of utilized facilities as the number of utilized facilities is varied. We introduce the concept of nested facility locations, in which the solution utilizing p facilities is a subset of the solution utilizing q facilities, for all $i \le p < q \le j$, given some lower limit i and upper limit j on r, the number of facilities that will be utilized in the future. This approach is demonstrated with application to the p-median model, with computational testing showing these new models achieve reductions in both average regret and worst-case regret when $r \ne p$ facilities are actually utilized.

1 Introduction

Selecting the locations for a set of facilities to be opened in order to service a set of customers is one of the most widely studied and applied problems in all of operations research. Since the foundational work of Hakimi in [10, 11], thousands of authors have published works examining facility location problems, with [10] currently cited by more than 3000 papers, according to Google Scholar.

However, as with any model, when an operations research analyst attempts to use results from a facility location problem formulation to influence decision making, the recommendations must be presented in a manner that is comprehensible to the decision maker. One aspect of the solutions obtained by traditional facility location models that can be difficult to communicate to decision makers is a potential lack of consistency in the set of utilized facilities as the number of utilized facilities is varied. For example, consider a stylized problem in which each demand point is assigned service at its nearest opened facility, where the objective is to minimize the sum of the distances between each demand point and its assigned facility. Assume that demand exists at five points located along a unit line segment at locations 0, 0.25, 0.5, 0.75 and 1. Suppose that one new facility could be placed at any of these demand points; in this case it is apparent that the optimal solution is to place the facility at the line segment’s midpoint. If two facilities were to be utilized, there are alternative optimal solutions (e.g., place the facilities at 0 and 0.75, or place the facilities at 0.25 and 0.75), but there is no optimal solution that places a facility at 0.5, demonstrating an inconsistency in the model’s recommendations as the number of facilities increases from one to two.

The ability of the analyst to “sell” the modeling solution can be hindered by the extent to which this inconsistency property, while demonstrably valid from a mathematical perspective, is nevertheless at odds with a decision maker’s intuition. The challenge imposed by this lack of consistency on the implementation of model results is most pronounced when the decision maker is uncertain about the number of facilities to be utilized in the future. In response, we introduce the concept of nested facility locations, defined as follows. A set of facility location solutions are said to be nested if the solution utilizing p facilities is a subset of the solution utilizing q facilities, for all $i \le p < q \le j$, given some lower limit i and upper limit j on r, the number of facilities that will be utilized in the future. Observe that such a set of nested solutions cannot exhibit the inconsistency discussed above. The nested concept is consistent with a situation in which an initial decision is made to prepare a set of j locations for potential future use, the decision maker then engages with various constituencies to discuss the $j-i+1$ alternative solutions (and does not wish to demonstrate this inconsistency during those discussions), and finally the actual number of facilities to be opened is then determined.

These concepts, applicable to situations in which the future number of facilities is uncertain, have parallels to the broader class of models for optimization under uncertainty. More recently, a body of research has arisen examining linkages between combinatorial optimization (such as the facility location models of [10]) and machine learning methods, e.g., [12], which explicitly considered facility location problems as an application area in which machine learning methods could be used to address uncertainties in input parameters.

Previous works have considered facility location models when the number of opened facilities is uncertain. The p-median problem with an uncertain number of future facilities was first examined by [7]. These authors assumed that an initial set of p facilities must be opened, and that it will subsequently become necessary to open an additional set of between 0 and q facilities, assuming a minimax regret objective. While their model ensures that the initial p facilities selected are included in every future set of $p, p+1,\ldots ,p+q$ facilities, these authors do not enforce that the optimal set of $p+i$ facilities are included in the optimal set of $p+j$ facilities where $0<i<j \le q$; that is, the solutions are not nested. Later, [5] considered this same problem, minimizing the expected regret, with a slightly modified mathematical representation, and provided heuristic solution methods that were found to be effective for large problem instances, albeit with a limitation that $q=1$. In [16], the authors considered a problem in which both the number of future facilities is uncertain and future demand is uncertain, identifying a set of initial facilities to open and a set of future relocations that include potentially opening new facilities and closing facilities opened in the initial time period. Clearly, as this formulation allows for facilities to be closed, the nested property is not enforced here.

The main contributions of this paper are the introduction of the concept of nested facility locations and the formulation of the nested p-median problem using two objective functions, minimizing expected regret and minimizing maximum regret. The use of a regret-based objective function is common in optimization problems (and facility location problems specifically) in which the underlying data are assumed to be uncertain and the decisions made at the outset constrain the recourse decisions available to the decision maker in the future; see e.g., [1, 7, 13, 14]. We develop two heuristic approaches, based on Lagrangian relaxation, to efficiently solve the model under each objective for large problem instances. Our computational results demonstrate both the novelty of the model compared to a similar approach by [7], and also the improved performance of our approach over a classic p-median model under an uncertain number of facilities.

2 Mathematical model

Consider the following p-median problem in which a set of facilities are opened from a set of candidate facility locations, and each member of a set of demand points is assigned to receive service from a single opened facility, such that the total distance between demand points and their assigned facilities is minimized.

Sets

• I: set of demand points

• J: set of candidate facility locations

Decision variables

• $x_j$: equals one if facility j is opened, equals zero otherwise

• $y_{ij}$: equals one demand point i is assigned to be served by facility j, equals zero otherwise

• z: total distance between demand points and the facilities to which they are assigned

Data parameters

• $\phi$: number of facilities to be opened

• $\gamma _{ij}$: distance between demand point i and facility j

$$\begin{aligned} \min z = \sum _i \sum _j \gamma _{ij} y_{ij} \end{aligned}$$

(1)

$$\begin{aligned} \sum _j x_{j}= \phi \end{aligned}$$

(2)

$$\begin{aligned} \sum _j y_{ij} = 1 \qquad \forall i \end{aligned}$$

(3)

$$\begin{aligned} y_{ij} \le x_{j} \qquad \forall i, \; \forall j \end{aligned}$$

(4)

$$\begin{aligned} x_j \in \{0,1\} \qquad \forall j \end{aligned}$$

(5)

$$\begin{aligned} y_{ij} \ge 0 \qquad \forall i, \; \forall j \end{aligned}$$

(6)

Constraint (6) is sufficient to limit variable $y_{ij}$ to take only binary values, based on the model structure [6]. Suppose this p-median model (1)–(6) were solved across a range of values for $\phi$, denoted as follows:

Sets

• H: set of potential numbers of facilities to be opened

Data parameters

• $\hat{\phi }_h$: number of facilities to be opened under set element $h \in H$, ordered such that $\hat{\phi }_{h+1} = \hat{\phi }_{h}+1 \quad \forall h$

Let $\hat{\alpha }_h$ denote the optimal objective function value obtained when this p-median model (1)–(6) is solved with $\hat{\phi }_h$ facilities to be opened.

The nested p-median problem can then be formulated as follows:

Decision variables

• $\hat{x}_{jh}$: equals one if facility j is opened when $\hat{\phi }_h$ facilities are opened, equals zero otherwise

• $\hat{y}_{ijh}$: equals one if demand point i is assigned to be served by facility j when $\hat{\phi }_h$ facilities are opened, equals zero otherwise

• $\hat{z}_h$: total distance between demand points and the facilities to which they are assigned when $\hat{\phi }_h$ facilities are opened

• $\hat{w}$ maximum relative penalty for the nested solution objective function, across all elements of set H

$$\begin{aligned} \min \sum _h \hat{z}_h \end{aligned}$$

(7)

$$\begin{aligned} \min \hat{w} \end{aligned}$$

(8)

$$\begin{aligned} \sum _j \hat{x}_{jh}= \hat{\phi }_h \qquad \forall h \end{aligned}$$

(9)

$$\begin{aligned} \sum _j \hat{y}_{ijh} = 1 \qquad \forall i, \; \forall h \end{aligned}$$

(10)

$$\begin{aligned} \hat{y}_{ijh} \le \hat{x}_{jh} \qquad \forall i, \; \forall j, \; \forall h \end{aligned}$$

(11)

$$\begin{aligned} \hat{x}_{jh} \in \{0,1\} \qquad \forall j, \; \forall h \end{aligned}$$

(12)

$$\begin{aligned} \hat{y}_{ijh} \ge 0 \qquad \forall i, \; \forall j, \; \forall h \end{aligned}$$

(13)

$$\begin{aligned} \hat{z}_h = \sum _i \sum _j \gamma _{ij} \hat{y}_{ijh} \qquad \forall h \end{aligned}$$

(14)

$$\begin{aligned} \hat{x}_{jh} \ge \hat{x}_{j,(h-1)} \qquad \forall j, \; \forall h>1 \end{aligned}$$

(15)

$$\begin{aligned} \hat{w} \ge \frac{\hat{z}_h-\hat{\alpha }_h}{\hat{\alpha }_h} \qquad \forall h \end{aligned}$$

(16)

Minimizing expected regret is equivalent to (for the p-median problem) minimizing expected distance across the elements of set H [13]. Therefore, model (7), (9)–(15), denoted NestedPmedExpectedRegret (NPER), minimizes the expected regret of the nested model. Alternatively, formulation (8)–(16), denoted NestedPmedMinimaxRegret (NPMR) solves a minimax relative regret objective for the nested model.

The p-median problem is known to be NP-hard [9]. For NPER, if $|H|=1$, NPER reduces to the classical p-median problem, and thus NPER is also NP-hard [14]. Because NPMR is minimax relative regret model for the p-median, NPMR is also NP-hard [1].

3 Initial computational results: illustrating regret

In this section, we conduct an initial numerical study to demonstrate the regret calculations, evaluating the performance of the NPER and NPMR models using a 30-instance set of benchmark problems from the online repository [15]. Each instance defines an ordered list of 100 locations and provides a matrix of the distances between each pair of locations. For our computational testing, we assume for each instance that the first 20 locations in the ordered list are candidate facility locations and that the other 80 locations are demand points. Assume an uncertain number of facilities are to be opened, ranging from a minimum of one facility to a maximum of four facilities. Models NPER and NPMR were both coded in GAMS 33.2 and solved using CPLEX 12.10.

3.1 Contrasting results with NOFUN

To help illustrate the difference between these nested models and the “Number Of Facility Locations Uncertain” (NOFUN) formulation of [7], consider one instance (number 27) from this test problem set. Models NPER and NOFUN (with an expected regret objective function) were each solved for this instance. Figure 1 presents an illustration of this test problem, graphed in the (x,y)-plane. The text boxes appearing inside the graph indicate for which values of $\phi _h$ a facility is opened at the corresponding location. For example, the black box located nearest to the lower-left corner of the figure indicates a facility location that was utilized in the NOFUN solution for $\hat{\phi }_h=4$, but which was not opened for any other value of $\hat{\phi }_h$. Observe that the NPER solution utilizes a total of four locations, as required by the nested property. The NOFUN solution, however, utilizes a total of six different locations. Both model solutions are identical for $\hat{\phi }_h=1$ and $\hat{\phi }_h=2$. Moreover, both models exhibit the nested property for values of $\hat{\phi }_h$ between one and three (although the third facility opened is at a different location for each model). However, observe that the NOFUN solution for $\hat{\phi }_h=4$ is a significant departure from the NOFUN solution for $\hat{\phi }_h=3$, with only one location in common between the two solutions.

Fig. 1

Facility locations opened in NPER and NOFUN solutions, problem instance 27

3.2 Calculating regret

As an illustration of how we calculate regret, consider again instance number 27 from the test problem data set. Suppose that the p-median model (denoted PMED) were solved for some value of $\phi$. This PMED model solution could then be utilized as the basis for a set of nested facility opening recommendations. For example, suppose that the 2-median solution for a particular test instance opened facilities at locations $j_1$ and $j_2$. Model NPER could then be run, forcing these two locations to define the solution for $\hat{\phi }_h=2$, thereby generating an optimized nested facility solution based on this 2-median solution; denote the solutions obtained from this two-step approach as Variations on the p-median solution (VpMS). This VpMS presents the best possible performance that could be achieved, were a p-median solution implemented, but it later become necessary to add or remove facilities from this solution.

Figure 2 illustrates this test problem instance, with the text boxes appearing inside the graph again indicating when a facility is opened at the corresponding location. Here, the PMED solutions are presented for $\phi \in \{1,2,3\}$, and are denoted by black boxes. The V2MS, denoted by red diamonds, is also presented for $\hat{\phi }_h \in \{1,2,3\}$. Observe that the V2MS presents a nested solution that is identical to the PMED solution for $\phi =$2 (by design).

Consider now the different solutions corresponding to one opened facility. Due to the nested property, the V2MS is limited to selecting one of the two facilities utilized in the 2-median solution; this 1-facility solution from the V2MS has objective function value equal to 235,518. Contrast this to the optimal 1-median solution, which has objective function value ($\hat{\alpha }_1$) equal to 218,369, and utilizes a facility that does not appear in the 2-median solution. Here, the V2MS has a relative regret equal to 7.9% when one facility is opened. Similarly, the optimal 3-median solution utilizes a facility that does not appear in either the 1-median or 2-median solutions, and is thus able to outperform the nested 3-facility solution obtained from the V2MS. Table 1 presents the regret calculations for this test problem instance, evaluating the V2MS relative to the PMED solution when 1, 2, 3 and 4 facilities are to be utilized.

Fig. 2

Facility locations opened in V2MS and PMED solutions, problem instance 27

Table 1 Regret calculations for problem instance 27

3.3 Comparing solution quality

Models NPER and NPMR were solved across all 30 test instances, with set $H=\{1,2,3,4\}$. To provide a basis for comparison of solution quality, model PMED was also solved for 1, 2, 3 and 4 facilities for each test instance. Note that this required, in total, 30 runs of NPER, 30 runs of NPMR, and 120 runs of PMED. Each of these PMED model solutions was then utilized as the basis for a set of nested facility opening recommendations, denoted VpMS as discussed above, and thus requiring an additional 120 runs of NPER. Figure 3 presents the average regret and maximum regret, across the 30 test instances, for each model solution, varying the actual number of facilities to be opened on the horizontal axis.

Fig. 3

Average regret and maximum regret across solutions

Observe that the VpMS solution has zero regret when p facilities are to be opened, by definition. However, should a p-median solution be implemented, but it subsequently become necessary to increase or decrease the number of facilities, the regret can be quite large. For the V1MS solution, the average regret ranges between 4.3% (for two opened facilities) and 6.4% (for four opened facilities), with corresponding maximum regret values of 13.5% and 19.0%. For the V2MS, V3MS and V4MS solutions, the greatest values for both average regret and maximum regret occur at $\phi _h$=1 opened facility (with average regret values of 7.3%, 9.9% and 11.3%, respectively, and maximum regret values of 20.6%, 21.6% and 28.0%, respectively).

The NPER and NPMR solutions both significantly reduce the potential exposure to large values of average regret and maximum regret, relative to the VpMS solutions. The NPER average regret varies between a minimum value of 1.7% (for two opened facilities) and a maximum of 3.9% (for four opened facilities), with maximum regret values ranging between 9.3 and 10.1% (for three and one opened facilities, respectively). Similarly, the NPMR average regret varies between 2.4 and 3.5% (for one and three opened facilities, respectively), while its maximum regret values range between 8.2% and 9.6% (for two and three opened facilities, respectively).

4 Solution approach

In this section we develop a heuristic approach based on Lagrangian relaxation (LR) to solve NPER and NPMR. A commonly used LR approach to solve a standard p-median problem involves relaxing constraints (3) [8]. This type of constraint appears in NPER and NPMR in constraints (10). The additional complicating constraints in NPER and NMPR are the nesting constraints (15). For our LR algorithm, we replace the original nesting constraints (15) from the NPER and NPMR models with the following set of constraints:

$$\begin{aligned} \hat{x}_{j,h} \ge \hat{x}_{j,h-h'} \; \forall j, \; \forall h>1, \; \forall h' <h \end{aligned}$$

(17)

The constraint set (17) includes constraints (15) as well as other redundant constraints, however we find empirically that relaxing constraints (17) enhances the lower bound.

4.1 Solving NPER using Lagrangian relaxation

We define $\lambda _{ih}$ and $\nu _{j,h,h'}$ as the Lagrange multiplier vectors associated with constraints (10) and (17), respectively. The Lagrangian relaxation $L(\lambda , \nu )$ of NPER with respect to constraints (10) and (17) is given by

$$\begin{aligned}&\min _{\hat{x},\hat{y}} \sum _h \sum _i \sum _j \gamma _{ij} \hat{y}_{ijh} + \sum _i \sum _h \lambda _{ih}\left( 1-\sum _j \hat{y}_{ijh}\right) \nonumber \\&\qquad + \sum _j \sum _{h>1} \sum _{h'<h} \nu _{j,h,h'}(\hat{x}_{j,h-h'}-\hat{x}_{j,h}), \end{aligned}$$

(18)

subject to constraints (9), (11)–(13).

Rearranging terms to isolate the $\hat{x}$ and $\hat{y}$ variables, $L(\lambda , \nu )$ is rewritten as

$$\begin{aligned}&\min _{\hat{x},\hat{y}} \sum _i\sum _j \sum _h (\gamma _{ij} - \lambda _{ih})\hat{y}_{ijh} + \sum _i \sum _h \lambda _{ih} + \sum _j \left\{ \hat{x}_{j,1} \sum _{h=2}^{|H|} \nu _{j,h,h-1} \right\} \nonumber \\&\qquad + \sum _j \left\{ \sum _{h=2}^{|H|-1} \hat{x}_{jh}\left\{ \left( \sum _{h'=h+1}^{|H|} \nu _{j,h',h'- h}\right) - \left( \sum _{h'=1}^{h-1} \nu _{j,h,h'}\right) \right\} \right\} \nonumber \\&\qquad - \sum _j \left\{ \hat{x}_{j,|H|} \left\{ \sum _{h'=1}^{|H|-1} \nu _{j,|H|,h'} \right\} \right\} \end{aligned}$$

(19)

subject to constraints (9), (11)–(13).

4.1.1 Calculating the NPER lower bound

Define $\rho _{jh}$ as the contribution of the (facility j, scenario h)-pair to the objective function of $L(\lambda , \nu )$. Then, $\rho _{jh}$ can be constructed based on (19) as:

$$\begin{aligned} \rho _{jh} = {\left\{ \begin{array}{ll} \varDelta _{jh} + \sum _{h=2}^{|H|} \nu _{j,h,h-1} &{} \text{ if } h=1 \\ \varDelta _{jh} + (\sum _{h'=h+1}^{|H|} \nu _{j,h',h'- h}) - ( \sum _{h'=1}^{h-1} \nu _{j,h,h'}) &{} \text{ if } 1< h < |H|\\ \varDelta _{jh} - \sum _{h'=1}^{|H|-1} \nu _{j,|H|,h'} &{} \text{ if } h = |H| \end{array}\right. } \end{aligned}$$

(20)

where $\varDelta _{jh} = \sum _i \min (0,\gamma _{ij}- \lambda _{ih})$.

For a given set of multipliers $\lambda$ and $\nu$, the optimal solution for this problem can be obtained using the following approach. For each scenario h, denote the $\hat{\phi }_h$ smallest values of $\rho _{jh}$ as $P^*_h=\{\hat{\rho }_{j_1}, \hat{\rho }_{j_2}, \ldots , \hat{\rho }_{j_{ \hat{\phi }_h}}\}$. Then, for each h, set $\hat{x}_{jh} =1$ for $j \in P^*_h$. Then set $\hat{y}_{ijh} = \hat{x}_{jh}$ if $\gamma _{ij}-\lambda _{ih} < 0$, otherwise set $\hat{y}_{ijh}$ to zero. Then calculate the objective function value of $L(\lambda , \nu )$, denoted as $Z_L(\lambda , \nu )$.

Note that since we relax constraints (17), the optimal solution to $L(\lambda , \nu )$ may not have a nested solution. This motivated our decision to formulate the LR using the nesting constraints (17), which include many redundant instances, rather than the more-compact nesting constraints (15). In this way, we would expect to encounter more frequent nesting in the lower bound solution in later iterations of the algorithm (which we observed to occur in our computational testing).

4.1.2 Calculating the NPER upper bound

We can find an upper bound to NPER by generating a feasible solution using part of the lower bound solution to $L(\lambda , \nu )$. The lower bound solution utilizes $\tilde{\varPhi } \ge \hat{\phi }_{|H|}$ facilities. We apply Algorithm 1, described below, to find $\hat{\phi }_{|H|}$ nested facilities out of the $\tilde{\varPhi }$ facilities chosen in the lower bound solution. The idea behind Algorithm 1 is to use information about a facility’s contribution to $L(\lambda , \nu )$ as a proxy for its value in an upper bound solution. After values of $\hat{x}_{jh}$ are determined using Algorithm 1, it is simple to set the corresponding values for $\hat{y}_{ijh}$ by setting $\hat{y}_{ijh}=1$ for the closest utilized facility j (i.e., $\hat{x}_{jh}=1$) We may then calculate the objective function, denoted as $Z_U$.

4.1.3 Subgradient optimization method for NPER

A subgradient method (Algorithm 2) is used to calculate values for the Lagrange multipliers $\lambda _{ih}$ and $\nu _{j,h,h'}$ at each iteration. We use subgradient smoothing to enhance convergence of the lower bound [2]. The parameters for the subgradient method are listed in Table 2 below, followed by Algorithm 2.

Table 2 Subgradient method parameters for solving NPER

4.2 Solving NPMR using Lagrangian relaxation

We re-organize constraint (16) as follows:

$$\begin{aligned} 0 \ge \frac{\hat{z}_h}{\hat{\alpha }_h} - (1 + \hat{w}) \; \forall h \end{aligned}$$

(21)

We define $\lambda _{ih}$, $\nu _{j,h,h'}$, and $\delta _h$ as the Lagrange multipliers associated with constraints (10), (17), and (21), respectively.

The Lagrangian relaxation $L(\lambda , v, \delta )$ of NPMR is given by

$$\begin{aligned}&\min _{\hat{x},\hat{y}, \hat{w}} \hat{w} + \sum _i \sum _h \lambda _{ih}\left( 1-\sum _j \hat{y}_{ijh}\right) \nonumber \\&\qquad + \sum _j \sum _{h>1} \sum _{h'<h} \nu _{j,h,h'}(\hat{x}_{j,h-h'}-\hat{x}_{j,h})\nonumber \\&\qquad + \sum _h \delta _h \left( \frac{\sum _i\sum _j \gamma _{ij}\hat{y}_{ijh}}{\hat{\alpha }_h} - 1 - \hat{w}\right) \end{aligned}$$

(22)

subject to constraints (9), (11)–(13).

Rearranging terms to isolate the $\hat{x}$, $\hat{y}$, and $\hat{w}$ variables, $L(\lambda , \nu , \delta )$ is rewritten as

$$\begin{aligned} \min _{\hat{x},\hat{y}, \hat{w}}&\sum _i\sum _j \sum _h (\frac{\gamma _{ij}}{\hat{\alpha }_h}\delta _h - \lambda _{ih})\hat{y}_{ijh} + \sum _i \sum _h \lambda _{ih}+ \sum _j \left\{ \hat{x}_{j,1} \sum _{h=2}^{|H|} \nu _{j,h,h-1} \right\} \nonumber \\&+ \sum _j \left\{ \sum _{h=2}^{|H|-1} \hat{x}_{jh}\left\{ \left( \sum _{h'=h+1}^{|H|} \nu _{j,h',h'- h}\right) - \left( \sum _{h'=1}^{h-1} \nu _{j,h,h'}\right) \right\} \right\} \nonumber \\&- \sum _j \left\{ \hat{x}_{j,|H|} \left\{ \sum _{h'=1}^{|H|-1} \nu _{j,|H|,h'} \right\} \right\} \nonumber \\&+ \hat{w}\left( 1-\sum _h \delta _h\right) \end{aligned}$$

(23)

subject to constraints (9), (11)–(13).

4.2.1 Calculating the lower and upper bounds for NPMR

Define $\rho _{jh}$ as the contribution of the (facility j, scenario h)-pair to the objective function of $L(\lambda , \nu , \delta )$. Then, $\rho _{jh}$ can be constructed based on (23) as:

$$\begin{aligned} \rho _{jh} = {\left\{ \begin{array}{ll} \varPi _{jh} + \sum _{h=2}^{|H|} \nu _{j,h,h-1} &{} \text{ if } h=1 \\ \varPi _{jh} + (\sum _{h'=h+1}^{|H|} \nu _{j,h',h'- h}) - ( \sum _{h'=1}^{h-1} \nu _{j,h,h'}) &{} \text{ if } 1< h < |H|\\ \varPi _{jh} - \sum _{h'=1}^{|H|-1} \nu _{j,|H|,h'} &{} \text{ if } h = |H| \end{array}\right. } \end{aligned}$$

(24)

where $\varPi _{jh} = \sum _i \min (0,(\frac{\gamma _{ij}}{\hat{\alpha }_h}\delta _h - \lambda _{ih})$. For a given set of multipliers $\lambda$, $\nu$, and $\delta$, the optimal solution and objective function value for this problem can be obtained using the same approach developed for NPER, with one change. That is, the above formulation will have the following characteristic: In each iteration, if $1-\sum \delta _h > 0$, then it is optimal to set $\hat{w}=0$. Otherwise, if $1-\sum \delta _h < 0$, it is optimal to set $\hat{w}=\infty$. Denote the optimal objective function value of the lower bound problem as $Z_L(\lambda , \nu ,\delta )$. We then calculate the upper bound for NPMR using the same technique developed for NPER in Algorithm 1, with objective function value $Z_U$ equal to the maximum relative regret value obtained from equation (16).

4.2.2 Subgradient optimization method for NPMR

The parameters for our subgradient method to solve NPMR include the parameters used in the NPER subgradient method (listed in Table 2) as well as those listed in Table 3. The details of the method are described in Algorithm 3.

Table 3 Additional subgradient method parameters to solve NPMR

5 Computational results

We tested the LR-based solution algorithm for NPER (denoted LR-ER) and NPMR (denoted LR-MR) on a set of test problems from the online repository [4]. These problems are drawn from the p-median instances examined in [3]; in our computational testing we utilize the problem instances containing 400 or more nodes (denoted pmed16 through pmed40 at [4]). We assume that all nodes are both demand points and potential facility locations, thus $I=J$. Models NPER and NPMR were again both coded in GAMS 33.2 and solved using CPLEX 12.10, here using nesting constraints (17) rather than (15), for consistency with LR-ER and LR-MR. The computational results obtained with this off-the-shelf optimization software will be denoted OTS-ER (for NPER) and OTS-MR (for NPMR).

In our computational testing we initialized the LR parameters $\theta _1=\theta _2=\theta _3=0.75$ and $\zeta =0.8$. Values for step-size coefficients $\theta _1, \theta _2$ were reduced by 10% after 30 unimproved iterations. The Lagrange multipliers were initialized as $\lambda _{ih}^1=\nu _{j,h,h'}^1=\delta _h^1=2$, and the termination criteria were set at $\sigma =10^{-6}$ and $N=1000$. For all instances tested, we assumed set $H=\{1,2,3,4\}$.

The results of the computational testing for NPER appear in Table 4. Each value presented in this table for OTS-ER and LR-ER represents the average value, across all instances, for each problem size. A maximum run time of 600 s was utilized with GAMS/CPLEX, thus the results for LR-ER present the model’s status at 600 s of run time, to allow for comparison. Column UB presents the best feasible objective function value obtained by GAMS/CPLEX. Observe that for the smallest problems ($|I|=|J|=400$), OTS-ER was able to obtain a provably optimal solution in all instances, with an average run time of 413 s, outperforming LR-ER. For the problem size $|I|=|J|=500$, OTS-ER was able to obtain a provably optimal solution for 4 of the 5 instances, however in the remaining instance OTS-ER terminated after 600 s with an optimality gap of 100%. Similarly, for the problem size $|I|=|J|=600$, OTS-ER was able to obtain a provably optimal solution for 1 of the 5 instances, in 3 of the remaining instance OTS-ER terminated after 600 s with an optimality gap of 100%. For these two problem sizes, LR-ER was able to obtain solution with average optimality gaps of 0.50% and 0.38%, respectively, for $|I|=|J|=500$ and 600. For all instances of the largest problem sizes ($|I|=|J|=700$, 800 and 900), OTS-ER terminated after 600 s with an optimality gap of 100%. Observe that for these large problem sizes, the best feasible solutions obtained by OTS-ER had objective function values that were 79%, 36% and 56% greater, on average, than the best feasible solutions obtained by LR-ER for $|I|=|J|=700$, 800 and 900, respectively.

Table 4 NPER computational experience

The results of the computational testing for NPMR appear in Table 5. Each value presented in this table for OTS-MR and LR-MR represents the average value, across all instances, for each problem size. Due to its difficulty in obtaining a solution, the maximum run time was increased to 3600 s for GAMS/CPLEX. However, the results for LR-MR again present the model’s status at 600 s of run time, to emphasize its performance advantage. For all 25 instances tested, GAMS/CPLEX returned a solution with an optimality gap of 100% (and an objective function lower bound of $-10^{-4}$), thus we do not present the optimality gap in this table. Observe that the best feasible solutions obtained by OTS-MR are considerably worse than the solutions obtained by LR-MR (despite OTS-MR being provided six times the run time allowed to LR-MR), with OTS-MR having objective function values that were 6.0, 4.5, 3.0, 6.1, 3.7 and 4.9 times the best feasible solutions obtained by LR-MR, on average, for $|I|=|J|=400$, 500, 600, 700, 800 and 900, respectively.

Table 5 NPMR computational experience

6 Conclusion

This paper has introduced the concept of nested facility locations, in which the solution utilizing p facilities is a subset of the solution utilizing q facilities, for all $i \le p < q \le j$, given some lower limit i and upper limit j on r, the number of facilities that will be utilized in the future. Such an approach overcomes a challenge in the solutions to traditional facility location models, which can generate solutions that do not maintain consistency in the set of utilized facilities as the number of utilized facilities is varied. The nested facility location concept is demonstrated with application to the classic p-median model, with computational testing showing these new models achieve reductions in worst-case regret when $r \ne p$ facilities are actually utilized, relative to the best possible performance that could be achieved, were a p-median solution implemented, but it later become necessary to add or remove facilities from this solution.

We develop two heuristic approaches, based on Lagrangian relaxation (denoted LR-ER and LR-MR, respectively), to efficiently solve the model under each objective for large problem instances. Computational testing on a set of large problem instances found LR-ER and LR-MR to perform well, significantly outperforming the commercial solver GAMS/CPLEX on the largest problem instances.

Future extensions to this research could extend the nested concept to other facility location models, such as the p-center or maximum covering models. The nested concept could potentially be applied to facility location models that consider a budget on future facility opening and closing decisions, as in [16]. It would also be possible to extend these concepts to continuous facility location models, in which the facility locations are selected as coordinates in a planar region. Another potential extension would incorporate the nested concept to situations in which additional aspects of the model were assumed to be uncertain, such as the distances between demand points and facilities. The nested facility location concept could also be extended to stochastic optimization approaches, in which uncertainties are characterized by probability distributions.