Upper Bound for the Competitive Facility Location Problem with Quantile Criterion

Abstract

In this paper, we consider a competitive location problem in a form of Stackelberg game. Two parties open facilities with the goal to capture customers and maximize own profits. One of the parties, called Leader, opens facilities first. The set of customers is specified after Leader’s turn with random realization of one of possible scenarios. Leader’s goal is to maximize the profit guaranteed with given probability or reliability level provided that the second party, called Follower, acts rationally in each of the scenarios. We suggest an estimating problem to obtain an upper bound for Leader’s objective function and compare the performance of estimating problem reformulations experimentally.

1 Introduction

We deal with a bilevel location model firstly suggested in [7] as a deterministic reformulation of a stochastic competitive location problem. In this problem, two competing parties open their facilities in a finite discrete space with the goal to maximize their profits, i.e. the value of income from customers service minus the fixed costs of facilities opening. A decision making process is organized as a Stackelberg game [10]. One of the parties, called Leader, opens its facilities first.

It is assumed that the set of customers is unknown for Leader. Instead of this Leader is provided with a finite set of possible scenarios. Each scenario has known probability of realization and fully characterizes the set of customers.

After Leader opens facilities one of possible scenarios is realized and the set of customers becomes specified. This information is available for the second party called Follower, who opens own facilities with the goal to maximize profit as well.

In the model under consideration, each customer chooses the party to be served by according to his preferences. The facility assigned to serve the customer must be more preferable for him than any competitor’s facility. This model of customers serving in competitive environment is referred to in [3] as a free choice of supplier rule. In the present paper we study a multi–scenario generalization of the problem in [3].

Leader’s goal in this situation is to maximize profit that can be guaranteed with given probability or reliability level. In other words, Leader selects a set of facilities to be opened such that there exists a subset of scenarios with total probability not less than the reliability level. In these scenarios, Leader gets a profit, which is not less than a certain value, and the goal is to make this value as big as possible. The scenarios participating in the calculation of guaranteed income are further referred to as active scenarios.

In [7] the value of income the customer brings to the facility is the same for all facilities. This assumption allows the authors to suggest upper and lower bounds for an optimum of the Leader’s problem. In the case when the income depends on serving facility, the suggested upper bound is not valid. By using the technique from [3] we formulate an estimating problem in the form of MIP providing an upper bound in the case of facility–dependent income values. We suggest two reformulations of the estimating problem and perform numerical experiments to compare their efficiencies.

The rest of the paper is organized as follows. In Sect. 2 we present a mathematical model of the competitive facility location problem with quantile criterion (QCompFLP) in the form of a pessimistic bilevel mixed–integer programming problem [5] and discuss a concept of its pessimistic feasible solution. Also, we suggest a procedure to compute a pessimistic feasible solution for given values of Leader’s location variables. Section 3 provides a formulation of the estimating problem for upper bound calculation. Two reformulations of it are presented as well. In Sect. 4 we compare the effectiveness of suggested formulations of the estimating problem and examine their qualities as providers of an upper bound for QCompFLP.

2 Mathematical Model

Let us introduce the necessary notations:

Sets:

$I=\{1,\ldots ,m\}$ is a set of facilities or candidate sites for opening a facility;

$S=\{1,\dots ,l\}$ is a set of possible scenarios;

$J_s$ is a finite set of customers in case when scenario $s\in S$ is realized. We assume that $J_{s_1}\cap J_{s_2}=\emptyset$ for each $s_1,s_2\in S$, $s_1\ne s_2$. The set of all possible customers is denoted with $J = \bigcup _{s\in S} J_s$. Without loss of generality we assume that $J=\{1,\ldots ,n\}$.

Parameters:

$f_i$ is a fixed cost of opening Leader’s facility $i\in I$;

$g_i$ is a fixed cost of opening Follower’s facility $i\in I$;

$c_{ij}$ is an income of Leader’s facility $i\in I$ from customer $j\in J$;

$d_{ij}$ is an income of Follower’s facility $i\in I$ from customer $j\in J$;

$p_s$ is a probability of realization of scenario $s\in S$;

$p_0$ is a reliability level.

Variables:

$x_i = \left\{ \begin{array}{l} 1, \text { if Leader opens facility }\,i\\ 0, \text{ otherwise, } \end{array}\right.$

$x_{ij} = \left\{ \begin{array}{l} 1, \text { if Leader's facility}\, i \,\text {is assigned to serve customer }\,j\\ 0, \text{ otherwise, } \end{array}\right.$

$z^s_i = \left\{ \begin{array}{l} 1, \text { if Follower opens facility }\,i\, \text {in the case of scenario }\,s\, \text {realization}\\ 0, \text{ otherwise, } \end{array}\right.$

$z_{ij} = \left\{ \begin{array}{l} 1, \text { if Follower's facility }\,i\, \text {is assigned to serve customer }\,j\\ 0, \text{ otherwise, } \end{array}\right.$

$\delta _s = \left\{ \begin{array}{l} 1, \text { if scenario }\,s\, \text {is active}\\ 0, \text{ otherwise, } \end{array}\right.$

C stands for the value of guaranteed income.

In the QCompFLP model we use a binary customer patronizing rule [9]. It means that each customer $j\in J$ brings income to a single facility opened by either Leader or Follower. We assume that this facility is chosen according to the preferences of the customer. The preferences are represented with linear order $\succeq _j$ on the set I. Given $i_1$, $i_2\in I$, the relation $i_1 \succeq _j i_2$ means that $i_1$ is not less preferable for j than $i_2$. If $i_1\ne i_2$ then $i_1$ is strictly more preferable than $i_2$, and we denote it with $i_1 \succ _j i_2$. For a nonempty set $I_0 \subseteq I$ we denote with $i_j(I_0)$ such an element of $I_0$, for which $i_j(I_0)\succeq _j k$ for all $k\in I_0$. For a nonzero (0,1)–vector $v = (v_i), i\in I$ we use notation $i_j(v)$ for an element $i_j(\{k\in I|v_k = 1\})$.

If we are given with boolean vectors x and z of Leader’s and Follower’s location variables values respectively, then Leader’s facility $i\in I$ can serve a customer $j\in J$ iff $i \succ _j i_j(z)$. Similarly, Follower’s facility $i\in I$ can serve a customer $j\in J$ iff $i \succ _j i_j(x)$.

Using introduced notations the mathematical model of the QCompFLP is written as the following pessimistic bilevel program:

$$\begin{aligned} \max _{(x_i),(x_{ij}),(\delta _s), C}\,\min _{(\tilde{z}^s_i), (\tilde{z}_{ij})}\left( -\sum _{i\in I}f_ix_i + C\right) , \end{aligned}$$

(1)

$$\begin{aligned} x_i \ge x_{ij}, \quad i\in I, \quad j\in J; \end{aligned}$$

(2)

$$\begin{aligned} \sum _{i\in I}x_{ij} \le \delta _s,\quad s\in S, \quad j\in J_s; \end{aligned}$$

(3)

$$\begin{aligned} C \le \sum _{i\in I}\sum _{j\in J_s} c_{ij}x_{ij} + M(1-\delta _s), \quad s\in S; \end{aligned}$$

(4)

$$\begin{aligned} \tilde{z}^s_i + \sum _{k\in I| i\succ _j k}x_{kj} \le 1, \quad s\in S, j\in J_s; \end{aligned}$$

(5)

$$\begin{aligned} \sum _{s\in S} p_s\delta _s\ge p_0; \end{aligned}$$

(6)

$$\begin{aligned} x_i, \delta _s \in \{0,1\}; 0\le x_{ij}\le 1, \quad i\in I, j\in J, s\in S; \end{aligned}$$

(7)

$$\begin{aligned} \text {where }(\tilde{z}^s_i), (\tilde{z}_{ij})\, \text {solves} \end{aligned}$$

(8)

$$\begin{aligned} \max _{(z^s_i),(z_{ij})}\sum _{s\in S}\left( -\sum _{i\in I}g_iz^s_i + \sum _{i\in I}\sum _{j\in J_s}d_{ij}z_{ij}\right) , \end{aligned}$$

(9)

$$\begin{aligned} z^s_i \ge z_{ij}, \quad i\in I, s\in S, j\in J_s; \end{aligned}$$

(10)

$$\begin{aligned} x_i + \sum _{k\in I| i\succeq _j k}z_{kj} \le 1, \quad j\in J; \end{aligned}$$

(11)

$$\begin{aligned} x_i + z_i^s \le 1, \quad i\in I, s\in S; \end{aligned}$$

(12)

$$\begin{aligned} z^s_i,\in \{0,1\}; 0\le z_{ij}\le 1, \quad i\in I, j\in J, s\in S. \end{aligned}$$

(13)

The objective function (1) of the upper–level problem represents the value of income, which is guaranteed with a probability $p_0$ reduced by the cost of opened facilities. Inequalities (2) forbid to serve customers with close facilities, (3) guarantee that customers from active scenarios cannot be served with more than one facility, (5) ensure that the customer is served with a facility which is more preferable than any of competitor’s ones. Constraints (4) provide that the value of guaranteed income is not greater than the income realized in any of active scenarios. The term with a sufficiently large constant M excludes inactive scenarios from the consideration. Constraints (6) impose that the income value is guaranteed with probability $p_0$.

The lower–level objective function (9) is a sum of profits Follower obtains in all possible scenarios. Its maximization is equivalent to maximization of the profit for each scenario separately. The constraints (10) and (11) have the same meaning as the upper–level constraints (2) and (5), respectively. Finally, the inequalities (12) provide that Follower does not open facility in the place occupied by Leader.

For brevity let us denote the vector of values of $x_i$, $i\in I$ and $z_i^s$, $i\in I$, $s\in S$ with x and z correspondingly. Given x we denote the problem $\mathcal {F}$ with $\mathcal {F}(x)$. Analogously, the problem $\mathcal {L}$ with the value of z in the constraints (5) is denoted with $\mathcal {L}(z)$. A whole model (1)–(13) is referred to as $(\mathcal {L},\mathcal {F})$.

2.1 Pessimistic Feasible Solutions of the Problem $(\mathcal {L},\mathcal {F})$

Consider some (0,1)–vector $x = (x_i)$, $i\in I$ and a quadruple $\chi (x) = (X, \varDelta , C, Z)$, where $X = \left( (x_i), (x_{ij})\right)$, $\varDelta = (\delta _s)$, $Z = \left( (z^s_i), (z_{ij})\right)$, $i\in I$, $j\in J$, $s\in S$. We call quadruple $\chi (x)$ a feasible solution of the problem $(\mathcal {L}, \mathcal {F})$ if Z is an optimal solution of the problem $\mathcal {F}(x)$ and $(X, \varDelta , C)$ is a feasible solution of the problem $\mathcal {L}(z)$, where $z = (z^s_i)$, $i\in I$, $s\in S$.

Let Opt(x) be a set of optimal solutions of the problem $\mathcal {F}(x)$. Given $Z\in Opt(x)$, let $\chi (x,Z)$ denote a quadruple $(X(Z), \varDelta (Z), C(Z), Z)$, where (X(Z), $\varDelta (Z)$, C(Z)) is an optimal solution of the problem $\mathcal {L}(z)$. We denote the value of objective function (1) on this solution with $L(\chi (x,Z))$. The solution $\chi (x,\check{Z})$ is called a pessimistic feasible solution of the problem $(\mathcal {L},\mathcal {F})$ if $L(\chi (x,\check{Z})) \le L(\chi (x,Z))$ for all $Z\in Opt(x)$. The problem $(\mathcal {L}, \mathcal {F})$ is equivalent to the problem of maximization of some implicitly given function such that $\check{f}(x) = L(\chi (x,\check{Z}))$ for each (0,1)–vector x.

The value $\check{f}(x)$ for a given x can be computed in two steps. At the first step the problem $\mathcal {F}(x)$ is solved, and let $F^*$ be its optimum. At the second step an auxiliary MIP provides a pessimistic feasible solution and a value of $\check{f}(x)$. To formulate it we introduce new nonnegative variables $u_j$, $j\in J$. Variable $u_j$ takes the value equals to Leader’s income from the customer j.

$$\begin{aligned} \min _{(z^s_i),(z_{ij}),(u_j)}\sum _{j\in J}u_j \end{aligned}$$

(14)

$$\begin{aligned} x_i+\sum _{k\mid i\succeq _jk}z_{kj}\le 1, \quad i\in I, \quad j\in J; \end{aligned}$$

(15)

$$\begin{aligned} z^s_i\ge z_{ij}, \quad i\in I, s\in S, j\in J_s; \end{aligned}$$

(16)

$$\begin{aligned} u_j\ge c_{ij}\Big (x_i-\sum _{k\mid k\succ _ji}z^s_k\Big ),\quad i\in I, s\in S, j\in J_s; \end{aligned}$$

(17)

$$\begin{aligned} \sum _{s\in S}\left( -\sum _{i\in I}g_iz^s_i+\sum _{i\in I}\sum _{j\in J_s}d_{ij}z_{ij}\right) \ge F^*; \end{aligned}$$

(18)

$$\begin{aligned} x_i + z_i^s \le 1, \quad i\in I, s\in S; \end{aligned}$$

(19)

$$\begin{aligned} z^s_i\in \{0,1\}; 0 \le z_{ij} \le 1,\quad i\in I, s\in S, j\in J; \end{aligned}$$

(20)

$$\begin{aligned} u_i\ge 0, \quad j\in J. \end{aligned}$$

(21)

Let (Z, U), $Z=((z^s_i),(z_{ij}))$, $U = (u_j)$ be an optimal solution of the problem (14)–(21), and let $z^s=(z^s_i)$. Notice that for solution (Z, U) the following equality holds for each $s\in S$, $j\in J_s$:

$$ u_j=\max _{i\mid i\succ _j i_j(z^s)}\big \{c_{ij}x_i\big \}. $$

The value of income the Leader gets in the scenario $s\in S$ is calculated as follows: $C_s = \sum _{j\in J_s}u_j$. To choose the set of active scenarios one should sort values $\{C_s\}$ in descending order. Without loss of generality we can assume that $C_1\ge C_2\ge \dots \ge C_l$. Let r be a such an index that $\sum _{s< r} p_s < p_0\le \sum _{s \le r} p_s$. Then it is easy to see that $\check{f}(x) = -\sum _{i\in I}f_ix_i + C_r$.

Now we are able to construct a pessimistic feasible solution $\chi (x,Z)$. For every $s\le r$ and all $j\in J_s$ such that $u_j>0$ let us denote with $i_j$ the index $i\in I$ for which the constraint (17) is active. Then we set $x_{i_jj}=1$ and $\delta _s = 1$. For all other indexes $i\in I$, $j\in J$, $s\in S$ we set $x_{ij} = 0$ and $\delta _s = 0$. The quadruple $(((x_i),(x_{ij})),(\delta _s),C_r,(z_i^s),(z_{ij}))$ is a desired pessimistic feasible solution of the problem $(\mathcal {L},\mathcal {F})$.

From the above we conclude that pessimistic QCompFLP is equivalent to the problem of maximization of implicitly given pseudo–boolean function. The function depends on m boolean variables. Its value on boolean vector $x = (x_i)$, $i\in I$ can be calculated by solving two mixed–integer linear programming problems.

3 Upper Bound

Consider the problem of finding the global maximum of pseudo–boolean function associating an arbitrary (0,1)–vector x with the value of objective function (1) on the corresponding pessimistic feasible solution $\chi (x,\check{Z})$. The method to calculate an upper bound for values of the function $\check{f}$ consists in constructing and solving of an auxiliary optimization problem, referred to as an estimating problem.

3.1 Estimating Problem

The basis of the estimating problem is a relaxation of the problem $(\mathcal {L},\mathcal {F})$ obtained by removing the lower–level problem $\mathcal {F}$ and its variables. The resulting single–level mixed–integer problem models the situation there Leader is a monopolist. Obviously, an optimal value of the model is a valid upper bound for the function $\check{f}$, but its accuracy is insufficient for practical application.

Similarly to the earlier considered models of competitive location [2–4], the relaxation of $(\mathcal {L}, \mathcal {F})$ can be strengthened by using the system of estimating subsets $\{I_j\}$, $j\in J$. The construction of estimating subsets for the case of single scenario is presented in [3] and can be easily extended to the case of several scenarios. An algorithm of subsets construction allows to claim that if the most preferable for the customer j Leader’s facility $i_j(x)$ is not in $I_j$, then Follower will open a facility which is more preferable for j than $i_j(x)$.

Following the method from [3] we transform an income matrix $(c_{ij})$ into a new matrix $(c^\prime _{ij})$, which majorizes $(c_{ij})$ and is correlated with the preferences of customers. It means that $c^\prime _{ij}\ge c_{ij}$ for all $i\in I$, $j\in J$ and for given $j\in J$ values $(c^\prime _{ij})$ are monotone according to the order $\succeq _j$: given $i_1, i_2\in I$ the relation $i_1\succeq _j i_2$ implies that $c^\prime _{i_1j}\ge c^\prime _{i_2j}$. Such a matrix can be constructed by assuming that $c^\prime _{ij} = \max _{k|i\succeq _j k} c_{kj}$ for all $i\in I$ and $j\in J$.

The algorithm of subsets $\{I_j\}$ construction for a single scenario case is presented in [3]. By considering an arbitrary scenario $s\in S$ separately we obtain the system of subsets $\{I_j\}$, where $j\in J_s$. By switching s one by one we obtain a subset $I_j$ for every $j\in J$. An algorithm of construction ensures that the following inequality holds for every $j\in J$ and every pessimistic feasible solution $\chi (x,\check{Z})$ of the problem $(\mathcal {L},\mathcal {F})$:

$$\begin{aligned} \sum _{i\in I}c_{ij}x_{ij} \le \sum _{i\in I_j}c^\prime _{ij}x_{ij}. \end{aligned}$$

(22)

By assuming that for every $i\in I$ and $j\in J$

$$ c''_{ij} = \left\{ \begin{array}{ll} c'_{ij}, &{}\text { if }\,i\in I_j\\ 0, &{}\text { otherwise } \end{array}\right. , $$

we get the following estimating problem:

$$\begin{aligned} \max _{(x_i),(x_{ij}),(\delta _s), C}\left( -\sum _{i\in I}f_ix_i + C\right) , \end{aligned}$$

(23)

$$\begin{aligned} x_i \ge x_{ij}, \quad i\in I, \quad j\in J; \end{aligned}$$

(24)

$$\begin{aligned} \sum _{i\in I}x_{ij} \le \delta _s,\quad s\in S, \quad j\in J_s; \end{aligned}$$

(25)

$$\begin{aligned} C \le \sum _{i\in I}\sum _{j\in J_s} c''_{ij}x_{ij} + M(1-\delta _s), \quad s\in S; \end{aligned}$$

(26)

$$\begin{aligned} \sum _{s\in S} p_s\delta _s\ge p_0; \end{aligned}$$

(27)

$$\begin{aligned} x_i, \delta _s \in \{0,1\}; 0\le x_{ij}\le 1,\quad i\in I, j\in J, s\in S. \end{aligned}$$

(28)

The model (23)–(28) is further referred to as $\mathcal {B}$. It is a relaxation of the bilevel problem $(\mathcal {L},\mathcal {F})$, obtained by removing the lower–level problem $\mathcal {F}$ and its variables. Inequalities (26) are the corollary of estimating subsets properties (22).

Thus, the optimum of the constructed estimating problem is an upper bound for $\max _{x\in \{0,1\}^m}\check{f}(x)$. Its calculation is a time consuming procedure since the model $\mathcal {B}$ has a big integrality gap provided by inequalities (26), where the right–hand side can significantly change the value after relaxation of variables $(\delta _s)$. To find a compromise between accuracy of the upper bound and its calculation time we suggest two reformulations of the model $\mathcal {B}$.

3.2 Relaxation of a Large MIP

As it was mentioned, solving the problem $\mathcal {B}$ can be a time–consuming procedure. Let us introduce its reformulation involving exponential number of variables.

Let $\mathcal {R}$ be a set of all subsets of S. For each $R\in \mathcal {R}$ we introduce a new boolean variable $u_R$, which takes the value 1 if the set of active scenarios equals to R and 0 otherwise. Additionally we need a (0, 1)–matrix $(a_{sR})$, $s\in S$, $R\in \mathcal {R}$ such that

$$ a_{sR}=\left\{ \begin{array}{ll} 1, &{} \text {if }s\in R \\ 0 &{} \text{ otherwise } \end{array} \right. . $$

Using the above definitions the reformulation of $\mathcal {B}$ is written as follows:

$$\begin{aligned} \max _{(x_i),(x_{ij}),(u_R), C} \left( -\sum _{i\in I}f_ix_i + C \right) , \end{aligned}$$

(29)

$$\begin{aligned} C \le \sum _{i\in I}\sum _{j\in J_s} c''_{ij}x_{ij} + M(1 - \sum _{R\in \mathcal {R}}{a_{sR}u_R}), \quad s\in S; \end{aligned}$$

(30)

$$\begin{aligned} \sum _{i\in I}x_{ij} \le \sum _{R\in \mathcal {R}}a_{sR}u_R,\quad s\in S, j\in J_s; \end{aligned}$$

(31)

$$\begin{aligned} x_i \ge x_{ij}, \quad i\in I, \quad j\in J; \end{aligned}$$

(32)

$$\begin{aligned} \sum _{R\in \mathcal {R}}\sum _{s\in R} a_{sR} p_s u_R\ge p_0; \end{aligned}$$

(33)

$$\begin{aligned} \sum _{R\in \mathcal {R}} u_R = 1; \end{aligned}$$

(34)

$$\begin{aligned} x_i, u_R \in \{0,1\}; 0\le x_{ij}\le 1, \quad i\in I, j\in J, R\in \mathcal {R}. \end{aligned}$$

(35)

To deal with the linear relaxation of this large problem consider its dual:

$$\begin{aligned} \min _{(\alpha _s), (\beta _j), (\gamma _{ij}), \eta , \lambda } \left( -p_0\eta + \lambda + M \right) \end{aligned}$$

(36)

$$\begin{aligned} \sum _{j\in J} \gamma _{ij} \le f_i,\quad i\in I; \end{aligned}$$

(37)

$$\begin{aligned} \beta _j + \gamma _{ij}\ge c''_{ij}\alpha _s, \quad i\in I, j\in J; \end{aligned}$$

(38)

$$\begin{aligned} \sum _{s\in S} \alpha _s = 1, \end{aligned}$$

(39)

$$\begin{aligned} \lambda \ge \sum _{s\in S}a_{sR}\left( p_s\eta + \sum _{j\in J_s} \beta _j - M\alpha _s\right) , \quad R\in \mathcal {R}; \end{aligned}$$

(40)

$$\begin{aligned} \alpha _s, \beta _j, \gamma _{ij}, \eta \ge 0. \end{aligned}$$

(41)

Let $D(\mathcal {R}^\prime ) = \left( (\alpha _s), (\beta _j), (\gamma _{ij}), \eta , \lambda \right)$ be an optimal solution of the problem (36)–(41), where exponentially large index set $\mathcal {R}$ in (40) is replaced with its relatively small subset $\mathcal {R}^\prime \subseteq \mathcal {R}$. In the case when $D(\mathcal {R}^\prime )$ satisfies (40) for all $R\in \mathcal {R}$, it is an optimal solution of the dual problem and provides a required upper bound. Otherwise there exists a (0, 1)–vector $(\delta _s)$ such that

$$\begin{aligned} \sum _{s\in S}\delta _s(p_s\eta + \sum _{j\in J_s} \beta _j - M\alpha _s) > \lambda . \end{aligned}$$

(42)

The existence of such a vector can be checked by solving the following problem:

$$\begin{aligned} \max _{(\delta _{s})}\sum _{s\in S}w_s\delta _s \end{aligned}$$

(43)

$$\begin{aligned} \sum _{s\in S}\delta _s p_s \ge p_0 \end{aligned}$$

(44)

$$\begin{aligned} \delta _s \in \{0,1\}, s\in S, \end{aligned}$$

(45)

where $w_s = p_s\eta + \sum _{j\in J_s} \beta _j - M\alpha _s$.

Given an optimal solution $(\delta ^*_s)$ of the problem (43)–(45), if the inequality $\sum _{s\in S}w_s\delta ^*_s \le \lambda$ holds, then the solution $D(\mathcal {R}')$ satisfies (40) for any $R\in \mathcal {R}$. Otherwise, one of constraints that the $D(\mathcal {R}')$ violates corresponds to the set of scenarios $\{s\in S|\delta ^*_s = 1\}$. We include it into $\mathcal {R}'$ and get back to solving the dual problem with a new constraint of type (40).

Thus the cutting–plane (CP) scheme to calculate an upper bound for the value $\max _{x\in \{0,1\}}\check{f}(x)$ is an iterative process [6]. On each iteration, a restricted dual problem is being solved. We check its optimal solution for feasibility in the initial dual problem. In the case of positive answer, a valid upper bound is obtained and the procedure terminates. Otherwise, a cut is generated by solving a knapsack–type problem, and a new iteration begins.

At the first iteration, we must guarantee a feasibility of restricted dual problem by appreciate choice of $\mathcal {R}'$. In our experiments we initialize $\mathcal {R}'$ with a random subset $S'\subseteq S$ such that $\sum _{s\in S'}p_s \ge p_0$.

3.3 Reformulation of Bilevel Estimating Problem

Let us get back to the problem $\mathcal {B}$. Notice that if the location variables values are chosen, one can easily obtain an optimal facility assignment for each customer and calculate the income value for each possible scenario. Assume that $p_{s} = \frac{1}{l}$ for all $s \in S$. Then an optimal set of active scenarios contains exactly $\lceil lp_0\rceil$ elements with the greatest total income. It leads us to the following bilevel formulation of the problem $\mathcal {B}$, which uses additional variables $(C_s)$, $s\in S$ for the value of income in the corresponding scenario.

$$\begin{aligned} \max _{(x_i),(x_{ij}),(C_s), C}\left( -\sum _{i\in I}f_ix_i + C\right) , \end{aligned}$$

(46)

$$\begin{aligned} x_i \ge x_{ij}, \quad i\in I, \quad j\in J; \end{aligned}$$

(47)

$$\begin{aligned} \sum _{i\in I}x_{ij} \le 1,\quad s\in S, \quad j\in J_s; \end{aligned}$$

(48)

$$\begin{aligned} C_s \le \sum _{i\in I}\sum _{j\in J_s} c''_{ij}x_{ij}, \quad s\in S; \end{aligned}$$

(49)

$$\begin{aligned} C \le C_s + M(1-\delta ^*_s), \quad s\in S; \end{aligned}$$

(50)

$$\begin{aligned} x_i\in \{0,1\}; x_{ij}, C, C_s \ge 0, \quad i \in I, j\in J, s\in S; \end{aligned}$$

(51)

$$\begin{aligned} \text {where }(\delta ^*_s)\, \text {solves} \end{aligned}$$

(52)

$$\begin{aligned} \max _{(\delta _s)}\sum _{s\in S}C_s\delta _s, \end{aligned}$$

(53)

$$\begin{aligned} \sum _{s\in S} \delta _s = \lceil lp_0 \rceil ; \end{aligned}$$

(54)

$$\begin{aligned} 0\le \delta _s \le 1, s\in S. \end{aligned}$$

(55)

In the lower–level problem (53)–(55) $\lceil lp_0\rceil$ scenarios with the greatest income are chosen. Notice that here we can let $\delta _s$, $s\in S$ take fractional values without loss of integrality of optimal solution.

Due to simplicity of the lower–level problem, we substitute it with complementary slackness conditions [1] to obtain a single–level reformulation of the problem $\mathcal {B}$. After linearization the resulting problem $\mathcal {B}'$ is written as follows:

$$\begin{aligned} \max _{(x_i),(x_{ij}),(\delta _s),(C_s), C}\left( -\sum _{i\in I}f_ix_i + C\right) , \end{aligned}$$

(56)

$$\begin{aligned} x_i \ge x_{ij}, \quad i\in I, \quad j\in J; \end{aligned}$$

(57)

$$\begin{aligned} \sum _{i\in I}x_{ij} \le 1,\quad s\in S, \quad j\in J_s; \end{aligned}$$

(58)

$$\begin{aligned} C_s \le \sum _{i\in I}\sum _{j\in J_s} c''_{ij}x_{ij}, \quad s\in S; \end{aligned}$$

(59)

$$\begin{aligned} C \le C_s + M(1 - \delta _s), \quad s\in S; \end{aligned}$$

(60)

$$\begin{aligned} \sum _{s\in S} \delta _s = \lceil lp_0 \rceil ; \end{aligned}$$

(61)

$$\begin{aligned} u_s \le M\delta _s , \quad s\in S; \end{aligned}$$

(62)

$$\begin{aligned} u_s + w \ge C_s, \quad s\in S; \end{aligned}$$

(63)

$$\begin{aligned} u_s + w \le C_s + M(1 - \delta _s), \quad s\in S; \end{aligned}$$

(64)

$$\begin{aligned} x_i, \delta _s \in \{0,1\}; x_{ij}, C_s, C\ge 0, \quad i\in I, j\in J, s\in S. \end{aligned}$$

(65)

Here w and $(u_s), s\in S$ are dual variables for constraints (54) and (55), respectively. Variables $(\delta _s), s\in S$ are boolean in this model since they play role of indicator variables in complementary slackness conditions linearization. Model (56)–(65) by itself is further addressed as $\mathcal {B}'$.

4 Numerical Experiments

In this section, we present results of comparison of proposed estimating problem formulations. The section consists of two parts. In the first subsection, we compare models and their relaxations on randomly generated inputs.

In the second subsection, we consider a number of randomly generated instances of QCompFLP. We construct a system of estimating subsets and compare values of the upper bound provided by problems $\mathcal {B}$, $\mathcal {B}'$, their relaxations and cutting–plane procedure with the value of function $\check{f}$ on locally optimal solution.

Calculations are performed in a single thread by workstation with processors Intel Xeon X5675 3.07 GHz and 96 GB RAM. To solve mixed–integer programs we use Microsoft Solver Foundation 3.1 library with built–in Gurobi MIP solver.

4.1 Instances Not Induced by QCompFLP

To examine the efficiency of upper bound calculation procedures we generate a set of inputs for the estimating problem. For different values of m, n, and l a series of three tests was performed. In each test income matrix $(c_{ij})$, $i\in I$, $j\in J$ is filled with random integers uniformly distributed on the integer range $\{5, 6,\dots , 15\}$. Fixed cost value $f_i$ equals to 50 for all $i\in I$. The probability of scenario is generated in two stages. On the first stage an integer $\rho _s$, $s\in S$ is chosen from the range $\{1,2,3,4\}$ with equal probabilities. The probability of realization of scenario s is set to be equal to $\rho _s/\sum _{l\in S}\rho _l$. In all instances of this bundle of tests $p_0 = 0.6$.

In the Table 1 we provide the following values:

Gap($\mathcal {B}$), relative integrality gap of the model $\mathcal {B}$, i.e. a difference between optimum of linear relaxation of $\mathcal {B}$ and its integer optimum divided by integer optimum, in percents;

Gap(CP), relative integrality gap of the model (29)–(35), i.e. a difference between the value provided by cutting–plane procedure and integer optimum divided by integer optimum, in percents;

OPT, value of integer optimum;

T($\mathcal {B}_{LR}$), calculation time for the linear relaxation of the model $\mathcal {B}$;

T(CP), calculation time for the cutting–plane procedure;

T($\mathcal {B}$), calculation time for model $\mathcal {B}$. It is limited by 10 min. The mark “TL” appears in the cases of reaching the time limit. Also in this cases the optimal value of objective function instead of relative integrality gap is presented in the columns Gap($\mathcal {B}$) and Gap(CP).

Table 1. Instances with different scenario probabilities

As Table 1 shows, the integrality gaps of both the model $\mathcal {B}$ and the model (29)–(35) are dramatically large. However on instances with $m = 10$ and $m = 15$ the relaxation of the second model outperforms the relaxation of $\mathcal {B}$: it can be solved by cutting–plane method in a comparable time and provide more accurate estimation of the optimum of $\mathcal {B}$. The calculation time for optimum of $\mathcal {B}$ is relatively big and grows rapidly while the dimensionality increases, thus the model $\mathcal {B}$ can be utilized in a posteriori accuracy estimation of non-exact algorithms and in implicit enumeration schemes to solve small instances. The relaxations are more perspective for exact methods dealing with bigger instances.

Table 2 presents results of dealing with instances where scenarios are equiprobable. Additionally to columns from the Table 1 it includes:

Gap($\mathcal {B}'$), relative integrality gap of the model $\mathcal {B}'$;

T($\mathcal {B}'_{LR}$), calculation time for the linear relaxation of the model $\mathcal {B}'$;

T($\mathcal {B}'$), calculation time for the model $\mathcal {B}'$ (is bounded by 10 min as like as for $\mathcal {B}$).

Table 2. Instances with equiprobable scenarios

According to the results from Table 2, the model $\mathcal {B}'$ outperforms $\mathcal {B}$ in relative integrality gap and calculation time. Its linear relaxation and linear relaxation of the model (29)–(35) provide the same results, but the first one consumes smaller amount of time. An important observation is that in the cases when $p_0l$ is an integer number linear relaxations of the three proposed models provide the same results as it is in the case of the fourth series of tests, where $l = 10$ and $p_0l = 6$.

4.2 Instances Induced by QCompFLP

In this subsection, we study the proposed models as an upper bound providers for the problem QCompFLP. Numerical data preparation consists of generating the QCompFLP instance, constructing an estimating subset system, and forming an input data for the estimating problem. For each generated instance of QCompFLP we start a local search procedure using scheme from [8] to obtain a lower bound for the optimum. It allows us to estimate the quality of the upper bound.

QCompFLP instances are generated as follows. All operations of random choice are performed with uniform distribution on the corresponding domain. Fixed costs values $f_i$ and $g_i$, $i\in I$ are calculated with formula $50 + 5\xi$, where value of $\xi$ is randomly chosen from the integer range $\{-3,-2, \dots , 3\}$ for each $f_i$ and each $g_i$, $i\in I$. For each $i\in I$, $j\in J$ the income value $p_{ij}$ is randomly chosen from the set $\{6,7,\dots ,14\}$. The value of $q_{ij}$ is calculated with formula $p_{ij} + \zeta$, where $\zeta$ is randomly chosen from range $\{-3,-2,\dots ,3\}$ each time. Scenario probabilities are equal. For each customer $j\in J$ we select at random the number of scenario the customer appears in and the order $\succeq _j$.

Table 3. Instances induced by QCompFLP

From Table 3 we see that revealed relations between performances of formulations of the estimating problem are retained for induced instances.

Column LB contains values of lower bound. In our case it is the best value of function $\check{f}$ the local search has found in 1 min for instances with $m = 10$ and in 10 min for instances with $m = 15$. The accuracy of the upper bound provided by estimating problem is comparable with results obtained for procedures using similar technique for previously studied bilevel location problems relative to QCompFLP [2, 4].

Table 4 illustrates the influence of reliability level on the lower and upper bounds. We consider a single instance of QCompFLP, which is the first one in a bundle of tests with $m = 10$, $n = 640$, $l = 16$ from the Table 3. As we can see the values of upper and lower bounds decrease with the grow of reliability level. The formulation $\mathcal {B}'$ performs better in common. However, the last test with $p_0 = 1$ leads the solver to crush without apparent reasons from our side.

Table 4. Influence of reliability level $p_0$

5 Conclusion and Discussion

In this paper, we investigate ways of calculation of an upper bound for the QCompFLP using reformulations of the estimating problem. Numerical experiments show that the suggested reformulations have smaller integrality gap. We highlighted a special case of QCompFLP where scenarios are equiprobable. This leads to a model, which outperforms the initial one in integrality gap and calculation time.

The quantile criteria is an interesting view on the robustness of solution. To operate with uncertainty in income from the customers we are to duplicate each customer for each possible value of the income. It leads us to the necessity of investigating techniques to deal with instances with large number of customers. Exact and approximate methods for the QCompFLP are subjects of the future research as well.