$\varepsilon$-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario

Abstract

We consider a model of two parties’ competition organized as a Stackelberg game. The parties open their facilities intending to maximize profit from serving the customers that behave following a binary rule. The set of customers is unknown to the party which opens its facilities first and is called the Leader. Instead, a finite list of possible scenarios specifying this set is provided to the Leader. One of the scenarios is to be realized in the future before the second party, called the Follower, would make their own decision. The scenarios are supplied with known probabilities of realization, and the Leader aims to maximize both the probability to get a profit not less than a specific value, called a guaranteed profit, and the value of a guaranteed profit itself. We formulate the Leader’s problem as a bi-objective bi-level mathematical program. To approximate the set of efficient solutions of this problem, we develop an $\varepsilon$-constraint method where a branch-and-bound algorithm solves a sequence of bi-level problems with a single objective. Based on the properties of feasible solutions of a bi-level program and mathematical programming techniques, we developed three upper bound procedures for the branch-and-bound method mentioned. In numerical experiments, we compare these procedures with each other. Besides that, we discuss relations of the model under investigation and the stochastic competitive location model with uncertain profit values.

1 Introduction

Consider a situation when a firm enters the market by opening facilities providing some service to customers. In general, a decision about facilities’ location must anticipate the competitors’ reaction which is rational and prescribed by a solution of some optimization problem. Competitive nature of the process cannot be ignored since facilities’ income depends on the further actions of competitors. We assume that there is a single competitor on the market or all the competitors can be aggregated into a single one. Then, we can consider the party locating facilities as the Leader in a Stackelberg game (Stackelberg 1952). The second player of this game, called the Follower, represents the competitor who makes its decision when knowing the Leader’s one.

Parameters of demand for products or services, provided by the competing parties, are affected by many factors and are hardly predictable. Besides the uncertainty inherent to predicted data, the demand is sensitive to external factors influencing its structure such as economic and political circumstances. We assume the Leader to consider a finite number of possible demand scenarios. Each scenario fully characterizes the set of customers with their attributes and has a known probability of realization. One of the scenarios will be implemented in the future, but, at the moment of making a decision, the available information is insufficient to determine which one it would be.

In a Stackelberg game framework, the Follower decides after the Leader. It provides the Follower with knowledge about the location of the Leader’s facilities. Moreover, additional pieces of evidence about the demand scenario reveal themselves, so the Follower can distinguish the scenario realized before making their own decision. Thus, unlike the Leader, the Follower is in a situation of full information when all the uncertainties have vanished. In this aspect, the BCompFLP can be considered as a so-called two-stage model, where decisions referred to as here-and-now decisions are made before revealing the values of uncertain parameters. When these values are known, other decisions called wait-and-see are computed. In this terminology, the Leader’s location decisions are here-and-now decisions, whereas the Follower’s location and customer’s distribution are wait-and-see decisions since these values are computed when the scenario is implemented.

Similarly to maximization facility location problem (Krarup and Pruzan 1983), we assume the parties to maximize their profit calculated as an income from service the customers minus fixed costs of open facilities. In a situation of uncertain demand scenario, the Leader’s income is a random variable with a discrete distribution. To compare different Leader’s solutions with each other, numeric characteristics of the income distribution such as expected value, value-at-risk ($V\!aR_\alpha$), conditional value-at-risk ($CV\!aR_\alpha$), and others could be used (Rockafellar and Uryasev 2002). The expectation is naturally the most widely used metric. In the paper (Yanıkoğlu and Kuhn 2018), the Leader’s objective function includes a mathematical expectation of the revenue from serving the customers with uncertain demand volumes. The authors consider the lower-level problem to be a linear programming problem with continuous variables. In our case, the wait-and-see variables are involved into the Follower’s location problem having a form of mixed-integer programming problem (MIP) being significantly harder. We assume that the Leader maximizes a guaranteed profit instead of the average one. At the same time, the Leader might be interested in knowing not only the safest and conservative solution but more risky and profitable ones as well. To satisfy this need, we supplement the Leader’s problem with the second objective function, representing a probability of obtaining a guaranteed profit. Following this way, we come to a bi-objective competitive facility location problem (BCompFLP), where both the Leader’s profit and the probability of getting it are maximized on the upper level. The lower-level problem of the BCompFLP is to maximize the Follower’s profit in each of the scenarios.

Possible applications for the BCompFLP may arise when there are several projects of reformations. For instance, a modification of the transportation system alters an attainability of facilities. Reformation of the taxation scheme affects the prices and, consequently, the demand of customers. Thus, each reformation project specifies customers’ behavior and characterize an individual scenario. In this situation, the probability of scenario implementation can be estimated by experts who are familiar with practices of decision-making in reformation processes. Another application case is the presence of different economic predictions provided by many experts. The buying power of the customers and their interest in a certain kind of products or services depends on the economic situation. The Leader may build scenarios based on parameters predicted by experts, and the probabilities of scenarios implementation can be coherent to the authority of the experts and their level of confidence. Finally, the scenarios are generated by sampling the demand parameters from some anticipated distribution when sample approximation (Emelogu et al. 2016) is applied to solve the Leader’s problem with stochastic demand. All the scenarios are equiprobable in the sample approximation problem, so this special class of BCompFLP instances, where the probabilities of realization are equal, is of particular interest.

The current state of the competitive location area is shown in detail by the most recent reviews (Kress and Pesch 2012; Karakitsiou 2015; Ashtiani 2016; Aras and Küçükaydın 2017). To put the present paper into the context of existing studies, we list the most significant modeling and algorithmic approaches to competitive location. As it is noticed in Spoerhase (2010) and Ashtiani (2016), the ingredients of the competitive location models are the space to establish facilities in, the customer behavior rule used, the demand type, the possibility of redesign or relocate facilities, and other factors. Besides, we refer to a review (Farahani et al. 2010) observing objective function types used in multi-criteria location problems.

The underlying space where the parties locate their facilities is considered to be either continuous or discrete. In continuous formulations, a facility can be placed at any of an infinite number of points from the continuous space such as Euclidean plane (Davydov et al. 2014; Saiz et al. 2009) or edges of a graph representing a transportation network (Bandyapadhyay et al. 2015). The present paper considers a discrete location model where the set of potential location is finite and can be represented by an abstract finite set or a set of graph nodes.

Regarding the customers’ behavior model, in most cases, an initial point is a definition of utility perceived by a customer from being served by a facility. Depending on aspects taken into account by the model, the utility is assumed to be a function of traveling distance, quality of the facility, service prices, and other measurable factors. From the computed utilities, two kinds of behavior can be simulated (Santos-Peñate et al. 2007). In proportional behavior rule, a customer’s demand is split among the open facilities in proportion to utility values. Models incorporating this rule are burdened by nonlinearities expressing the proportions and can be applied to problems of simultaneously choosing the location and design of new facilities. A short communication on models with a particular case of proportional rule called Huff-like or gravity-based rule is given in Fernández and Hendrix (2013). A cover-based proportional rule, where the demand is equally split among the facilities covering the customer by their spheres of influence, is presented in Drezner et al. (2015). Instead of visiting all the facilities producing nonzero utility, a customer might choose a single facility to get service from by maximizing the utility value perceived. In this case, we come to a binary behavior rule. Generally, additional assumptions must be made to break ties between facilities producing the same utility value. This issue is discussed in detail in Pelegrín et al. (2015). If the utility value depends only on the location of the facility and all the utility values perceived by a customer are different, we come to a situation when the customer is associated with an order defined on the set of potential facility locations. Based on the utility values, the customer may compare any couple of facilities and decide which one they would prefer to another. In the present paper, we assume the customers to be accompanied with linear-order relations representing their preferences. Binary behavior rule can be formulated with linear inequalities and is suitable for modeling the demand for homogeneous products. Polyhedral properties of formulations for this rule are studied in Vasilyev et al. (2013) and Canovas et al. (2007).

Due to the high computational complexity of bi-level programming problems, multi-objective formulations are studied rarely in the literature. In Uno and Katagiri (2008), the authors consider a problem to prevent an attacker from reaching important nodes of the network. The Leader is a protection planner who opens defensive facilities at some nodes, while the Follower, an attacker, minimizes an amount of energy consumed while moving toward the important nodes. In the multi-objective formulation, for each of the important nodes, a corresponding objective represents the amount of energy the attacker has when it reaches the node. The authors propose a heuristic approach to find satisfactory solutions. A series of works (Fernández and Tóth 2009; Redondo et al. 2015) focuses on single-level nonlinear continuous competitive location problems with two objectives: maximizing both the market share and the profit obtained. In Gang et al. (2015) and references therein, evolution-based approaches are utilized to solve some industrial problems formulated in terms of multi-objective bi-level programming. Finally, in Alekseeva et al. (2017), the authors consider a bi-level location problem where the lower-level problem has several objectives. That case is complicated even in terms of definitions since multiple incomparable solutions of the lower-level give different values to the Leader’s objective function. The authors overcome terminological and computational difficulties and propose a hybrid procedure to obtain near-optimal solutions for the upper-level problem.

The papers (Beresnev 2014; Hemmati and Smith 2016) consider formulations, closely related to the one studied in the present paper. They propose exact algorithms to maximize the Leader’s profit in a case when the demand scenario is known. The algorithms implement the branch-and-bound approach and the cut generation scheme, respectively. In contrast to Beresnev (2014), in Hemmati and Smith (2016), another interpretation of the location model is given where competing parties choose products to place on the market. Customers buy the most preferable product, whereas, according to free choice of supplier rule used both in Beresnev (2014) and in the present paper, a party can serve the customer by any facility which is preferred to all the competitor’s ones.

In the present paper, we suggest an $\varepsilon$-constraint method (Ehrgott 2006) to find an approximation of the Pareto frontier of BCompFLP. It consists in solving a series of single-objective bi-level subproblems where the value of the second Leader’s objective function, representing a probability of getting a guaranteed profit, is bounded from below. Models of that type were considered in Ivanov and Morozova (2016) where a local search procedure is suggested to find a good Leader’s solution. In Melnikov and Beresnev (2016), we have formulated an estimating problem in the form of MIP providing an upper bound for the single-objective subproblem. Two reformulations of the estimating problem have been suggested as well. In the present work, we incorporate the suggested upper bound procedures into an implicit enumeration scheme called as a subroutine in the $\varepsilon$-constraint method. To investigate the efficiency of elements of this scheme, we perform numerical experiments with artificial data. Besides studying the efficiency of the procedures developed, we explore connections of BCompFLP with stochastic competitive location model where profit values are random parameters with known distribution. In our experiments, we inspect the distribution of the Leader’s objective function and try to answer the question if sample approximation of the stochastic problem can be utilized to get quality solutions of the initial problem.

The paper is organized as follows: In Sect. 2, we introduce all the necessary notations and formalize the BCompFLP in terms of bi-level integer programming. Concepts of feasibility are carefully discussed as well. The key ingredients of the proposed method such as the branch-and-bound scheme to solve a constrained Leader’s problem and the upper bound procedures utilized are presented in Sect. 3. Computational study of the proposed procedures and experimental results are given in Sect. 4. Finally, Sect. 5 concludes the paper.

2 Mathematical model

Before formalizing the Leader’s problem, let us introduce some auxiliary terminology. When taking risks, the Leader may consider only some of the scenarios available and make a more specific decision leading to higher income. We call these scenarios active, and the other ones inactive, respectively. The least profitable active scenario determines the value of a guaranteed income, i.e., a tight lower bound for the value of income in a case when the scenario realized is an active one.

In the mathematical model of BCompFLP, we use the following index sets:

• $I=\{1,\ldots ,m\}$ is a set of locations available to open facilities;

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

• $J_s$ is a set of customers’ indexes in the scenario $s\in S$.

Without loss of generality, we assume that $J_{s_1}\cap J_{s_2}=\emptyset$ for all $s_1,s_2\in S$, $s_1\ne s_2$. This assumption is not restrictive since any customer appearing in several scenarios can be duplicated so that all the copies would have different indexes. Let $J = \bigcup _{s\in S} J_s=\{1,\ldots ,n\}$ denote the set of all customers’ indexes.

The list of input parameters for BCompFLP consists of

• $f_i$, the fixed cost of opening the Leader’s facility $i\in I$;

• $g_i$, the fixed cost of opening the Follower’s facility $i\in I$;

• $c_{ij}$, the income of the Leader’s facility i from serving the customer $j\in J$;

• $d_{ij}$, the income of the Follower’s facility i from serving the customer $j\in J$;

• $p_s$, the probability of realization of scenario $s\in S$.

Finally, we use the following binary variables.

• $x_i$ is equal to one, if the Leader opens facility i, and zero otherwise;

• $z_i^s$ is equal to one, if the Follower opens facility $i\in I$ in the scenario $s\in S$, and zero otherwise;

• $x_{ij}$ is equal to one, if the Leader’s facility $i\in I$ is assigned to serve the customer $j\in J$, and zero otherwise;

• $z_{ij}$ is equal to one, if the Follower’s facility $i\in I$ is assigned to serve the customer $j\in J$, and zero otherwise;

• $\delta _s$ is equal to one, if the scenario $s\in S$ is active, and zero otherwise.

We assume that each customer is served by a single facility chosen with respect to customer’s preferences represented by a linear order on the set I. Given $i_1$, $i_2\in I$, $j\in J$ the relation $i_1 \succeq _j i_2$ means that for the customer j, either $i_1$ is more preferable than $i_2$ or $i_1 = i_2$. If $i_1\succeq _j i_2$ and $i_1\ne i_2$, then we use the notation $i_1 \succ _j i_2$. The greatest element of a non-empty subset $I'\subseteq I$ according to the order $\succeq _j$ is denoted with $\alpha _j(I') = \{i'\in I'| i'\succeq _j k \, \forall k\in I'\}$. Given a nonzero Boolean vector ${\varvec{v}} = (v_i)$, $i\in I$, we set $\alpha _j({\varvec{v}}) = \alpha _j(\{i\in I|v_i = 1\})$.

By using the introduced notations, the BCompFLP can be written as the following a bi-objective bi-level program:

$$\begin{aligned}&\max _{(x_i),(x_{ij}),(\delta _s)} \left( -\sum _{i\in I}f_ix_i +\min _{s\in S| \delta _s = 1} \sum _{i\in I}\sum _{j\in J_s}c_{ij} x_{ij} \right) , \end{aligned}$$

(1)

$$\begin{aligned}&\max _{(x_i),(x_{ij}),(\delta _s)} \sum _{s\in S}p_s\delta _s, \end{aligned}$$

(2)

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

(3)

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

(4)

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

(5)

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

(6)

$$\begin{aligned}&({\tilde{z}}^s_i), ({\tilde{z}}_{ij}) \text { solves the Follower's problem:} \end{aligned}$$

(7)

$$\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}$$

(8)

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

(9)

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

(10)

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

(11)

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

(12)

The first objective function (1) of the upper-level problem represents the Leader’s guaranteed profit calculated as fixed costs subtracted from the guaranteed income. The second Leader’s objective (2) is to maximize the total probability of active scenario realization. Inequalities (3) forbid to serve customers from closed facilities; (4) guarantee that customers from active scenarios cannot be served by more than one facility; (5) ensure that the customer is served with a facility which is more preferable than any competitor’s one.

The lower-level objective function (8) is a sum of profit values obtained by the Follower in all the scenarios. Its maximization is equivalent to maximizing the profit for each scenario individually. The constraints (9) and (10) have the same meaning as the upper-level constraints (3) and (5), respectively. Finally, the inequalities (11) provide that the Follower does not open facility in locations occupied by the Leader.

For brevity, further, we use the following vector notations. Vectors of Leader’s and Follower’s location variables’ values $(x_i)$, $i\in I$, and $(z_i^s)$, $i\in I$, $s\in S$, are denoted by ${\varvec{x}}$ and ${\varvec{z}}$, correspondingly. Similarly, values $(\delta _s)$ are stored in the vector $\varvec{\delta }$. Assignment matrices $(x_{ij})$ and $(z_{ij})$, $i\in I$, $j\in J$, are denoted by ${\varvec{X}}$ and ${\varvec{Z}}$, respectively. Given ${\varvec{x}}$, we denote the problem ${\mathcal {F}}$, where the corresponding values of $x_i$, $i \in I$, are introduced into the inequalities (10), (11), by ${\mathcal {F}}({\varvec{x}})$. Analogously, the problem ${\mathcal {L}}$ with the value of ${\varvec{z}}$ in the constraints (5) is denoted by ${\mathcal {L}}({\varvec{z}})$. Whole model (1)–(12) is further referred to as $({\mathcal {L}},{\mathcal {F}})$.

2.1 Pessimistic feasible solutions of the problem $({\mathcal {L}},{\mathcal {F}})$ and efficiency

Consider a triplet $(X, \varvec{\delta }, Z)$, where $X = ({\varvec{x}}, {\varvec{X}})$, $Z = ({\varvec{z}}, {\varvec{Z}})$. We say that it is a feasible solution of the problem $({\mathcal {L}}, {\mathcal {F}})$ induced by a pair $({\varvec{x}}, \varvec{\delta })$ if it satisfies constraints (3)–(6), (9)–(12) and Z is an optimal solution of the problem ${\mathcal {F}}({\varvec{x}})$. To simplify the presentation, we additionally assume that assignment variables $(x_{ij})$ and $(z_{ij})$ take their optimal values in all the feasible solutions.

When the lower-level problem has multiple optimal solutions, it is necessary to specify the rule to select the one to be incorporated in the upper-level problem. The most common approach is considering optimistic and pessimistic feasible solutions (Dempe 2002; Yanıkoğlu and Kuhn 2018). For a single-objective bi-level maximization problem, these concepts assume that the lower-level optimal solution is chosen which maximizes or minimizes the upper-level objective function, respectively. However, when the upper-level problem is multi-objective, it is unclear, which lower-level solution is most or least desirable for the upper-level objective functions. This difficulty does not apply to the BCompFLP since the Follower influences the Leader’s profit only. The set of active scenarios, determining the value of the second Leader’s objective function, can be chosen independently when locations and assignments of the competing parties are known. Thus, we can base the rule of choosing the Follower’s optimal solution on the value of the Leader’s profit. Often, a pessimistic formulation of a bi-level problem is more difficult in terms of the existence of an optimal solution and computing a feasible solution than an optimistic one. Here, we discuss a pessimistic formulation, but an optimistic one can be covered with the same technique after a few natural modifications.

Let $L_1(X, \varvec{\delta }, Z)$ denotes the value of objective function (1) on the feasible solution $(X, \varvec{\delta }, Z)$. Analogously, let $L_2(X, \varvec{\delta }, Z) = \sum _{s \in S}p_s\delta _s$ be the corresponding value of the objective function (2). A feasible solution $(X', \varvec{\delta }, {\tilde{Z}})$ induced by the pair $({\varvec{x}}, \varvec{\delta })$ is called a pessimistic feasible solution of the problem $({\mathcal {L}},{\mathcal {F}})$ if $L_1(X', \varvec{\delta }, {\tilde{Z}}) \le L_1(X, \varvec{\delta }, Z)$ for any feasible solution $(X, \varvec{\delta }, Z)$ induced by $({\varvec{x}}, \varvec{\delta })$.

Now we see that the pessimistic BCompFLP can be considered as a problem to maximize an implicitly given vector-function $\varvec{{\mathfrak {f}}}:\{0,1\}^m\times \{0,1\}^l\rightarrow {\mathbb {R}}^2$ such that, for any pair of (0,1)-vectors $({\varvec{x}}, \varvec{\delta })$, we have ${\mathfrak {f}}_r({\varvec{x}}, \varvec{\delta }) = L_r(X, \varvec{\delta }, {\tilde{Z}})$, $r = 1,2$, where $(X, \varvec{\delta }, {\tilde{Z}})$ is a pessimistic feasible solution induced by $({\varvec{x}}, \varvec{\delta })$.

To compute $\varvec{{\mathfrak {f}}}({\varvec{x}}, \varvec{\delta })$, we could find an optimal Follower’s location $\tilde{{\varvec{z}}}$ minimizing the Leader’s profit in all the scenarios. Similarly to the single-scenario formulation (Beresnev 2014), the procedure consists of two steps. At the first step, we solve the problem ${\mathcal {F}}({\varvec{x}})$ and obtain its optimum $F^*$. At the second step, an auxiliary MIP provides a Follower’s solution minimizing the Leader’s objective function (1).

Having optimal location vector $\tilde{{\varvec{z}}}^s=({\tilde{z}}^s_i)$ of the Follower, we compute the value of Leader’s income from serving each of the customers:

$$\begin{aligned} u_j=\max _{i\mid i\succ _j \alpha _j(\tilde{{\varvec{z}}}^s)}(c_{ij}x_i),\quad s\in S,\quad j\in J_s. \end{aligned}$$

When $\varvec{\delta }$ is chosen, we can construct a pessimistic feasible solution induced by $({\varvec{x}}, \varvec{\delta })$. If $\delta _s = 0$ for some $s\in S$, then $x_{ij} = 0$ for any $i\in I$, $j\in J_s$. For $s\in S$ such that $\delta _s = 1$, and all $j\in J_s$ such that $u_j>0$, let $i_j = \arg \max _{i\in I}c_{ij}\Big (x_i-\sum _{k\mid k\succ _ji}z^s_k\Big )$. Then, we set $x_{i_jj}=1$. For all other indexes $i\in I$, $j\in J$ we set $x_{ij} = 0$. The triplet $(X,\varvec{\delta },{\tilde{Z}})$, $X = ({\varvec{x}},(x_{ij}))$ is a desired pessimistic feasible solution of the problem $({\mathcal {L}},{\mathcal {F}})$. Now, $\varvec{{\mathfrak {f}}}({\varvec{x}},\varvec{\delta })$ can be computed straightforwardly:

$$\begin{aligned} {\mathfrak {f}}_1({\varvec{x}},\varvec{\delta }) = -\sum _{i\in I} f_ix_i + \min _{s|\delta _s = 1}\sum _{j\in J_s}u_j,\quad {\mathfrak {f}}_2({\varvec{x}},\varvec{\delta }) = \sum _{s\in S}p_s\delta _s. \end{aligned}$$

We say that the pair $({\varvec{x}},\varvec{\delta })$strongly dominates$({\varvec{x}}',\varvec{\delta }')$ if $\varvec{{\mathfrak {f}}}({\varvec{x}},\varvec{\delta }) > \varvec{{\mathfrak {f}}}({\varvec{x}}',\varvec{\delta }').$ Additionally, $({\varvec{x}},\varvec{\delta })$dominates$({\varvec{x}}',\varvec{\delta }')$ if $\varvec{{\mathfrak {f}}}({\varvec{x}},\varvec{\delta }) \ge \varvec{{\mathfrak {f}}}({\varvec{x}}',\varvec{\delta }')$ and there exists $r\in \{1,2\}$ such that ${\mathfrak {f}}_r({\varvec{x}},\varvec{\delta }) > {\mathfrak {f}}_r({\varvec{x}}',\varvec{\delta }').$ The pair $({\varvec{x}},\varvec{\delta })$ is called (weakly) efficient if there is no other pair that (strongly) dominates $({\varvec{x}},\varvec{\delta })$.

3 $\varepsilon$-Constraint method

We have shown that BCompFLP can be considered as a problem to maximize a vector-function $\varvec{{\mathfrak {f}}}:\{0,1\}^m\times \{0,1\}^l\rightarrow {\mathbb {R}}^2$ mapping an arbitrary pair of (0,1)-vectors $({\varvec{x}},\varvec{\delta })$ into the values of objective functions $L_1(X,\varvec{\delta },{\tilde{Z}})$, $L_2(X,\varvec{\delta },{\tilde{Z}})$ on the pessimistic feasible solution $(X,\varvec{\delta },{\tilde{Z}})$ induced by the pair. Under solution of this problem, we would mean the set of all efficient pessimistic feasible solutions or, in other terminology, a Pareto frontier (Ehrgott 2006). Other objects related to a multi-objective problem are so-called nadir points (Özpeynirci 2017) being efficient solutions with the worst values of an individual objective function. Such solutions show the boundaries for values of each of the objective functions. In our case, these are the “best-case” and the “worst-case” solutions, i.e., whose ones where the set of active scenarios contains the most profitable scenario and all the possible scenarios, respectively.

To approximate the set of efficient solutions, we develop an $\varepsilon$-constraint method iteratively finding weakly efficient solutions of the Leader. On each iteration, the objective function (1) is maximized while the function (2) is bounded from below. Note that depending on $\varvec{\delta }$, the function ${\mathfrak {f}}_2$ takes value from the set ${\mathcal {P}} = \{p'|p' = \sum _{s \in S'}p_s, S'\subseteq S\}$. It implies that the set of weakly efficient solutions may contain up to $2^l$ elements. We start from some initial value of the probability threshold $p_0$ and solve the problem

$$\begin{aligned}&\max _{{\varvec{x}},\varvec{\delta }}{\mathfrak {f}}_1({\varvec{x}},\varvec{\delta }), \end{aligned}$$

(13)

$$\begin{aligned}&{\mathfrak {f}}_2({\varvec{x}},\varvec{\delta })\ge p_0 \end{aligned}$$

(14)

by an implicit enumeration algorithm. Schematically, it is a parallel depth-first search method with greedy branching function applied to location variables ${\varvec{x}}$.

The obtained solution $({\varvec{x}}^*, \varvec{\delta }^*)$ is weakly efficient since, for any feasible solution $({\varvec{x}}', \varvec{\delta }')$ such that ${\mathfrak {f}}_2({\varvec{x}}', \varvec{\delta }') \ge p_0$, it holds ${\mathfrak {f}}_1({\varvec{x}}', \varvec{\delta }') \le {\mathfrak {f}}_1({\varvec{x}}^*, \varvec{\delta }^*)$. On the next iteration, we increase the value of $p_0$ and repeat the procedure while $p_0 \le 1$.

Since the left-hand side of the constraint (14) takes values from the set ${\mathcal {P}}$, it is sufficient to consider all the elements of ${\mathcal {P}}$ as the probability threshold $p_0$. Note that if the pair $({\varvec{x}}_0,\varvec{\delta }_0)$, where $\varvec{\delta }_0 = 0$, is weakly efficient, then ${\mathfrak {f}}_1({\varvec{x}},\varvec{\delta }) = 0$ for any weakly efficient pair $({\varvec{x}},\varvec{\delta })$. Thus, computing the set of weakly efficient solutions, one may start from the initial value of $p_0$ equal to $\min _{s\in S}p_s$. Having the solution $({\varvec{x}}^*, \varvec{\delta }^*)$ of the problem (13)–(14), the next value of the threshold to be considered is $\min \{p\in {\mathcal {P}}| p > \sum _{s\in S}p_s\delta ^*_s\}$. It is easy to see that the problem to find this value is NP-hard since it is relative to a (0,1)-knapsack problem with weights of items equal to their costs. Based on additional assumptions about the values of $p_s$, efficient approaches to modify the threshold value $p_0$ can be suggested. We apply a strategy to increase $p_0$ by some predefined discretization parameter $\Delta$ after each iteration.

3.1 Solving a subproblem by implicit enumeration

To get an advantage of the power of modern computers, we have developed a parallel branch-and-bound algorithm to solve a subproblem (13), (14). The algorithm is organized in a master–worker framework. A master thread keeps all the information about the computational process and maintains exchanging data between worker threads. An essential role of the master thread is balancing the load of the workers. It is performed by splitting the unexplored part of the feasible region and assigning idling workers to perform the searching process in the subregions obtained. Each of the workers performs a depth-first search and informs the master about computational progress.

During the branching process, some components of the vector ${\varvec{x}}$ become fixed to a given value, 0 or 1. A worker stores the information about these components in a partial solution${\varvec{y}} = (y_i)$ in a following way. A component $y_i$, $i\in I$, is set to zero or one if $x_i$ is fixed to take the corresponding value. Otherwise, $y_i$ is set to be equal to an undetermined value “$*$”. Further, we use additional notations $I^\theta ({\varvec{y}}) = \{i\in I| y_i = \theta \}$, $\theta \in \{0, 1, *\}$, and $P({\varvec{y}}) = \{{\varvec{x}}\in \{0,1\}^m| x_i = y_i \text { for all } i\in I^0({\varvec{y}})\cup I^1({\varvec{y}})\}$. The problem ${\mathcal {L}}$ augmented with constraints $x_i = y_i$, $i\in I^1({\varvec{y}})\cup I^0({\varvec{y}})$, is further referred to as $L({\varvec{y}})$.

Having T working threads, we initialize a computation by generating T partial solutions ${\varvec{y}}_1$, ${\varvec{y}}_2, \ldots , {\varvec{y}}_T$ such that $\bigcup _{t\in \{1,\ldots ,T\}}P({\varvec{y}}_t) = \{0,1\}^m$ and $P({\varvec{y}}_{t_1}) \cap P({\varvec{y}}_{t_2}) = \emptyset$ for $t_1\ne t_2$. Further, the worker t is assigned to solve the problem ${\mathcal {L}}({\varvec{y}}_t)$. When a subset $P({\varvec{y}}_t)$ is explored, one of the workers, having a relatively large subset of unexplored solutions, receives a command to split its workload. For a partial solution ${\varvec{y}}$ encoding the unexplored subset, two partial solutions ${\varvec{y}}^0$ and ${\varvec{y}}^1$ are generated. These partial solutions differ from ${\varvec{y}}$ in a single component $i\in I^*({\varvec{y}})$ in a such a way that $y^0_i = 0$ and $y^1_i = 1$. A worker–donor proceeds with the partial solution ${\varvec{y}}^0$, whereas a worker–recipient initializes computations with ${\varvec{y}}^1$.

An implicit enumeration of a subset $P({\varvec{y}})$ relies on the upper bound for a maximum of the function ${\mathfrak {f}}_1$, which is computed by solving a specially constructed estimating problem proposed in Melnikov and Beresnev (2016). The problem has a form of MIP and can be tackled with a common MIP solver. Two alternative ways of computing an upper bound, based on the mentioned model, are proposed as well. Further, we describe all these procedures.

3.2 Estimating problem ${\mathcal {B}}(y)$

Similarly to the single-scenario competitive location model considered in Beresnev (2014), the upper bound for the optimum of ${\mathcal {L}}({\varvec{y}})$ can be obtained by solving a specially constructed MIP. To formulate it, we compute a system of estimating subsets $\{I_j({\varvec{y}})\}$, $j\in J$. The algorithm of constructing the estimating subsets is given in Beresnev (2013). The key property of these subsets is formulated in the following lemma.

Lemma 1

(Beresnev 2013) Given $j\in J$, let ${\varvec{x}}\in P({\varvec{y}})$ and $\alpha _j({\varvec{x}})\not \in I_j({\varvec{y}})$. Then, $\sum _{k\in I|k \succ _j \alpha _j({\varvec{x}})}{\tilde{z}}_k \ge 1$.

Further, we transform the income matrix $(c_{ij})$ into a matrix $(c^\prime _{ij})$ which is monotone with respect to the preferences of customers and majorizes $(c_{ij})$. It means that for every $j\in 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}$. Additionally, $c^\prime _{ij}\ge c_{ij}$ for all $i\in I$, $j\in J$. Such a matrix can be constructed by setting $c^\prime _{ij} = \max _{k|i\succeq _j k} c_{kj}$ for all $i\in I$ and $j\in J$.

Lemma 2

For every $j\in J$ and every pessimistic feasible solution $(X,\varvec{\delta },{\tilde{Z}})$ of the problem $({\mathcal {L}}({\varvec{y}}),{\mathcal {F}})$, the following inequality holds:

$$\begin{aligned} \sum _{i\in I}c_{ij}x_{ij} \le \max _{i\in I_j}c'_{ij}x_i, \end{aligned}$$

(15)

where maximum over the empty set equals zero.

Proof

If ${\varvec{x}} = 0$, then the inequality holds. Assume that the condition (15) is violated for some pessimistic feasible solution $(X,\varvec{\delta },{\tilde{Z}})$ of the problem $({\mathcal {L}}({\varvec{y}}),{\mathcal {F}})$ induced by a pair $({\varvec{x}}, \varvec{\delta })$ with ${\varvec{x}} \ne 0$. In this case, $k = \arg \max _{i\in I}c_{ij}x_{ij}\not \in I_j$. Moreover, for any $i\in I_j$ such that $x_i = 1$ we have $k\succ _j i$ due to monotonicity of the matrix $c'_{ij}$. It implies that $\alpha _j({\varvec{x}})\not \in I_j$, but from Lemma 1 and conditions (5), $x_{ij} = 0$ for any $i\in I$ since there exists a Follower’s facility which is more preferable for the customer j than $\alpha _j({\varvec{x}})$. Thus, we come to a contradiction. $\square$

By setting

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

for all $i\in I$, $j\in J$, we get the following estimating problem:

$$\begin{aligned}&\max _{(x_i),(x_{ij}),(\delta _{s}), C} \left( -\!\!\!\sum _{i\in I^1({\varvec{y}})}f_i -\!\!\!\sum _{i\in I^*({\varvec{y}})}f_ix_i + C \right) , \end{aligned}$$

(16)

$$\begin{aligned}&x_i \ge x_{ij}, \quad i\in I^*({\varvec{y}}), \quad j\in J; \end{aligned}$$

(17)

$$\begin{aligned}&\sum _{i\in I\backslash I^0({\varvec{y}})}x_{ij} \le \delta _s,\quad s\in S, \quad j\in J_s; \end{aligned}$$

(18)

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

(19)

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

(20)

$$\begin{aligned}&x_i = y_i, \quad i\in I^0({\varvec{y}})\cup I^1({\varvec{y}}); \end{aligned}$$

(21)

$$\begin{aligned}&x_i, x_{ij}, \delta _s \in \{0,1\},\quad i\in I^*({\varvec{y}}),\quad s\in S; \end{aligned}$$

(22)

The model (16)–(22) is further referred to as ${\mathcal {B}}({\varvec{y}})$. Inequalities (17) and (18) are taken from the problem ${\mathcal {L}}({\varvec{y}})$. Constraints (19) are the corollary of Lemma 2. Finally, the inequality (20) bounds from below the value of the second objective function of the Leader.

Notice that an appropriate choice of values $M_s$, $s\in S$, in the inequalities (19) reduces the integrality gap of the model ${\mathcal {B}}({\varvec{y}})$ and speeds up the computation of the upper bound. Given $s'\in S$, we choose the value of $M_{s'}$ by the following rule. Firstly, for each $s\in S$, we compute a primitive upper bound for the sum $\sum _{i\in I\backslash I^0({\varvec{y}})}\sum _{j\in J_s} c''_{ij}x_{ij}$ as ${\bar{C}}_s = \sum _{j\in J_s}\max _{i\in I\backslash I^0({\varvec{y}})} c_{ij}''$. Without loss of generality, let us assume that scenarios are ordered in such a way that $s' = l$ and ${\bar{C}}_1\ge {\bar{C}}_2\ge \cdots \ge {\bar{C}}_{l-1}$. Let $r\in S$ be such an index that $\sum _{s< r} p_s < p_0$ and $\sum _{s \le r} p_s \ge p_0$. If $r = l$, then all the scenarios must be active, and the big-M term is unnecessary. Otherwise, we set $M_{s'} = {\bar{C}}_r$. In the following lemma, we show that this value is the tightest one which does not affect the set of feasible solutions of the estimating problem.

Lemma 3

For any feasible solution $({\varvec{x}},{\varvec{X}},\varvec{\delta }, C)$ of the problem ${\mathcal {B}}({\varvec{y}})$ such that $\delta _{s'} = 0$, it holds $C \le {\bar{C}}_r$. There exists a feasible solution $({\varvec{x}}',{\varvec{X}}',\varvec{\delta }', C')$ of the problem ${\mathcal {B}}({\varvec{y}})$ such that $\delta _{s'} = 0$ and $C' = {\bar{C}}_r$.

Proof

From feasibility of $({\varvec{x}},{\varvec{X}},\varvec{\delta }, C)$, we have $\sum _{s \in S}p_s\delta _s \ge p_0$. Let $C_s = \sum _{i\in I}\sum _{j\in J_s}c_{ij}x_{ij}$. The following relations hold:

$$\begin{aligned} C \le \min _{s|\delta _s = 1} C_s \le \min _{s|\delta _s = 1} {\bar{C}}_s \le {\bar{C}}_r. \end{aligned}$$

The first inequality follows from (19). The second one is true due to $C_s\le {\bar{C}}_s$ for any $s\in S$. And the last relation results from $\delta _{s'}= 0$ and the choice of r.

The solution $({\varvec{x}}',{\varvec{X}}',\varvec{\delta }', C')$ from the second part of the lemma statement can be constructed directly. Let $x'_i = 1$ for all $i\in I\backslash I^0({\varvec{y}})$. Further, we set $\delta '_{s} = 1$ if $s \le r$ and $\delta '_{s} = 0$ otherwise. For $s\le r$ and any given $j\in J_s$, we set $x'_{kj} = 1$, where $k = \arg \max _{i\in I\backslash I^0({\varvec{y}})} c''_{ij}$. It is easy to see that $C' = \min _{s|\delta '_s = 1} \sum _{j\in J_s}\sum _{i\in I}c''_{ij} x'_{ij} = {\bar{C}}_r$.

$\square$

The lemmas above imply the following theorem.

Theorem 1

The optimum of the problem ${\mathcal {B}}({\varvec{y}})$ is an upper bound for the value $\max _{{\varvec{x}}, \varvec{\delta }}{\mathfrak {f}}_1({\varvec{x}}, \varvec{\delta })$, where ${\varvec{x}}\in P(y)$ and ${\mathfrak {f}}_2({\varvec{x}}, \varvec{\delta }) \ge p_0$.

3.3 Relaxation of a large MIP and a cutting-plane method

The model ${\mathcal {B}}({\varvec{y}})$ can be reformulated as a MIP with an exponential number of variables. Denote the set of all subsets of S with ${\mathcal {R}}$. For each $R\in {\mathcal {R}}$, we introduce a new boolean variable $u_R$ equal to one, if the set of active scenarios is equal to R, and zero otherwise. Additionally, we define a (0, 1)-matrix $(a_{sR})$, $s\in S$, $R\in {\mathcal {R}}$ such that $a_{sR}$ is equal to one, if $s\in R$, and zero otherwise. By using the above definitions, we can replace the variables $\delta _s$, $s\in S$, as $\delta _s = \sum _{R\in {\mathcal {R}}}a_{sR}u_R$. An additional constraint $\sum _{R\in {\mathcal {R}}} u_R = 1$, ensuring that the only set of active scenarios must be chosen, finalizes the reformulation.

Numerical experiments show that the introduced large MIP is tighter than ${\mathcal {B}}({\varvec{y}})$ in terms of integrality gap (Melnikov and Beresnev 2016). Direct solving such a large model is likely to be inefficient, but its linear relaxation can be considered as an alternative way to calculate an upper bound in a branch-and-bound scheme. We obtain an optimum of the relaxation by solving its dual problem by a cutting-plane method (Briant et al. 2008). The dual program is written as follows:

$$\begin{aligned}&\min _{(\alpha _s), (\beta _j), (\gamma _{ij}), \eta , \lambda } \left( - \sum _{i\in I^1({\varvec{y}})}f_i + \lambda - p_0\eta + \sum _{s \in S}M_s\alpha _s + \sum _{i\in I^1({\varvec{y}})} \sum _{j\in J}\gamma _{ij} \right) \end{aligned}$$

(23)

$$\begin{aligned}&\sum _{j\in J} \gamma _{ij} \le f_i,\quad i\in I^*({\varvec{y}}); \end{aligned}$$

(24)

$$\begin{aligned}&\beta _j + \gamma _{ij}\ge c''_{ij}\alpha _s, \quad i\in I\backslash I^0({\varvec{y}}),\quad s\in S,\quad j\in J_s; \end{aligned}$$

(25)

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

(26)

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

(27)

$$\begin{aligned}&\alpha _s, \beta _j, \gamma _{ij}, \eta \ge 0, i\in I\backslash I^0({\varvec{y}}), \quad s\in S,\quad j\in J. \end{aligned}$$

(28)

Let $D({\mathcal {R}}^\prime ) = \left( (\alpha _s), (\beta _j), (\gamma _{ij}), \eta , \lambda \right)$ be an optimal solution of the problem (23)–(28), where an exponentially large index set ${\mathcal {R}}$ in (27) is replaced by its relatively small subset ${\mathcal {R}}^\prime \subseteq {\mathcal {R}}$. If $D({\mathcal {R}}^\prime )$ satisfies (27) 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 $\varvec{\delta }$ such that

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

(29)

To check if there exists such a vector, we solve the following problem:

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

(30)

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

(31)

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

(32)

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

Given an optimal solution $\varvec{\delta }^*$ of the problem (30)–(32), if the inequality $\sum _{s\in S}w_s\delta ^*_s \le \lambda$ holds, then the solution $D({\mathcal {R}}')$ satisfies (27) for any $R\in {\mathcal {R}}$. Otherwise, one of constraints violated by $D({\mathcal {R}}')$ 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 (27).

Thus, the cutting-plane (CP) scheme to calculate an upper bound for the value $\max _{{\varvec{x}}, \varvec{\delta }}{\mathfrak {f}}_1({\varvec{x}}, \varvec{\delta })$ is an iterative process. On each iteration, we solve a restricted dual problem and check if its optimal solution is feasible in the initial dual problem. In the case of an affirmative answer, a valid upper bound is obtained, and the procedure terminates. Otherwise, a cut is generated by solving a knapsack-type problem (30)–(32), and a new iteration begins.

To guarantee feasibility of the restricted dual problem at the first iteration, we set ${\mathcal {R}}'$ to contain a randomly chosen subset $S'\subseteq S$ such that $\sum _{s\in S'}p_s \ge p_0$.

3.4 Equiprobable scenarios and estimating problem ${\mathcal {B}}'(y)$

The case of equiprobable scenarios, i.e., when $p_{s} = 1 / l$ for all $s \in S$, is an important case of BCompFLP arising, for instance, in sample approximations of stochastic programming problems (Shapiro 2008). Given ${\varvec{x}}$, a set of active scenarios maximizing ${\mathfrak {f}}_1({\varvec{x}},\varvec{\delta })$ contains exactly $\lceil lp_0\rceil$ elements with the greatest income. Let us introduce variables $(C_s)$, $s\in S$, storing the value of income in the corresponding scenario. The set of most profitable active scenarios can be chosen by solving the following knapsack problem:

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

(33)

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

(34)

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

(35)

Notice that this model is equivalent to its linear relaxation since the simplex method obtains an optimal solution with no fractional components. Its linear relaxation can be equivalently rewritten in the form of complementary slackness conditions (Audet et al. 1997) which are nonlinear initially. After linearizing these expressions, we introduce new constraints into the estimating problem and obtain its another reformulation ${\mathcal {B}}'({\varvec{y}})$ looking as follows:

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

(36)

$$\begin{aligned}&x_i \ge x_{ij}, \quad i\in I^*({\varvec{y}}), \quad j\in J; \end{aligned}$$

(37)

$$\begin{aligned}&\sum _{i\in I\backslash I^0({\varvec{y}})}x_{ij} \le \delta _s,\quad s\in S, \quad j\in J_s; \end{aligned}$$

(38)

$$\begin{aligned}&C_s = \sum _{i\in I\backslash I^0({\varvec{y}})}\sum _{j\in J_s} c''_{ij}x_{ij}, \quad s\in S; \end{aligned}$$

(39)

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

(40)

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

(41)

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

(42)

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

(43)

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

(44)

$$\begin{aligned}&x_i = y_i, \quad i\in I^0({\varvec{y}})\cup I^1({\varvec{y}}); \end{aligned}$$

(45)

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

(46)

Here, w and $(u_s), s\in S$ are dual variables for constraints (34) and (35), respectively. Variables $(\delta _s), s\in S$ are boolean in this model due to linearization purposes.

4 Numerical experiments

In this section, we study performance of the suggested procedures and investigate some properties of the solutions obtained by the $\varepsilon$-constraint method. Firstly, we consider a family of randomly generated instances of BCompFLP, where scenarios correspond to different variations of the transportation network. These instances are used to compare branch-and-bound methods equipped with different upper bound procedures and study a Pareto frontier of the BCompFLP. Further, we come to an important application of the BCompFLP related to the issue of stability of competitive location model’s solution with respect to perturbations of numerical data, and, namely, perturbations of the profit matrix. We concentrate on studying the question about does consideration of multiple demand scenarios help to obtain more “stable” solutions in a situation of uncertain demand parameters values.

All the calculations are performed by a workstation with two six-core processors Intel Xeon X5675 3.07 GHz and 96 GB RAM. The methods are implemented in C# programming language and get solutions of arising optimization problems from Gurobi 8.0 MIP solver (Gurobi Optimization 2016).

4.1 Instances based on transportation network variations

Consider a graph with a set of vertices divided into two disjoint non-empty subsets, $V_1$ and $V_2$. Nodes of the subset $V_1$ form a connected subgraph and represent potential locations to open facilities. The set of the customers is represented by vertices of the set $V_2$. Each vertex $v\in V_2$ has exactly four edges connecting it with randomly chosen vertices from $V_1$. Lengths of these edges are generated randomly for each of the scenarios. Preferences of the customer located in the vertex $v\in V_2$ are based on distances from v to vertices from $V_1$: The shorter the distance, the more preferable the facility located in the corresponding vertex. Thus, scenarios are different from each other only in the preferences of the customers.

Each customer $j\in J$ is assumed to have a budget $b_j$ which is the same for all the scenarios. Income from serving the customer j does not depend on the serving facility and equals $b_j$ for both the Leader and the Follower, i. e. $c_{ij} = d_{ij} = b_j$, for all $i\in I$. Values of the parameters are independently chosen with uniform distribution from the corresponding integer segments: $f_i$ from $\{7, 8, \ldots , 13\}$; $g_i$ from $\{4, 5, \ldots , 10\}$; $b_j$ from $\{1, 2, \ldots , 5\}$.

For all the generated test instances, we have $|V_2| = 30$ and 15 scenarios in total. Thus, we have a set J containing 450 customers, where each of the customers is represented by fifteen copies having different preferences resulting from variations of distance matrix corresponding to each of the scenarios.

We consider four classes of instances that differ from each other in a topology of the network formed by vertices from $V_1$. These classes are named in accordance with the topology of the network: Tree, $\hbox {Plane}_{\ell _1}$, Sphere, and Grid.

The class Tree contains instances where connections between vertices from $V_1$ form a tree. Each of the connections is represented either by a short or a long edge. The length of a short edge is an integer between 1 and 15, while the long edge’s length varies between 100 and 150. An edge is short with probability 0.9 and is long otherwise. Experiments with relative competitive location models show that this topology specifies a relatively simple structure of preferences allowing to solve instance faster (Mel’nikov 2014).

The second class considered is called $\hbox {Plane}_{\ell _1}$ because the set $V_1$ is represented by points of the unit square. The coordinates of points are chosen independently with uniform distribution. All the vertices are connected, and the length of connection is computed by $\ell _1$-metric as a sum of absolute values of coordinate differences.

Similarly to the class $\hbox {Plane}_{\ell _1}$, in the class Sphere, all the vertices from $V_1$ are connected with each other. Being represented by points of a sphere, whose polar and azimuthal angles are chosen randomly with uniform distribution, these vertices are less likely to contain “peripheral” and “internal” ones. A distance between two vertices is computed along a great circle passing through the points representing them.

Finally, in the class $\varvec{\mathrm {Grid}}$, the network organized by vertices from $V_1$ is a rectangular grid. In this structure, the vertices can be thought to be elements of a matrix. Each element is connected with its nearest neighbors located at the same column or the same row. Thus, all the vertices have up to four edges. The edges’ lengths are randomly chosen integers from 1 to 3.

Fig. 1

Network with $m=10$ vertices

Table 1 Weakly efficient solutions of the instance with $m=10$ vertices

To illustrate the model’s outcomes on instances generated, let us consider a transportation network shown in Fig. 1. It represents the connections between the ten vertices available to establish facilities forming the set $V_1$. On the base of the network, we obtain an instance from the class Tree. All the parameters’ values of the instance are generated in the manner described earlier.

Table 1 provides the characteristics of weakly efficient solutions obtained for different values of the threshold $p_0$. The right part of the table has five columns corresponding to the solutions with the value of $p_0$ given in the second row of the table header. The main part of the table is divided into 15 rows representing the demand scenarios. For each scenario s, the probability of its realization, $p_s$, and the Leader’s profit for each of the solutions are given. The profit values in active scenarios are shown in bold. In the bottom part of the table, the values of the Leader’s objective functions are given. The last row provides the vertex numbers where the Leader’s facilities are established.

Note that the Leader has no location decision that guarantees a positive profit in all the scenarios since the solution for $p_0 = 1$ is an empty one. More risky solutions may result in a higher guaranteed profit. At the same time, possible losses in non-active scenarios are not taken into account, so more risky solutions can perform better in a worst-case scenario than the less risky ones. We observe this for the solutions with $p_0 = 0.4$, where the Leader gets a negative profit of − 7, and $p_0 = 0.6$ with the profit of − 12 in the worst scenario.

4.2 Choosing the upper bound procedure

In this subsection, we aim to compare the performances of a branch-and-bound algorithm equipped with different upper bound procedures. For brevity, we refer these algorithms as $A_{\mathcal {B}}$, $A_\mathcal {B'}$, and $A_{\mathrm{CP}}$, respectively. In Melnikov and Beresnev (2016), we studied the procedures independently and concluded that the model ${\mathcal {B}}'$ performs better than ${\mathcal {B}}$ on instances with equiprobable scenarios. Additionally, the upper bound provided by CP takes less time than solving ${\mathcal {B}}$ and ${\mathcal {B}}'$, while the value obtained is more accurate than optimums of these models’ relaxations. It is necessary to mention that an optimization library Microsoft Solver Foundation 3.1 used in Melnikov and Beresnev (2016) to solve MIPs turned up to be significantly slower than the latest versions of commercial optimization software. Thus, our interest is to investigate how the suggested models perform when being installed into the branch-and-bound framework and solved by very recent optimization tools.

Table 2 Branch-and-bound: equiprobable scenarios

In Tables 2 and 3, we present results of numerical experiments with instances where scenarios have equal and randomly generated probabilities, correspondingly. The experiment was organized in the following way. For each of the classes considered, instances with $|I| = m = 9$, 16, and 25 were generated. Instances of the class Grid are based on $3\times 3$, $4\times 4$, and $5\times 5$ grids formed by vertices from $V_1$, respectively. For each instance, four values of threshold $p_0$ were considered: 0.25, 0.5, 0.75, and 1. Computations had been stopped when reaching the time limit of 30 min. The tables contain the following columns:

• $T_{\mathcal {B}}$, $T_{{\mathcal {B}}'}$, and $T_{\mathrm{CP}}$ are for computation times of $A_{\mathcal {B}}$, $A_\mathcal {B'}$, and $A_{\mathrm{CP}}$, respectively. In a case when the time limit is reached and the computations are not finished, we provide the progress of the algorithm written in italics. The progress is computed as a percentage of leaves of a branching tree that are explored by the algorithm.

• $N_{\mathcal {B}}$, $N_{{\mathcal {B}}'}$, and $N_{\mathrm{CP}}$ are for the total number of nodes of the branching tree explored by the corresponding algorithm.

• Opt is for the optimal value of the function ${\mathfrak {f}}_1$; for instances which are not solved by some of the algorithms, we give the best objective value obtained. The modification of the method delivered this value is given in brackets when the methods were terminated with different results.

• B is an initial upper bound value computed by $A_{{\mathcal {B}}}$ and $A_{\mathcal {B'}}$.

• CP is an initial upper bound value computed by $A_{\mathrm{CP}}$.

Table 3 Branch-and-bound: scenarios with different probabilities

As we can see from Tables 2 and 3, the structure of the graph specifying customers preferences significantly affects computational time needed to solve the instance. Similarly to the previously studied competitive location models (Mel’nikov 2014), instances based on trees are simpler than the ones based on graphs with higher connectivity. Oppositely, grids and similar regular graph structures induce instances that are more difficult for our approach because the intricate structure of preferences makes the upper bound computed by using the models based on estimating subsets overly optimistic.

Another general observation considers the role of the parameter $p_0$. For all the considered instances, the case $p_0 = 1$ is the simplest one. One of the reasons for this is that big-M terms vanish from the estimating problem formulations in this case. The enumeration speeds up due to a faster computation of the upper bound. Additionally, the method, using CP to calculate the upper bound, shows itself more competitive for these instances.

When analyzing Table 2, one would notice that the difference between the upper bounds presented in columns B and CP is significant. The value provided by CP is around two times higher than the one provided by MIP. It results in a weak performance of the branch-and-bound equipped with CP. For $\varvec{\mathrm {Grid}}$ instances with $m = 9$ and $p_0 = 0.25$, 0.5, $A_{\mathrm{CP}}$ explores around seven hundreds of nodes which is more than the total number of possible location decisions. Another notable effect is that the number of nodes explored by CP is significantly higher than the one explored by ${\mathcal {B}}$ and $\mathcal {B'}$ for the class Tree. For other classes, which are more difficult in terms of computational time, the situation is the opposite. It results from the behavior of the cutting-plane method which needs fewer iterations to converge when the structure of preferences is relatively simple. $A_{{\mathcal {B}}}$ and $A_{{\mathcal {B}}'}$ perform similarly, and the data do not give priority to any of them.

In Table 3, scenarios with different probabilities of realization were considered. To generate the probabilities, we choose at random a set of integers $\{\rho _s\}$ from the interval $\{1, \ldots , 4\}$. For the scenario $s\in S$, we set $p_s = \rho _s/\sum _{s \in S}\rho _s$. The model ${\mathcal {B}}'$ cannot be applied in this situation, and our goal is to compare ${\mathcal {B}}$ and CP with each other. As we can see, the key points regarding performances of the methods noted from the analysis of Table 2 stay the same in a case of different probabilities. Thus, the modification $A_{{\mathcal {B}}}$ showed itself the most universal and capable among the considered ones, and the following computations are performed using this tool.

4.3 Dealing with uncertainty in the CompFLP model

The model BCompFLP provides a rich set of instruments for making a decision in a situation of uncertainty. Let us back to the basic CompFLP model (Beresnev 2014), which can be regarded as BCompFLP with a single scenario. In the benchmark library (Discrete location problems 2018), a series of instances of CompFLP with known optimal solutions is collected. Our interest in this subsection is to investigate what happens with these solutions when the elements of the profit matrix slightly change, and how the BCompFLP model can support decisions when profits are stochastic.

Consider the class of instances A20 from Discrete location problems (2018). There, similarly to previously introduced instances, both the set of customers and the set of potential facility locations are represented by vertices of a randomly generated graph. The Leader’s fixed costs are set to 40 for all $i\in I$, whereas the Follower’s ones are randomly chosen from 25 to 35. Instances have names of a form ‘a20-xx,’ where the postfix ‘xx’ is formed by an individual number of instance.

In the class A20, profit matrices of both players are equal, i. e. $c_{ij} = d_{ij}$ for all $i\in I$, $j\in J$, and their elements are taken from the integer interval $\{10, \ldots , 20\}$. Let us assume these elements are determined with an accuracy of 10%. To take into account possible variations of these parameters, we generate a list of scenarios where the same set of customers is attributed to different realizations of the profit matrix. Given the facility i and the customer j, we set the corresponding value of the profit matrix to a random positive integer from the interval $[0.9 c_{ij},~1.1 c_{ij}]$ independently for each of the scenarios.

In our experiments, we considered instances of BCompFLP with 10, 15, and 20 realizations of the profit matrix (scenarios), whereas the total number of possible variations is sufficiently higher. Each of these variations determines the value of the Leader’s profit provided that the Follower’s reaction is rational. Thus, each Leader’s decision on facilities’ location is characterized by a distribution of the profit value. To express this distribution, given the Leader’s location, we sample $\nu = 1000$ variations of the profit matrix and compute the corresponding value of the Leader’s profit.

The graphs in Fig. 2 show the profit distribution for five solutions computed by the $\varepsilon$-constraint method for $p_0 = 0.2$, 0.4, 0.6, 0.8, and 1. The value of $p_0$ is shown on the horizontal axis, whereas the vertical axis corresponds to the profit value.

A distribution is visualized by both a box and a violin-type plots. Boxes’ whiskers show minimal and maximal value among $\nu$ computed values of the profit. Lower and upper sides of a box show the first and the third quartile for this set of values. Finally, a band inside a box represents a median value. A general look of a distribution function is shown by shaded vertically oriented shapes, where thicker parts of a shape correspond to more probable values of profit.

Fig. 2

Distribution of the Leader’s profit for solutions obtained for different values of $p_0$

On the figures, two line graphs are depicted as well. The light-gray line shows the value ${\mathfrak {f}}^*_1(p_0)$ which is an optimal value of ${\mathfrak {f}}_1$ in the BCompFLP model with ${\mathfrak {f}}_2\ge p_0$. To compare this value with the real value of the profit guaranteed with a probability $p_0$, we added a dark-gray line showing the value ${\mathfrak {f}}^\nu _1(p_0)$ which is the $\lceil (1 - p_0)\nu \rceil$-th-order statistic for a set of profit values computed for $\nu$ sampled profit matrices.

From the graphs presented, we notice that the density function of ${\mathfrak {f}}_1$ is often multimodal. Given the Leader’s location, the optimal solution of the Follower and, consequently, the set of customers captured by the Leader depend on the realization of the profit matrix. For the numerical data under consideration, the function ${\mathfrak {f}}_1$ takes similar values for variations of the profit matrix inducing the same optimal solution of the Follower. At the same time, changing the Follower’s solution may influence ${\mathfrak {f}}_1$ heavily. It results in that the shape of the distribution is represented by several clusters. Values from the same cluster correspond to a single location of the parties and differ from each other due to deviations of the profit matrix.

Distribution of the profit value tends to be more concentrated for solutions obtained with higher $p_0$. At the same time, these solutions are often less preferable than ones computed for lower $p_0$. It is true for the instance a20-01, 10 scenarios, $p_0 = 1$, for a20-04, 20 scenarios, $p_0 = 1$, and in several other cases. We suppose that here we observe a phenomenon similar to so-called overfitting in the machine learning area. It manifests itself in that the solution strongly adapts to the specific of the numeric data appeared in the scenarios considered and performs worse on the data unseen before.

One could suggest that ${\mathfrak {f}}^*_1(p_0)$ converges to $\lim _{\nu \rightarrow +\infty }{\mathfrak {f}}^\nu _1(p_0)$ when the number of scenarios considered in the BCompFLP model tends to infinity. The graphs support this suggestion. Comparison of the graphs built for a different number of scenarios shows that the convergence rate decreases when $p_0$ grows. The values ${\mathfrak {f}}^*_1(p_0)$ and ${\mathfrak {f}}^\nu _1(p_0)$, represented by light and dark lines, respectively, tend to be closer for smaller $p_0$ and could differ significantly for $p_0$ close to one. The question of convergence of the sample average approximation to the actual solution of the stochastic model with expectation objective function is considered in Shapiro (2008). To our knowledge, the case of quantile objective function remains unstudied.

5 Conclusion

In this paper, we considered a competitive location model BCompFLP where the Leader makes a decision in a situation where multiple demand scenarios are possible. It allows taking into account uncertainty in all the aspects characterizing the demand such as the number of customers, their preferences, and income from serving them. We formulate the Leader’s problem as a bi-objective bi-level program aiming to maximize both the Leader’s profit and the probability to get it. Efficient solutions of the model provide information about trade-offs between revenues and risks as well as about regrets which are possible in concrete circumstances. Thus, BCompFLP is a powerful tool supporting a decision-making process in situations meeting assumptions of the model.

To approximate the Pareto frontier of the problem, we developed an $\varepsilon$-constraint method providing a subset of weakly efficient solutions. In the method, a series of bi-level problems with a single objective is solved by a branch-and-bound algorithm. Three upper bound procedures built on the basis of a specially constructed estimating problem in a form of MIP were built in the algorithm and compared with each other in numerical experiments.

Further, we performed a series of experiments aiming to investigate relationships between the stochastic competitive location problem with uncertain profits and its sample approximation that can be written as a BCompFLP. The data show that the value of guaranteed profit in the sample approximation BCompFLP converges to the corresponding profit value in the stochastic model. At the same time, the number of scenarios that are to be included in the BCompFLP model depends on the probability $p_0$ of obtaining the guaranteed profit. The higher $p_0$, the more scenarios are needed to get a good approximation of the guaranteed profit.

Another effect observed in our experiments is analogous to overfitting in the machine learning area. It manifests itself in that solutions obtained for high probability $p_0$ are sometimes worse in terms of profit distribution than the ones corresponding to lower $p_0$. As an instance, a location obtained for $p_0 = 1$ exploits all the specific of scenarios when aiming to optimize the profit in all of them. It leads to a decrease in the profit in unseen scenarios and worsening the profit distribution.

Our future research is oriented on developing models for stochastic competitive location and methods to solve them.