Robustness of solutions to the capacitated facility location problem with uncertain demand

Abstract

We investigate the properties of robust solutions of the Capacitated Facility Location Problem with uncertain demand. We show that the monotonic behavior of the price of robustness is not guaranteed, and therefore that one cannot discriminate among alternative robust solutions by simply relying on the trade-off price-vs-robustness. Furthermore, we report a computational study on benchmark instances from the literature and on instances derived from a real-world application, which demonstrates the validity in practice of our findings.

1 Introduction

The Capacitated Facility Location Problem (CFLP) [10, 21] considered in this paper can be described as follows. We are given a set M of potential facility locations and a set N of customers. Associated with each $i \in M$ is a maximum capacity of the facility $s_i$, and each customer $j \in N$ is associated with a nonnegative demand $d_j$. Two types of cost arise: (i) the decision to establish a facility at i incurs a fixed-charge (setup) cost $f_i$ and (ii) for $i \in M$ and $j \in N$, a transportation cost $c_{ij}$ reflecting the expense if all of the demand of customer j is satisfied from facility i. The problem consists of minimizing the sum of the setup costs of opened facilities and of the transportation costs, while satisfying demand requirements and capacity constraints. The CFLP can be mathematically formulated as follows:

$$\begin{aligned} \text {(CFLP)} \quad \min \quad&\sum _{i\in M} f_i y_i + \sum _{i\in M} \sum _{j\in N} c_{ij} x_{ij} \nonumber \\ \text{ s.t. } \quad&\sum _{i\in M} x_{ij} = 1, \,\,\quad \forall j \in N, \end{aligned}$$

(1)

$$\begin{aligned}&\sum _{j \in N} d_{j}x_{ij} \le s_iy_i,\,\,\quad \forall i \in M, \end{aligned}$$

(2)

$$\begin{aligned}&x \in X, \end{aligned}$$

(3)

$$\begin{aligned}&y_{i} \in \{0,1\},\,\, \forall i \in M. \end{aligned}$$

(4)

Problem CFLP deals with the following two-level decision variables: (i) strategic variables $\mathbf{y}$, used to model the long-term decisions, and (ii) operational variables $\mathbf{x}$, which model the short-term, operational part of the problem. In the literature, there are two main variants of the CFLP: the single source CFLP (SS-CFLP), where a customer must be completely assigned to a single facility (i.e, $X = \{0,1\}^{m \times n}$), and the multiple source CFLP (MS-CFLP) where a customer could be assigned to several facilities [15] (i.e., $X \subseteq \mathbb {R}^{m \times n}_+$). Several applications in transportation, logistics, telecommunications, and production planning can be formulated using models having the same structure of model CFLP.

We assume that the demand coefficients $d_{j}$ are uncertain, and that the model of data uncertainty is based upon the following scenario space. Let each coefficient $d_{j} \ge 0$ be an (independent), symmetric, and bounded random variable $\tilde{d}_{j}$ taking values in the interval ${\bar{d}}_{j} \pm \varepsilon {\bar{d}}_{j}$, i.e., ${\bar{d}}_{j}(1 - \varepsilon ) \le \tilde{d}_{j} \le {\bar{d}}_{j}(1+\varepsilon )$ with $\varepsilon > 0$ and ${\bar{d}}_{j}$ corresponding to the nominal value of the uncertain parameter. We define the scenario space $U(\varepsilon )$ as follows:

$$\begin{aligned} U(\varepsilon ) = \left\{ \tilde{d}_{j} \in \mathbb {R}_+ : {\bar{d}}_{j} (1-\varepsilon ) \le \tilde{d}_{j} \le {\bar{d}}_{j} (1+\varepsilon ), \forall j \in N \right\} . \end{aligned}$$

Therefore, the scenario space is the uncertainty set within which the decision maker hypothesizes every realization of the uncertain parameter will occur. In addition, we assume that the uncertainty can affect the objective function of problem CFLP, as the cost vector $\mathbf{c}$ can be computed as a function of the uncertainty coefficients $d_{j}$.

One way of dealing with the uncertainty of the parameters of the problem is provided by Robust Optimization (RO) [6]. RO ensures that a robust solution $(\mathbf{y} , \mathbf{x}$) be feasible with respect to every realization of the robust parameters in the pre-specified interval defined by $\varepsilon$. However, while in certain applications it might be of paramount importance to guarantee feasibility of the robust solution 100% of the times (e.g., in medical applications, or some critical engineering applications), in most realms of application of robust optimization, e.g., in management, it is not necessary to produce a solution that hedges against every possible realization of the uncertain parameters in the scenario space, since full immunization comes at a high cost in terms of objective function value. Therefore, while recognizing the nature of the data in a support or uncertainty set U which defines the scenario space, to avoid being overly conservative and, therefore, to mitigate the adverse effect of full immunization on the objective function value, one might want to optimize over a smaller support ${\tilde{U}} \subseteq U$. The rationale is that, if ${\tilde{U}}$ is properly crafted, one might obtain important benefits in terms of costs while keeping the risk of incurring infeasible scenarios very low.

This strategy is of particular interest to the business community, where the fact that customer demand may vary does not typically have drastic repercussions as, for example, in medical or engineering applications. Therefore, in line with the reasoning put forth by Bertsimas and Sim [6], given a set of uncertain parameters taking values in U, the goal of a practitioner using a robust model could be to define a support ${\tilde{U}} \subseteq U$ and to find a robust solution such that (i) if nature selects a realization of the uncertain parameters from ${\tilde{U}}$, the solution is deterministically feasible, and (ii) if nature selects a realization of the parameters in $U {\setminus } {\tilde{U}}$, the probability of incurring an infeasible scenario is still very low. The next section motivates our study by means of an introductory example.

1.1 Motivation and introductory example

The work in this paper is also motivated by a real-world application from a major dairy company whose core business is the production and distribution of perishable products. Our study addresses a strategic problem of defining the partition of the customers to a set of depots under uncertain customer demands. We consider the following robust formulation of SS-CFLP:

$$\begin{aligned} \text {(R-SS-CFLP)} \min&\sum _{i \in M} f_i y_i + \max _{\mathbf {d} \in U(\varepsilon )}\sum _{i \in M} \sum _{j \in N}(d_j \overline{c}_{ij})x_{ij} \nonumber \\ \text{ s.t. } \quad&\sum _{j \in N} d_j x_{ij} \le s_iy_i, \quad \forall i \in M, \mathbf {d} \in U(\varepsilon ), \nonumber \\&(1), (4), x_{ij} \in \{0,1\}, \forall i \in M, j \in N, \end{aligned}$$

(5)

where $\mathbf {d} \in \mathbb {R}^n_+$, and $U(\varepsilon ) \subseteq \mathbb {R}^n_+$ denotes the support (box uncertainty set) at hand and $\overline{c}_{ij}$ denotes the unitary transportation cost for serving j from i. We then consider the following experimental setup.

• (i) Optimization over the support $U(\varepsilon )$. We solve the robust counterpart of formulation SS-CFLP (see Sect. 3) with box support $U(\varepsilon )$, with $\varepsilon \in \left\{ 0.05,0.1,0.15, 0.2, \ldots , 0.9\right\}$, and we obtain the corresponding robust solution $(\mathbf {y},\mathbf {x})_\varepsilon$ of cost $(z)_\varepsilon$. Clearly, we have $(z)_{\varepsilon ''} \ge (z)_{\varepsilon '}$ if $\varepsilon '' > \varepsilon '$.

• (ii) Evaluation over the scenario space $U({\hat{\varepsilon }})$. We define a family of nested scenarios spaces $U({\hat{\varepsilon }})$, with ${\hat{\varepsilon }} \in \left\{ 0.1, 0.2, \ldots , 0.9\right\}$, and for each ${\hat{\varepsilon }}$ we generate 1,000,000 realizations of coefficients $d_j$ and we evaluate, in terms of violation of constraints (5), the solutions $(\mathbf {y},\mathbf {x})_{\varepsilon }$.

Figure 1 presents the results of the aforementioned experiment on a SS-CFLP real-world instance. On the horizontal axis, we indicate the size of the support used for the optimization step ($\varepsilon$), and on the vertical axis we report the number of infeasible scenarios evaluated by using the robust solution $(\mathbf {y},\mathbf {x})_{\varepsilon }$ over the nested scenarios spaces (${\hat{\varepsilon }}$).

Fig. 1

R-SS-CFLP: example about the real-world instance A

In the figure, consider the pair of values $\varepsilon =0.45$ and $\varepsilon =0.5$, for the line given by ${\hat{\varepsilon }}=0.85$. We observe that the robust solution associated with the smaller support, i.e., $(\mathbf {y},\mathbf {x})_{0.45}$, is more robust than the solution associated with the larger uncertainty set, i.e., $(\mathbf {y},\mathbf {x})_{0.5}$. A similar behaviour can also be observed for other values of $\varepsilon$ and lines given by ${\hat{\varepsilon }}$. This empirical observation poses a problem when it comes to comparing and evaluating two robust solutions using the “price of robustness” [6] as a proxy: due to the fact that the monotonic behavior of the curve is not guaranteed, one cannot discriminate among alternative robust solutions by simply relying on the trade-off price-vs-robustness. As evinced from Fig. 1, a more expensive solution, obtained over a larger support, could be less robust than a cheaper solution, obtained over a smaller support. It is worth mentioning that, RO does not make a claim about the solution quality for instances outside of the support set, and therefore we are not identifying a potential fault of the RO framework, but we are rather highlighting that the monotonic behavior of the price of robustness is not guaranteed whenever the underlying uncertainty set is subject to a variation.

Contributions and paper organization Our distinct contributions in this paper are as follows: (i) it is the first time that a limitation/drawback associated with the price of robustness is identified for the CFLP: the monotonicity of the trade-off price-vs-robustness cannot be guaranteed a priori. Furthermore, we show that there always exists a situation in which a nominal solution can be more robust, and cheaper, than a robust solution, (ii) we conduct a computational study on both real-world and benchmark instances, to ascertain the significance of such phenomenon. Empirical evidence suggests that such phenomenon cannot be neglected by the decision maker, since it has a significant impact in terms of costs and reliability of the implemented solution.

The remainder of the paper is organized as follows. Section 2 reviews contributions related to the optimization problems addressed in this paper. The main results of this paper are given in Sect. 3, where the properties of nominal and robust solutions are investigated. Section 4 reports the computational studies, and conclusions are given in Sect. 5.

2 Literature review

RO has received a considerable increase of interest over the last decade. There exists a vast literature on this topic, and for a detailed introduction to robust optimization, we refer the reader to [5, 7], whereas for an overview of developments in robust optimization since 2007 the reader is referred to [12, 17], where the latter provides a review with a special focus on the application of robust optimization to operations management. More recent works on RO have developed solution frameworks to produce less conservative solutions such as two-stage RO and more general multi-stage RO, also known as robust adjustable [4].

When alternative robust solutions are compared, two prominent criteria have been proposed in the literature, the Pareto Robust Optimality criterion of [14] and the price of robustness of [6]. With respect to the former, the idea is to exploit the degeneracy of many RO models and select a Pareto-optimal solution, i.e., a solution that is optimal with respect to the worst-case scenario, and is not dominated by any other solution for all the possible scenarios of the uncertainty set. For example, if the uncertainty of the problem is in the objective function, a robust solution ${\mathbf {x}}^*$ is Pareto-optimal if the cost associated with the worst case realization of the uncertain parameter is minimal and, in addition, no other solution is cheaper that ${\mathbf {x}}^*$ for any realization of the uncertain parameter in the uncertainty set. Therefore, the Pareto-optimality criterion focuses on the selection of alternative robust solution within the same uncertainty set. On the other hand, the price of robustness is employed to discriminate among alternative robust solutions obtained using different uncertainty sets. Thus, it considers the trade-off between the size of ${\tilde{U}}$, and therefore the value of the objective function, and the probability of violation of the uncertain constraints (2) has been employed to select and discriminate among alternative robust solutions. More specifically, as mentioned, one would expect a monotonically non-decreasing behavior of the price of robustness curve with respect to the size of the support ${\tilde{U}}$. In other words, if we assume that the size of ${\tilde{U}}$ is proportional to the value of $\varepsilon$, then the trade-off captured by the price of robustness states that a larger values of $\varepsilon$ should lead to optimal solutions associated with an increase in the objective function value and a decrease in the probability of violation of constraints (2). Pareto-optimal solutions were also investigated by Chassein and Goerigk [8]. The authors considered linear programming problems with uncertain cost functions and presented a column generation approach that requires no direct solution of the computationally expensive worst-case problem.

It is worth pointing out that our study goes beyond the search of a Pareto Robust Optimal (PRO) solution, as done in [8, 14]. A PRO solution is defined as a minimum cost solution which provides the maximum slack of the robust constraint (e.g., unused capacity in a facility location problem) for every realization of the uncertain parameter in the uncertainty set. Our approach departs from that of [14] since (i) their analysis is based on the fact that the uncertainty sets used in the optimization and evaluation phases are the same. We want to explore whether the price-of-robustness framework holds when the uncertainty set used in the evaluation phase is decoupled from the one used in the evaluation phase; (ii) our analysis is not limited to PRO solutions, but we extend the analysis by comparing solutions in terms of expected values of constraints violation, and (iii) we compare alternative robust solutions obtained over different uncertainty sets extending the reasoning to other measures to capture the robustness of a solution, which goes beyond the slack measure proposed in [14].

Facility location problems find application in a number of realms, e.g., supply chain management, distribution system design and telecommunication network design, among others. Laporte et al. [15] and Melo et al. [19] present a comprehensive literature review of facility location models in the context of supply chain management.

Uncertain versions of the facility location problem consider different types of uncertainties (for instance, regarding demand, costs, and facility reliability), and mainly focus on the uncertainty of the demands. For example, Lodi et al. [16] investigated machine learning methods to address uncertainties in input parameters whereas McGarvey and Thorsen [18] considered uncertainty with respect to the number of future facilities required. Different methods have been proposed to deal with uncertainty, among them RO. For a comprehensive overview of robust facility location approaches we direct the interested reader to [9, 22] and references therein. A detailed review of facility location with uncertain parameters and their solution methods can also be found in Laporte et al. [15].

While the literature on the deterministic CFLP is vast, the robust version of the CFLP has not received much attention so far. Opher et al. [20] studied a variant of the multi-period CFLP in which the maximum capacity of each facility must be determined, and showed that the robust approach offers significant improvements when compared with the nominal solution. In a similar fashion, Gülpinar et al. [13] presented different robust models for the CFLP, with both known and ambiguous demand probability distribution function. Both papers ascertain the superiority of the robust solution over the deterministic one on an extensive set of benchmark instances. An et al. [1] investigated two-stage RO models for the reliable p-median facility location problem by considering two practical features, i.e., facility capacity and demand change due to site disruption. The authors designed an exact algorithm based on column-and-constraint generation and Bender decomposition methods, and solved to optimality instances with up to 49 sites. Zeng and Zhao [23] described a column-and-constraint generation algorithm to solve two-stage RO problems as an alternative to Benders-style cutting plane methods. The proposed solution framework was used to solve a two-stage robust location-transportation problem. Recently, Du et al. [11] have considered two-stage facility location problems in an uncertain and dynamic environment, aiming at building a network that serves demand in both general and disruptive situations. The paper compared a two-stage robust model and a two-stage stochastic model for the reliable p-center problem, and the experiments reported showed that the solutions produced by the two-stage robust model are not overly conservative.

3 Non-monotonicity of the price of robustness

In this section, we investigate properties of the nominal and robust solutions. We first show that, given an optimal robust solution over a box support $U(\varepsilon )$ (i.e., optimization scenario), it is possible to construct a scenario from an uncertainty set of size $U({\hat{\varepsilon }}) \supset U(\varepsilon )$ (i.e., evaluation scenario) for which the nominal solution remains feasible while the robust solution becomes infeasible.

Definition 1

A polyhedral support for the uncertain parameters $d_j$ is defined as $Q(\varepsilon )=\{ \mathbf{d} \ge 0: W \mathbf{d} \le \mathbf{h} (\varepsilon )\}$, where $W \in \mathbb {R}^{r\times n}$, and $\mathbf{h} (\varepsilon )\in \mathbb {R}^r$ is the parameter which controls the size of the support and, therefore, the degree of immunization of the robust solution.

The robust counterpart of CFLP can be derived by reformulating the semi-infinite constraints (5) as shown by the following theorem.

Theorem 1

[3] The robust counterpart of problem CFLP can be formulated as a the following MILP:

$$\begin{aligned} \text {(R-CFLP)} \quad \min \quad&\sum _{i\in M} f_i y_i + \sum _{i\in M} \sum _{j\in N} c_{ij} x_{ij} \\ \text{ s.t. } \quad&(1), (3), (4),\\&\sum _{t=1}^{r} h_{t} \psi _{it} \le s_iy_i,&\forall i \in M, \\&\sum _{t=1}^r w_{tj} \psi _{it} \ge x_{ij},&\forall j \in N, i \in M,\\&\psi _{i} \in \mathbb {R}^r_+,&\forall i \in M, \end{aligned}$$

where $w_{tj} \in W$ and $h_{t} \in {\mathbf {h}}$, with W and ${\mathbf {h}}$ specified as in Definition 1.

Let $(\mathbf{y} ^*,\mathbf{x} ^*)$ be an optimal solution to the nominal problem CFLP with nominal values ${\bar{d}}_{ij}$ and cost $z^*$. Moreover, let $(\mathbf{y} ,\mathbf{x} )_\varepsilon$ be an optimal solution to formulation R-CFLP over the box support $U(\varepsilon )$, $\varepsilon > 0$, of cost $(z)_{\varepsilon } > z^*$. The following theorem holds.

Theorem 2

If solution $(\mathbf{y} ,\mathbf{x} )_\varepsilon$ is evaluated over a scenario space $U({\hat{\varepsilon }})$ with ${\hat{\varepsilon }}> \varepsilon > 0$, there may exist a sample $[{\hat{d}}_{j}] \in U({\hat{\varepsilon }})$ such that the nominal solution $(\mathbf{y} ^*,\mathbf{x} ^*)$ is feasible whereas solution $(\mathbf{y} ,\mathbf{x} )_\varepsilon$ is infeasible.

Proof. The proof is by an example. Consider an instance where $m=2$ (i.e., $M=\{1,2\}$) and $n=3$ (i.e., $N=\{1,2,3\}$) with $X \subseteq \mathbb {R}^{2 \times 3}_+$, defined by the following parameters:

• ${\bar{d}}_1 = {\bar{d}}_2 = {\bar{d}}_3 = {\bar{d}}$; $f_1=f_2$;

• The cost matrix $[c_{ij}]$ is defined as follows: $\mathbf{c} = \left[ \begin{array}{ccc} c_{11} &{}\quad 0 &{}\quad B\\ c_{21} &{}\quad B &{}\quad 0 \end{array}\right]$ where $c_{11} < c_{21}$ and B is a large constant;

• $s_1 \ge 2{\bar{d}}$, $s_2 \ge 2{\bar{d}}$, $s_1 \ge {\bar{d}}(2+\varepsilon )$, $s_1 < 2{\bar{d}}(1+\varepsilon )$, $s_2 \ge {\bar{d}}(1+\varepsilon )$.

Then, the nominal solution $(\mathbf{y} ^*,\mathbf{x} ^*)$ is $\mathbf{y} ^*= \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad \mathbf{x} ^*= \left[ \begin{array}{ccc} 1 &{}\quad 1 &{}\quad 0\\ 0 &{}\quad 0 &{}\quad 1 \end{array}\right]$ while the robust solution $(\mathbf{y} ,\mathbf{x} )_\varepsilon$ depends on $\varepsilon$ and is $\mathbf{y} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad \mathbf{x} = \left[ \begin{array}{ccc} \frac{s_1-{\bar{d}}(1+\varepsilon )}{{\bar{d}}(1+\varepsilon )} &{}\quad 1 &{}\quad 0\\ 1-\alpha &{}\quad 0 &{}\quad 1 \end{array}\right]$ where the term $x_{11}=\alpha =\frac{s_1-{\bar{d}}(1+\varepsilon )}{{\bar{d}}(1+\varepsilon )} <1$. Clearly, $(z)_{\varepsilon } > z^*$.

Consider ${\hat{\varepsilon }}$ such that ${\hat{\varepsilon }} > \varepsilon$, then there exists a scenario $[{\hat{d}}_j] \in U({\hat{\varepsilon }})$ which makes the robust solution $(\mathbf{y} ,\mathbf{x} )_\varepsilon$ infeasible while the nominal solution $(\mathbf{y} ^*,\mathbf{x} ^*)$ remains feasible. Consider $[{\hat{d}}_{ij}] = \begin{bmatrix} {\bar{d}}(1+\delta )&{\bar{d}}(1-{\hat{\varepsilon }})&\end{bmatrix},$ with $0 \le \delta \le {\hat{\varepsilon }}$. Below, we aim to find a value of $\delta$ such that constraints (2) are satisfied by the nominal solution $\mathbf{x} ^*$ for the scenario $[{\hat{d}}_{j}]$, that is the constraints with $i=1,2$ are satisfied by solution $\mathbf{x} ^*$:

$$\begin{aligned} {\left\{ \begin{array}{ll} x^*_{11}{\bar{d}}(1+\delta ) + x^*_{12}{\bar{d}}(1-{\hat{\varepsilon }}) \le s_1 &{} \qquad (a)\\ x^*_{23}{\bar{d}}(1+{\hat{\varepsilon }}) \le s_2,&{} \qquad (b) \end{array}\right. } \end{aligned}$$

(6)

whereas the constraint (2) with $i=2$ is violated by solution $\mathbf{x}$, i.e., $x_{21} {\bar{d}}(1+\delta ) + x_{23}{\bar{d}}(1+{\hat{\varepsilon }}) > s_2,$ or, equivalently,

$$\begin{aligned} {\left\{ \begin{array}{ll} {\bar{d}}(1+\delta ) + {\bar{d}}(1-{\hat{\varepsilon }}) \le s_1,\\ {\bar{d}}(1+{\hat{\varepsilon }}) \le s_2, \\ (1-\frac{s_1 -{\bar{d}}(1+\varepsilon )}{{\bar{d}}(1+\varepsilon )}){\bar{d}}(1+\delta ) + {\bar{d}}(1+{\hat{\varepsilon }}) > s_2, \end{array}\right. } \end{aligned}$$

(7)

which implies ${\hat{\varepsilon }} \le \frac{s_2-{\bar{d}}}{{\bar{d}}}$, and $\max \{0,\delta _L\} < \delta \le \min \{{\hat{\varepsilon }},\delta _U\}$ with $\delta _U= \frac{s_1 - {\bar{d}}(1-{\hat{\varepsilon }})}{{\bar{d}}}-1$ and $\delta _L= \frac{s_2 - {\bar{d}}(1+{\hat{\varepsilon }})}{2{\bar{d}}(1+\varepsilon ) - s_1}(1+\varepsilon ) - 1$.

Note that if constraint (a) (case $i=1$) of inequalities (6) is satisfied, then also constraint $x_{11}{\bar{d}}(1+\delta ) + x_{12}{\bar{d}}(1-{\hat{\varepsilon }}) \le s_1$ is satisfied by any $\mathbf{x}$ solution since $x_{12}=x^*_{12}$ and $x_{13}=0$ and $x_{11} < 1$.

Since $s_1 \ge 2{\bar{d}}$, we have $s_1-{\bar{d}}(1-{\hat{\varepsilon }}) > {\bar{d}}$, hence $\delta _U > 0$. Sufficient conditions for the existence of a set of values of $\delta$ such that the statement of the theorem is verified are:

$$\begin{aligned} {\left\{ \begin{array}{ll} s_1 - {\bar{d}}(1-{\hat{\varepsilon }}) \ge \left[ s_2 - {\bar{d}}(1+{\hat{\varepsilon }})\right] (1+\varepsilon ) \\ {\bar{d}} \le 2{\bar{d}}(1+\varepsilon ) - s_1 \end{array}\right. }, \end{aligned}$$

(8)

which lead to $\varepsilon \ge \frac{s_1-{\bar{d}}}{2{\bar{d}}}$, ${\hat{\varepsilon }} > \varepsilon$, ${\hat{\varepsilon }} \le \frac{s_2-{\bar{d}}}{{\bar{d}}}$, and ${\hat{\varepsilon }} \ge \frac{s_2(1+\varepsilon ) - {\bar{d}}\varepsilon -s_1}{{\bar{d}}(2+\varepsilon )}$.

The choice of values of $\varepsilon$ and ${\hat{\varepsilon }}$ in the halfspaces derived above guarantees that $\delta _L \le \delta _U$. Thus, a suitable value of $\delta$ exists. $\Box$

Fig. 2

Representation of Theorem 3

As previously stated, consider a nominal optimal solution $(\mathbf{y} ^*,\mathbf{x} ^*)$ and an optimal solution $(\mathbf{y} ',\mathbf{x} ')_{\varepsilon '}$ to R-CFLP over the box support $U(\varepsilon ')$ with cost $(z')_{\varepsilon '} > z^*$. In the following, we show that by optimizing R-CFLP on a larger support $U(\varepsilon '')$ (with $\varepsilon '' > \varepsilon '$) does not necessarily provide a solution which is more robust than the solution associated with $U(\varepsilon ')$, if the solutions are evaluated over a scenario space $U({\hat{\varepsilon }})$, with $U({\hat{\varepsilon }}) \supset U(\varepsilon '') \supset U(\varepsilon ')$. Indeed, the following theorem holds.

Theorem 3

Let $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$ be an optimal robust solution of $R-CFLP$ over the box support $U(\varepsilon '')$, with $\varepsilon '' > \varepsilon '$. If solution $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$ is evaluated over a scenario space $U({\hat{\varepsilon }})$ with $U({\hat{\varepsilon }}) \supset U(\varepsilon '') \supset U(\varepsilon ')$, and the uncertain parameters $d_{j}$ are uniformly distributed in $U({\hat{\varepsilon }})$, then the violation probability of solution $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$ can be strictly greater than the violation probability of solution $(\mathbf{y} ',\mathbf{x} ')_{\varepsilon '}$ and the ratio between solution costs $(z')_{\varepsilon '}$ and $(z'')_{\varepsilon ''}$ can be arbitrarily small.

Proof. The proof is by an example. Consider an instance where $m=3$ (i.e., $M=\{1,2,3\}$) and $n=2$ (i.e., $N=\{1,2\}$) with $X \subseteq \mathbb {R}^{2 \times 3}_+$, defined by the following parameters:

• The nominal values are ${\bar{d}}_1=\frac{3}{2}$ and ${\bar{d}}_2=\frac{3}{2}$;

• The cost matrix $[c_{ij}]$ is defined as follows: $\mathbf{c} = \left[ \begin{array}{cc} c_{11} &{}\quad c_{12}\\ c_{21} &{}\quad c_{22}\\ B &{}\quad c_{32} \end{array}\right]$ where $c_{11}=c_{12}$, $c_{21}=c_{22}$, $c_{11} < c_{21}$, $c_{12} < c_{22}$, $c_{32}<c_{22}$, $c_{12} < c_{32}+f_3$ and B is a large constant;

• The capacities of the facilities are $s_1=s_2=s_3=3$.

The nominal solution $(\mathbf{y} ^*,\mathbf{x} ^*)$ is $\mathbf{y} ^*= \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \quad \mathbf{x} ^*= \left[ \begin{array}{cc} 1 &{}\quad 1 \\ 0 &{}\quad 0 \\ 0 &{}\quad 0 \\ \end{array}\right] .$ Consider $\varepsilon '=1$; then the robust optimal solution $(\mathbf{y} ',\mathbf{x} ')_{\varepsilon '}$ is $\mathbf{y} ' = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \quad \mathbf{x} ' = \left[ \begin{array}{ccc} \frac{1}{2} &{}\quad \frac{1}{2} \\ \frac{1}{2} &{}\quad \frac{1}{2} \\ 0 &{}\quad 0 \end{array}\right] .$ Clearly, $(z')_{\varepsilon '} > z^*$.

Consider now a value $\varepsilon '' > \varepsilon '$, with $\varepsilon ''=\frac{4}{3}$; we have $U(\varepsilon '') \supset U(\varepsilon ')$. For the support $U(\varepsilon '')$, a corresponding optimal solution $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$ is $\mathbf{y} '' = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \quad {} \mathbf{x} '' = \left[ \begin{array}{ccc} \frac{6}{7} &{}\quad 0 \\ \frac{1}{7} &{}\quad \frac{1}{7} \\ 0 &{}\quad \frac{6}{7} \end{array}\right] .$ Let $(z'')_{\varepsilon ''}$ be the cost of solution $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$. We have $(z'')_{\varepsilon ''}> (z')_{\varepsilon '} > z^*$. Note that, if $f_3 \gg f_2$, the ratio between solution costs $(z')_{\varepsilon '}$ and $(z'')_{\varepsilon ''}$ can be arbitrarily small.

For solution $(\mathbf{y} ',\mathbf{x} ')_{\varepsilon '}$ constraints (2) for $i=1,2$ correspond to: $\frac{1}{2}d_1 + \frac{1}{2}d_2 \le 3$, whereas the constraint for $i=3$ is redundant. For solution $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$ constraints (2) are as follows:

$$\begin{aligned} i=1: \frac{6}{7}d_1 \le 3; i=2: \frac{1}{7}d_1 + \frac{1}{7}d_2\le 3; i=3: \frac{6}{7}d_2 \le 3, \end{aligned}$$

(9)

where the constraint for $i=2$ is dominated by the constraints for $i=1,3$. Figure 2 illustrates the different regions corresponding to the above inequalities. Consider a value ${\hat{\varepsilon }} > \varepsilon ''$, such that $U({\hat{\varepsilon }}) \supset U(\varepsilon '') \supset U(\varepsilon ')$, with ${\hat{\varepsilon }}=\frac{5}{3}$. Assuming that the uncertain parameters $d_{j}$ are uniformly distributed in the box $U({\hat{\varepsilon }})$, the probability that solution $(\mathbf{y} ',\mathbf{x} ')_{\varepsilon '}$ is not feasible can be computed as:

(10)

where Vol(S) denotes the volume of region S (see also Fig. 2), whereas the probability that solution $(\mathbf{y} '',\mathbf{x} '')_{\varepsilon ''}$ is not feasible can be computed as:

(11)

We therefore have $P_{infeas}(\mathbf{y} ',\mathbf{x} ') < P_{infeas}(\mathbf{y} '',\mathbf{x} '')$, thus the probability of violation of a supposedly more robust solution can be higher than the probability of the less robust solution. $\Box$

The counter-intuitive behavior showed in this section leads to less expensive solutions obtained by considering a specified uncertainty set that are more robust than more expensive solutions obtained by considering a larger uncertainty set. In the following section we investigate how often this behaviour happens in practice.

4 Computational study

In this section we introduce a set of indicators created ad-hoc to measure the incidence of the non-monotonicity of the price of robustness in practice. The computational results are presented on two classes of instances: real-world instances and instances taken from widely used benchmarks from the literature.

The models presented are implemented in C++ using IBM ILOG CPLEX 12.8.0 as MILP solver. All experiments are executed on a single core of an Intel Xeon E5-4620 at 2.2 GHz with 4 GB of available memory. All the instances from the literature are solved to optimality within 1 h. A total of 102 out of 160 real-world instances are solved to optimality, for the remaining 58 real-world instance we consider the best feasible solution obtained within a time limit of 24 h.

4.1 Indicators

In this section we introduce the indicators used to evaluate the inversion of monotonicity for a given instance. Given an instance of a class of problems, and two sets within which $\varepsilon$ and ${\hat{\varepsilon }}$ can vary, we are interested in measuring how often the inversion of monotonicity occurs.

Let inst be a deterministic instance and $\texttt {inst}_{\varepsilon }$ be the robust counterparts obtained with a box support with a given value of $\varepsilon >0$. We call $(\mathbf {y}^*,\mathbf {x}^*)$, $(\mathbf {y}^*,\mathbf {x}^*)_{\varepsilon }$ the associated optimal solutions and with $z^*$ and $(z^*)_{\varepsilon }$ their corresponding optimal values.

We measure the robustness of a solution $(\mathbf {y}, \mathbf {x})$ with respect to a given scenario $\mathbf{d} \in U({\hat{\varepsilon }})$ with the basic binary indicator FV that is equal to one if the solution $(\mathbf {y},\mathbf {x})$ is not feasible for the given scenario $\mathbf{d}$.

Let ${\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} (FV((\mathbf {y}^*,\mathbf {x}^*),\mathbf{d} ))$ be the average value of the indicator FV, for a given solution $(\mathbf {y}^*,\mathbf {x}^*)$ and scenario space $U({\hat{\varepsilon }})$. To compute an approximate estimate of ${\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})}$, we use a sampling/Montecarlo simulation. Let $n_s$ be the number of samples, we have: ${\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} (FV((\mathbf {y}^*,\mathbf {x}^*),\mathbf{d} )) \approx \frac{\sum _{i=1}^{n_s} FV((\mathbf {y}^*,\mathbf {x}^*),\mathbf{d} _i)}{n_s}$ with $\mathbf{d} _i$ uniformly generated in $U({\hat{\varepsilon }})$.¹ In the rest of this section, we exemplify the use of the indicator on the real-world instance A, for which all the associated problems where solved to optimality by the MIP solver within the imposed time limit.

As a first step, we solve the deterministic version ($\varepsilon =0$) and the robust versions of the instance with box supports with $\varepsilon$ ranging from 0.05 up to 0.9 with step 0.05. Next, for each solution $(\mathbf {y}^*,\mathbf {x}^*)$, we calculate ${\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} (FV((\mathbf {y}^*,\mathbf {x}^*),\mathbf{d} ))$ with ${\hat{\varepsilon }}$ also ranging from 0.05 up to 1.0. Each solution is evaluated by generating $n_s=10^6$ scenarios.

Table 1 A instance, box support, FV values (in percentage)

Table 1 reports under column “of” the normalized value of the objective function (in percentage), the average values of FV for each combination of solution and $U({\hat{\varepsilon }})$ used to generate the scenarios $\mathbf{d}$. For example, the fist row of Table 1 reports the values corresponding to $(\mathbf {y}^*,\mathbf {x}^*)$, the deterministic solution, while the second row reports the values relative to $(\mathbf {y}^*,\mathbf {x}^*)_{0.05}$, and so on, until the last row, with the values related to $(\mathbf {y}^*,\mathbf {x}^*)_{0.9}$. Note that for compactness, the values of FV are reported in percentage. From the first row, we observe that ${\mathbb {E}}_\mathbf{d \in U(0.05)} (FV((\mathbf {y}^*,\mathbf {x}^*),\mathbf{d} ))=42.78\%$, the percentage of infeasibility increases along the line, up to a value of ${\mathbb {E}}_\mathbf{d \in U(1)} (FV((\mathbf {y}^*,\mathbf {x}^*),\mathbf{d} ))=86.28\%$, obtained when we consider scenarios generated with ${\hat{\varepsilon }}=1.0$.

Under the price of robustness framework, each column, read from top to bottom, should report non-increasing values since, for increasing values of $\varepsilon$, i.e., the size of the uncertainty set used in the optimization phase, while keeping ${\hat{\varepsilon }}$ (the size of the evaluation space) constant, one would expect to obtain more robust, albeit more expensive -see column ‘of’- solutions. In other words, FV should be monotonically non-increasing columnwise. More formally, if $\varepsilon ' \le \varepsilon '' \le {\hat{\varepsilon }}$ we would expect to have ${\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }} )} (FV((\mathbf {y}^*,\mathbf {x}^*)_{\varepsilon ''},\mathbf{d} )) \le {\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} (FV((\mathbf {y}^*,\mathbf {x}^*)_{\varepsilon '},\mathbf{d} ))$. However, this is not always the case. If we consider again Table 1, we observe the following values:

$$\begin{aligned} {\mathbb {E}}_\mathbf{d \in U(0.9)} (FV((\mathbf {y}^*,\mathbf {x}^*)_{0.45},\mathbf{d} )) =0.83\%\; {\mathbb {E}}_\mathbf{d \in U(0.9)} (FV((\mathbf {y}^*,\mathbf {x}^*)_{0.5},\mathbf{d} ))=1.15\%\;. \end{aligned}$$

The values indicate that, if we consider the scenarios from $U({\hat{\varepsilon }})$ with ${\hat{\varepsilon }}=0.9$, the solution obtained with a smaller support is infeasible significantly less than the solution obtained with a supposedly more robust support.

To summarize the overall behaviour of Table 1, we introduce the following two derived indicators, based on FV:

• The number of variations n(FV):

  $$\begin{aligned} n(FV)= \sum _{{\hat{\varepsilon }}=0.05}^{1} \sum _{\varepsilon =0.05}^{1} \mathbb {1}_{\left\{ {\mathbb {E}}_\mathbf{d \in U\left( {\hat{\varepsilon }}\right) } \left[ FV\left( \left( \mathbf {y},\mathbf {x}\right) _{\varepsilon },\mathbf{d} \right) \right] > {\mathbb {E}}_\mathbf{d \in U\left( {\hat{\varepsilon }}\right) } \left[ FV\left( \left( \mathbf {y},\mathbf {x}\right) _{\varepsilon -0.05},\mathbf{d} \right) \right] \right\} }\;. \end{aligned}$$

  (12)

  Value n(FV) counts the number of inversions of monotonicity in the price of robustness with respect to the indicator FV. The twelve entries when it happens are reported in bold in Table 1.

• The average variation $avg(FV)=\alpha /n(FV)$, where $\alpha$ is computed as:

  $$\begin{aligned} \begin{aligned} \displaystyle \sum _{{\hat{\varepsilon }}=0.05}^{1} \sum _{\varepsilon =0.05}^{1} \max \left\{ 0, {\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} \left[ FV((\mathbf {y}^*,\mathbf {x}^*)_{\varepsilon },\mathbf{d} )\right] \right. \\\left. -{\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} \left[ FV((\mathbf {y}^*,\mathbf {x}^*)_{\varepsilon -0.05},\mathbf{d} )\right] \right\} . \end{aligned} \end{aligned}$$

  Value avg(FV) is the average of the difference between the value of one entry of the table and the value of the entry above, when such a difference is positive.

With respect to Table 1, we obtain the following two derived indicators, $n(FV) = 12$ out of 189 potential cases and $avg(FV) = 0.218$. We have therefore 12 cases where the monotonicity of the price of robustness is not respected, and the average increase in the number of infeasible scenarios for such cases is $0.218\%$. Finally, it is important to analyze the change in the objective function value when the monotonicity of the price of robustness is not respected. Let us indicate with: $\delta _z^* = 100.0 \, \dfrac{(z^*)_{\varepsilon }-(z^*)_{\varepsilon -0.05}}{(z^*)_{\varepsilon }}$ the gap, in percentage, of the objective function values when comparing two robust solutions obtained over two “adjacent” support sets, i.e., robust solutions obtained over the support sets defined by $\varepsilon -0.05$ and $\varepsilon$. We thus define the average objective function loss as:

$$\begin{aligned} ofl(FV)= \dfrac{\displaystyle \sum \nolimits _{{\hat{\varepsilon }}=0.05}^{1}\sum \nolimits _{\varepsilon =0.05}^{1} \mathbb {1}_{ \left\{ {\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} \left[ FV\left( \left( \mathbf {y}^*,\mathbf {x}^*\right) _{\varepsilon },\mathbf{d} \right) \right] > {\mathbb {E}}_\mathbf{d \in U({\hat{\varepsilon }})} \left[ FV\left( \left( \mathbf {y}^*,\mathbf {x}^*\right) _{\varepsilon -0.05},\mathbf{d} \right) \right] \right\} }\delta ^*_z }{n(FV)}, \end{aligned}$$

i.e., ofl(FV) indicates the average increase in the objective function when the value of FV of an entry is strictly greater than the value of the entry above it.

With respect to the example, the value of ofl(FV) is $1.69\%$, i.e, if we only consider the 12 cases where the monotonicity of the price of robustness is not respected, the average increase in the objective function is almost $2\%$.

4.2 Results on real-world instances

The data of the real-world instances were prepared and provided by the dairy company that motivated our study. Four different distributions centres (denoted as A, B, C, and D) corresponding to the distribution areas of four regions were selected by the company for the computational study. The customer demands were estimated based on representative historical data, and are computed as a function of the different products delivered to the customers. The locations of the potential facilities and the corresponding capacities were defined based on the existing infrastructures. In this context, the aim of the company is to investigate scenarios where the main goal is to minimize the number of facilities used, followed by the minimization of the transportation costs, i.e., fixed costs $f_i$ are assumed to be equal to a large positive constant. The number of facilities for the four instances is equal to 10, the number of customers varies from 157 to 197 and the minimum number of facilities is either 5 or 6.

In Table 2 we report the aggregated values of the indicators for the real-world SS-CFLP instances, where for each instance the value of indicator n(FV) is out of 189 potential cases.

The values reported clearly evince that the phenomenon cannot be neglected. It is interesting to mention that for instances A, C and D, a positive value of ofl(FV) is due to an increase of the transportation cost (i.e., the term of the objective function relative to the ${\mathbf {x}}$ variables), while for the instance B, the positive value of ofl(FV) is also due to an increase of the fixed cost (i.e., the number of facilities accounted for by the ${\mathbf {y}}$ variables).

Table 2 Real-world instances

4.3 Results on the capacitated facility location problem (CFLP)

We use as CFLP instances a subset of the MS-CFLP instances proposed by [2] and available at http://people.brunel.ac.uk/~mastjjb/jeb/info.html. The original instances have a name of the form xy, where x gives information about the graph and the number of commodities, while y gives information about the cost structure. Table 3 reports the properties of the instances studied. The fixed cost proportion computed as $(\max _{i \in M}f_i) / (\sum _{i \in M}\sum _{j \in M}c_{ij}/(|M||N|))$, representing the relative importance of the fixed costs with respect to the variable costs. To obtain instances with controlled capacity tightness we modified the original xy instances by increasing the capacities values and obtaining z-xy instances, where z indicates the capacity of each facility. The total number of SS-CFLP instances is 48, each of them tested with a box supports with $\varepsilon$ ranging from 0 to 1 with a step equal to 0.05. Therefore, we solved a total of 48 nominal problems and $48\times 20 = 960$ robust problems.

Table 3 CFLP: z-xy instance description

Table 4 SS-CFLP instances

In Table 4 we report the aggregated values of the indicators n(FV), avg(FV), ofl(FV) for the SS-CFLP. Note that the values reported in the tables are fractional, since they are obtained as average values. The values reported in the row labeled 12.x1 are obtained as the average values of the following six values: 12.6, 12.7, 12.9, 12.10, 12.12, 12.13, where each of them represents a combination of facility capacity and number of customers as reported in Table 3. Looking at the table, the values of the indicators are often non-negligible, confirming that the inversion of the monotonicity of the price of robustness is not an isolated phenomenon. The table shows that increasing the y parameter (the fixed cost proportion) from 1 to 4 has a non-negligible impact.

5 Conclusions

We showed that, for the Capacitated Facility Location Problem (CFLP) with uncertain demand, the framework of the price of robustness might fail to capture the actual relation between price and robustness of a set of optimal solutions. More specifically, via both theoretical and empirical results, we evinced that (i) it is possible to find a scenario (a realization of the uncertain parameters brought about by nature) for which the nominal solution is cheaper and more robust than a solution obtained over a non-empty support set; (ii) an optimal solution obtained over a smaller support set might be cheaper and more robust than a solution obtained over a larger support set; (iii) this type of behavior, when exists, holds for a wide interval of realizations of the uncertain parameters, thus showing that the non-monotonicity of the price of robustness is not just a statistical fluke.