Keywords

1 Introduction

In contrast to the classical location problem [9] models of competitive location consider several competing parties [4–6, 10]. The parties simultaneously or sequentially open their facilities with the aim to optimize personal objective functions. The goals of the competitors are associated with the customers capture and satisfying their demands. There is a number of customer behavior models resulting from the characteristics of the demand and other factors [13]. We assume that the customer capture is based on his preferences. They are assumed to be known for both parties.

In our model, we consider the competition of two sides that open their facilities sequentially. The decision making process can be considered as a Stackelberg game [15]. The formalization of this kind of games can be done in a natural way in terms of bilevel programming [8]. According to the game terminology the party that opens its facilities first will be referred to as Leader. The second party that opens its facilities knowing Leader’s decision will be referred to as Follower.

In the present work, we deal with the model of competitive location where in contrast to models from [4–6] Follower is able to close Leader’s facilities by using discrediting, black PR and other methods of unfair competition.

The Leader’s aim in this competition is to open such a set of facilities that brings maximum profit provided that Follower can close some of Leader’s facilities and capture some customers. Follower’s goal is to maximize profit as well. Follower decides which Leader’s facilities are to be closed and where to open own facilities.

First publications considering bilevel location models with opportunity of closing or destructing of the facilities appeared in 2008. In [14] authors formulate the model of interdiction median problem with fortification (RIMF), where one party called a defender commits resources to protect facilities serving customers from the rational attack of another party. The authors investigate properties of the model and suggest an enumeration scheme to obtain an optimal defender’s solution. Further developments of the model can be found in [1, 11, 16] where stochastic generalizations of the model are considered. Other models of protection against the rational attack are investigated in [2, 3].

An important feature of our model is necessity of a revision of the feasibility definition. The most common concepts of feasibility for bilevel programming problems are optimistic and pessimistic solutions. In the present work we focus on the problem of finding a pessimistic optimal solution. The suggested approach is based on the ideas developed and approved in [4, 6]. The first point is representation of the Leader’s problem in the form of pseudo–Boolean function maximization. The number of variables the function depends on is equal to the number of places available for facility opening. The representation allows implementing inexact methods of search in a Boolean cube such as local search and its modifications. The second important point is calculation of an upper bound for the values the function takes on subsets specified by partial (0,1)–vectors. It allows developing an implicit enumeration scheme proved to be effective when applied to previously studied models.

In this paper, we show that given values of the Leader’s location variables the problem of finding a pessimistic feasible solution is reduced to mixed–integer programming problem. This implies that the required pseudo–Boolean function can be constructed. By using the approach from [4, 6] we define a modified system of evaluating subsets, which allow to formulate sufficient conditions of capturing the customer by Follower. This conditions written in a form of linear inequalities, are used as valid inequalities for strengthening the bilevel model. The relaxation of the strengthened model by removing the lower–level problem provides an upper bound for the optimal value of the pseudo–Boolean function.

The paper is organized as follows. In Sect. 1 we propose the model of the facility location in unfair competition in the form of a bilevel integer programming problem. Section 2 is devoted to the problem of finding a pessimistic feasible solution of the model. A reduction to a pseudo–Boolean function maximization problem is discussed as well. In Sect. 3 we construct an estimating problem providing an upper bound for the optimal value of the pseudo–Boolean function.

2 Mathematical Model

Let us introduce the necessary notations.

Index sets:

\(I=\{1,\ldots ,m\}\) is a set of locations (candidate sites for opening facilities);

\(J=\{1,\ldots ,n\}\) is a set of customers.

Parameters:

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

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

\(G_i\) is a cost of closing a Leader’s facility \(i \in I\);

\(p_{ij}\) is a profit of Leader’s facility \(i\in I\) obtained from a customer \(j \in J\);

\(q_{ij}\) is a profit of Follower’s facility \(i\in I\) obtained from a customer \(j \in J\);

Variables:

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

\( z_i=\left\{ \begin{array}{l} 1, \text { if Follower opens facility }i \\ 0, \text { otherwise, } \end{array}\right. \)

\( s_i=\left\{ \begin{array}{l} 1, \text { if Follower closes Leader's facility } i\\ 0, \text { otherwise, } \end{array}\right. \)

\( x_{ij} = \left\{ \begin{array}{l} 1, \text { if Leader's facility }i \text { serves the customer } j\\ 0, \text { otherwise, } \end{array}\right. \)

\( z_{ij} = \left\{ \begin{array}{l} 1, \text { if Follower's facility } i \text { serves the customer } j\\ 0, \text { otherwise. } \end{array}\right. \)

We assume that the preferences of a customer \(j\in J\) are represented with a linear order \(\succeq _j\) on the set I. The relation \(i_1\succeq _j i_2\) shows that either facility \(i_1\) is more preferable for j than \(i_2\), or \(i_1 = i_2\). If \(i_1\ne i_2\) and \(i_1\succeq _j i_2\), we use denotation \(i_1\succ _j i_2\).

Given \(j\in J\), we denote the greatest element of a nonempty set \(K\subseteq I\) according to the order \(\succeq _j\) with \(i_j(K)\). In other words, \(i_j(K)\) is a \(i\in K\) such that \(i \succeq _j k\) for all \(k\in K\). For a nonzero Boolean vector \(x = (x_i)\), \(i\in I\) we assume that \(i_j(x) = i_j(\{i\in I|x_i = 1\})\).

It is assumed that a customer is captured by the party that opens the most preferable facility for him. Moreover, the party is able to serve the captured customer only with a facility that is more preferable for him than any competitor’s facility. If Boolean vectors x and z correspond to Leader’s and Follower’s facilities locations respectively, then Leader’s facility \(i\in I\) can serve 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)\).

Now we can formulate the model of facility location in unfair competition in terms of bilevel integer programming:

$$\begin{aligned} \max _{(x_i),(x_{ij})}\min _{(\tilde{z}_i), (\tilde{z}_{ij}), (\tilde{s}_i)}\left( -\sum _{i\in I}f_ix_i+\sum _{j\in J}\sum _{i\in I}p_{ij}x_{ij}\right) , \end{aligned}$$
(1)
$$\begin{aligned} \tilde{z}_i+\sum _{k\mid i\succeq _jk}x_{kj}\le 1, \quad i\in I, \quad j\in J; \end{aligned}$$
(2)
$$\begin{aligned} x_i-\tilde{s}_i\ge x_{ij}, \quad i\in I,\quad j\in J; \end{aligned}$$
(3)
$$\begin{aligned} x_i, x_{ij} \in \{0,1\}, \quad i\in I,\quad j\in J; \end{aligned}$$
(4)
$$\begin{aligned} \text {where }(\tilde{z}_i), (\tilde{z}_{ij}), (\tilde{s}_i) \text { solves} \end{aligned}$$
(5)
$$\begin{aligned} \max _{(z_i),(z_{ij}),(s_i)}\Big \{-\sum _{i\in I}G_is_i-\sum _{i\in I}g_iz_i+\sum _{j\in J}\sum _{i\in I}q_{ij}z_{ij}\Big \}, \end{aligned}$$
(6)
$$\begin{aligned} x_i-s_i+z_i\le 1,\quad i\in I; \end{aligned}$$
(7)
$$\begin{aligned} x_i\ge s_i,\quad i\in I; \end{aligned}$$
(8)
$$\begin{aligned} x_i-s_i+\sum _{k\mid i\succeq _jk}z_{kj}\le 1, \quad i\in I, \quad j\in J; \end{aligned}$$
(9)
$$\begin{aligned} z_i\ge z_{ij}, \quad i\in I,\quad j\in J; \end{aligned}$$
(10)
$$\begin{aligned} z_i, z_{ij}, s_i \in \{0,1\}, \quad i\in I, \quad j\in J. \end{aligned}$$
(11)

We denote the upper–level problem (1)–(5) with \(\mathcal {L}\) and the lower–level problem (6)–(11) with \(\mathcal F\). The problem (1)–(11) is denoted by \((\mathcal L,\mathcal F)\).

Leader’s objective function (1) expresses the value of his profit and consists of two components. The first one is the cost of facilities to be opened, and the second summand represents the income collected by them. We assume that in the cases when the problem \(\mathcal F\) has several optimal solutions Follower plays against Leader and chooses the solution that minimizes (1). Constraints (2) ensure that Leader serves the customer with a facility which is more preferable for the customer than any Follower’s facility. In addition, these constraints ensure that the customer is served with no more than one Leader’s facility. Constraints (3) guarantee that customers are served with open facilities. Follower’s problem \(\mathcal F\) has a similar form. Additional term in Follower’s objective function (6) equals to the cost of closing Leader’s facilities. Constraints (7) ensures that Follower’s facility can be opened only in a location without Leader’s one, and constraints (8) allow to close only the Leader’s facility which is open.

3 Pessimistic Feasible Solutions

A pair \((X,\tilde{Z})\) is called a feasible solution of the problem \((\mathcal L,\mathcal F)\) if \(X=((x_i),(x_{ij}))\) is a feasible solution of the problem \(\mathcal L\) with given \(\tilde{z}=(\tilde{z}_i)\), \(\tilde{s}=(\tilde{s}_i)\), and \(\tilde{Z}=((\tilde{z}_i),(\tilde{z}_{ij}),(\tilde{s}_i))\) is an optimal solution of the problem \(\mathcal F\) with given \(x=(x_i)\).

Denote the value of objective function (6) on a feasible solution Z of the problem \(\mathcal {F}\) with F(Z) and the value of objective function (1) on a feasible solution \((X,\tilde{Z})\) of the problem \((\mathcal {L}, \mathcal {F})\) with \(L(X,\tilde{Z})\).

Given values of variables \(x=(x_i)\), \(i\in I\), let us select “good” Leader’s solutions among all feasible solutions \((X,\tilde{Z})\) of the problem \((\mathcal L,\mathcal F)\). We call a feasible solution \((\tilde{X},\tilde{Z})\), \(\tilde{X}=((x_i),(\tilde{x}_{ij}))\) strong if \(L(\tilde{X},\tilde{Z})\ge L(X,\tilde{Z})\) for every feasible solution \((X,\tilde{Z})\), where \(X=((x_i), (x_{ij}))\). It is clear that a feasible solution \((\tilde{X},\tilde{Z})\), \(\tilde{X}=((x_i), (\tilde{x}_{ij}))\) is strong if for all \(j\in J\) holds

$$ \sum _{i\in I}p_{ij}\tilde{x}_{ij}=\max _{k|k\succ _j i_j(\tilde{z})} p_{kj}(x_k-\tilde{s}_k), $$

where maximum over an empty set is assumed to be equal to zero.

We say that a strong feasible solution \((\bar{X},\bar{Z})\) of the problem \((\mathcal L,\mathcal F)\), where \(\bar{X}=((x_i),(\bar{x}_{ij}))\), is pessimistic, if \(L(\bar{X},\bar{Z})\le L(\tilde{X},\tilde{Z})\) for each strong feasible solution \((\tilde{X},\tilde{Z})\), \(\tilde{X}=((x_i),(\tilde{x}_{ij}))\). A pessimistic feasible solution \((X^*, Z^*)\) of the problem \((\mathcal L,\mathcal F)\) is called a pessimistic optimal solution if \(L(X^*, Z^*)\ge L(\bar{X}, \bar{Z})\) for each pessimistic feasible solution \((\bar{X}, \bar{Z})\).

Given a Boolean vector \(x=(x_i)\), \(i\in I\), consider the problem of finding a pessimistic feasible solution \((\bar{X},\bar{Z})\), \(\bar{X}=((x_i),(\bar{x}_{ij}))\) of the problem \((\mathcal {L},\mathcal {F})\). This solution can be computed in two steps.

At the first step given a vector x solve the problem \(\mathcal F\) and get an optimal value \(F^*\) of its objective function. At the second step solve the following auxiliary problem. To formulate it we introduce new variables \(u_j, j\in J\). The variable \(u_j\) takes the value of the maximum profit Leader gets from serving the customer j.

The aforementioned problem is formulated as follows:

$$\begin{aligned} \min _{(z_i),(z_{ij}),(s_i), (u_j)}\sum _{j\in J}u_j \end{aligned}$$
(12)
$$\begin{aligned} x_i-s_i+z_i\le 1,\quad i\in I; \end{aligned}$$
(13)
$$\begin{aligned} x_i\ge s_i,\quad i\in I; \end{aligned}$$
(14)
$$\begin{aligned} x_i-s_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_i\ge z_{ij}, \quad i\in I,\quad j\in J; \end{aligned}$$
(16)
$$\begin{aligned} u_j\ge p_{ij}(x_i-s_i-\sum _{k\mid k\succ _ji}z_k),\quad i\in I, \quad j\in J; \end{aligned}$$
(17)
$$\begin{aligned} -\sum _{i\in I}G_is_i-\sum _{i\in I}g_iz_i+\sum _{j\in J}\sum _{i\in I}q_{ij}z_{ij}\ge F^*; \end{aligned}$$
(18)
$$\begin{aligned} z_i, z_{ij}, s_i \in \{0,1\}, \quad i\in I, \quad j\in J; \end{aligned}$$
(19)
$$\begin{aligned} u_i\ge 0, \quad j\in J. \end{aligned}$$
(20)

Let \((\bar{Z},\bar{U})\), \(\bar{Z}=((\bar{z}_i),(\bar{z}_{ij}), (\bar{s}_i))\), \(\bar{U}=(\bar{u}_j)\) be an optimal solution of the problem (12)–(20), and let \(\bar{z}=(\bar{z}_i)\). Notice that for solution \((\bar{Z},\bar{U})\) the following equality holds for each \(j\in J\):

$$ \bar{u}_j=\max _{i\mid i\succ _j i_j(\bar{z})}\big \{p_{ij}(x_i-\bar{s}_i)\big \}. $$

Now we are able to construct a strong feasible solution \((\bar{X},\bar{Z})\), \(\bar{X}=((x_i),(\bar{x}_{ij}))\) of the problem \((\mathcal L,\mathcal F)\) corresponding to \((\bar{Z},\bar{U})\). For \(j\in J\) such that \(\bar{u}_j>0\) let us denote by \(i_j\) the index \(i\in I\) for which the constraint (17) is active. Then for \(i\in I, j\in J\) we set

$$ \bar{x}_{ij}=\left\{ \begin{array}{ll} 1, &{} \text { if } \bar{u}_j>0 \text { and } i=i_j \\ 0 &{} \text { otherwise } \end{array} \right. . $$

Notice that \((\bar{X},\bar{Z})\) is a strong feasible solution of the problem \((\mathcal L,\mathcal F)\). In addition, observe that \(\bar{u}_j=\sum \limits _{i\in I} p_{ij}\bar{x}_{ij}, j\in J\).

Theorem 1

Given (0,1)–vector \(x = (x_i)\), \(i\in I\), if \((\bar{Z},\bar{U})\), \(\bar{Z}=((\bar{z}_i),(\bar{z}_{ij}), (\bar{s}_i))\), \(\bar{U}=(\bar{u}_j)\) is an optimal solution of the problem (12)–(20), then the solution \((\bar{X},\bar{Z})\), \(\bar{X}=((x_i),(\bar{x}_{ij}))\) of the problem \((\mathcal L,\mathcal F)\), corresponding to \((\bar{Z},\bar{U})\) is a pessimistic feasible solution of the problem \((\mathcal L,\mathcal F)\).

Proof

Let \((\tilde{X}, \tilde{Z})\), \(\tilde{X}=((x_i),(\tilde{x}_{ij}))\), \(\tilde{Z}=((\tilde{z}_i), (\tilde{z}_{ij}), (\tilde{s}_i))\) be a strong feasible solution of the problem \((\mathcal L,\mathcal F)\). Set \(\tilde{z}=(\tilde{z}_i)\) and

$$ \tilde{u}_j=\sum _{i\in I}p_{ij}\tilde{x}_{ij},\quad j\in J. $$

Since \((\tilde{X}, \tilde{Z})\) is a strong feasible solution, then

$$ \tilde{u}_j=\max _{i\mid i\succ _ji_j(\tilde{z})}p_{ij}(x_i-\tilde{s}_i), \quad j\in J. $$

Consequently, \((\tilde{Z}, \tilde{U})\), \(\tilde{U}=(\tilde{u}_i)\) is a feasible solution of the problem (12)–(20). We get

$$ \sum _{j\in J}\sum _{i\in I}p_{ij}\tilde{x}_{ij}=\sum _{j\in J}\tilde{u}_j\ge \sum _{j\in J}\bar{u}_j=\sum _{j\in J}\sum _{i\in I}p_{ij}\bar{x}_{ij}. $$

It follows that \(L(\bar{X},\bar{Z})\le L(\tilde{X}, \tilde{Z})\), and the Theorem 1 is proved.

Since any (0,1)–vector x defines the value of objective function (1) on the corresponding pessimistic feasible solution, then the problem \((\mathcal {L}, \mathcal {F})\) can be considered as a pseudo–Boolean function maximization problem. This function f depends on m Boolean variables and for every vector of Leader’s locations gives the value of Leader’s profit.

4 Upper Bound

Consider the problem of computing an upper bound for values of the aforementioned pseudo–Boolean function f(x), \(x\in \{0,1\}^m\). Our goal is to modify the approach from [4, 6] and apply it to the problem under investigation. The method consists in strengthening of the initial bilevel problem with some additional constraints satisfied by all pessimistic feasible solutions. The relaxation of the strengthened model by removing the lower–level problem provides a valid upper bound.

Valid inequalities for the problem \((\mathcal {L}, \mathcal {F})\) utilize a specially constructed system of subsets \(\{I_j\}\), \(j\in J\). Our goal is to form a nontrivial subset \(I_j\) for each \(j\in J\) such that in the case, when the most preferable for \(j_0\in J\) Leader’s facility is not in \(I_{j_0}\), then \(j_0\) does not bring profit to Leader. Given \(j_0\in J\), let us formulate the rule to determine if an arbitrary \(i\in I\) is in the subset \(I_{j_0}\) or not.

Consider the set \(N(i)=\{k\in I\mid k\succ _{j_0}i\}\) of facilities more preferable for \(j_0\) than i and its superset \(\bar{N}(i)=N(i)\cup \{i\}\). The set

$$ J(i)=\{j\in J \mid i = i_{j}(I\backslash N(i))\} $$

contains customers for which all the facilities that are more preferable than i are contained in N(i). Since \(j_0\in J(i)\), then \(J(i)\ne \emptyset \).

For each \(k\in N(i)\) denote the subset of J(i) that can be captured by k by

$$ J_1(i,k)=\{j\in J(i)\mid k = i_j((I\backslash N(i))\cup \{k\})\}, $$

and for each \(k\in \bar{N}(i)\) the subset of J(i) that can be captured by k after closing the facility i by

$$ J_2(i,k)=\{j\in J(i)\mid k = i_j((I\backslash \bar{N}(i))\cup \{k\})\}. $$

Suppose that \(i\notin I_{j_0}\) if there exists \(k\in N(i)\) such that

$$ \sum \limits _{j\in J_1(i,k)}q_{kj}\ge g_k, $$

or if there exists \(k\in \bar{N}(i)\) such that \( \sum \limits _{j\in J_2(i,k)}q_{kj}\ge g_k+G_i \). Otherwise we assume that \(i\in I_{j_0}\).

Lemma 1

Let \((\bar{X},\bar{Z})\), \(\bar{X}=((\bar{x}_i),(\bar{x}_{ij}))\), \(\bar{Z}=((\bar{z}_i),(\bar{z}_{ij}),(\bar{s}_i))\) be a pessimistic feasible solution of the problem \((\mathcal L, \mathcal F)\) and \(\{I_j\}\) be a system of estimating subsets. For each \(j_0\in J\) the following holds: if \(i_{j_0}(\{i\in I| \bar{x}_i - \bar{s}_i = 1\})\notin I_{j_0}\), then \(\sum \limits _{i\in I}p_{ij_0}\bar{x}_{ij_0}=0\).

Proof

Consider (0,1)–vectors \(\bar{x}-\bar{s}=(\bar{x}_i-\bar{s}_i)\), \(i\in I\) and \(\bar{z}=(\bar{z}_{i})\), \(i\in I\). If \(\bar{x}-\bar{s} = 0\), then from (3) we obtain the required. Otherwise, set \(i_x=i_{j_0}(\bar{x}-\bar{s})\). Assume that \(i_x\notin I_{j_0}\) and consider the set \(N(i_x)=\{i\in I|i\succ _{j_0}i_x\}\). If \(N(i_x)\ne \emptyset \) and \(\sum _{i\in N(i_x)}\bar{z}_i > 0\), then from (2) and (3) we get \(\sum \limits _{i\in I}\bar{x}_{ij_0}=0\).

Otherwise, consider the set \(J(i_x)=\{j\in J| i_x = i_j(I\backslash N(i_x))\}\). Since \((\bar{x}_i-\bar{s}_i)=\bar{z}_i=0\) for all \(i\in N(i_x)\), then \(i_j(\bar{x}-\bar{s})\succ _j i_j(\bar{z})\) for each \(j\in J(i_x)\). From \(i_x\notin I_{j_0}\) we get two possibilities:

(1) there exists \(k\in N(i_x)\) such that for \(J_1(i_x,k)\) we have \(\sum \limits _{j\in J_1(i_x,k)}q_{kj}\ge g_k\);

(2) there exists \(k\in \bar{N}(i_x)\) such that for \(J_2(i_x,k)\) we have \(\sum \limits _{j\in J_2(i_x,k)}q_{kj}\ge g_k+G_{i_x}\).

In the first case we can construct a new feasible solution \(Z=((z_i), (z_{ij}), (s_i))\) of the problem \(\mathcal F\) which differs from the optimal solution \(\bar{Z}\) only in that \(z_k=1\) and \(z_{kj}=1\) for \(j\in J_1(i_x, k)\).

For solutions Z and \(\bar{Z}\) the following inequality holds:

$$ F(Z)-F(\bar{Z})=-g_k+\sum _{j\in J_1(i_x,k)}q_{kj}\ge 0. $$

If this inequality is strict we have a contradiction with optimality of \(\bar{Z}\). If \(\sum \limits _{i\in I}p_{ij_0}\bar{x}_{ij_0}>0\) the replacement of the optimal solution \(\bar{Z}\) of the problem \(\mathcal {F}\) with a feasible solution Z does not reduce the objective function of the lower–level problem but reduces the upper–level one. It contradicts with the fact that \((\bar{X}, \bar{Z})\) is a pessimistic feasible solution.

In the second case we construct a feasible solution \(Z=((z_i), (z_{ij}), (s_i))\) of the problem \(\mathcal F\), which differs from \(\bar{Z}\) only in that \(z_k=1\), \(z_{kj}=1\) for \(j\in J_2(i_x,k)\), and \(s_{i_x}=1\). For the lower–level objective function, we have:

$$ F(Z)-F(\bar{Z})=-g_k-G_{i_x}+\sum _{j\in J_2(k,i_x)}q_{kj}\ge 0. $$

By repeating the argument for the first case we get the Lemma 1 proved.

Corollary 1

Let \((\bar{X},\bar{Z})\) be a pessimistic feasible solution of the problem \((\mathcal L, \mathcal F)\) and \(\{I_j\}\) is a system of estimating subsets. There exists a pessimistic feasible solution (X, Z), \(X=((x_i),(x_{ij}))\), \(Z=((z_i),(z_{ij}),(s_i))\) of the problem \((\mathcal L, \mathcal F)\) such that \(L(X,Z) = L(\bar{X},\bar{Z})\) and for each \(j\in J\) the following inequality holds:

$$\begin{aligned} \sum _{i\in I}x_{ij}\le \sum _{i\in I_j}x_{i}. \end{aligned}$$
(21)

Proof

Set (X, Z) to be equal to \((\bar{X}, \bar{Z})\). If the right hand side of (21) is positive, then (21) results from the constraints (2).

If for some \(j\in J\) we have \(x_i = 0\) for all \(i\in I_j\) then Lemma 1 can be applied. Indeed, in this case \(i_j(\{i\in I|x_i - s_i = 1\})\not \in I_j\) and thus \(\sum \limits _{i\in I}p_{ij}x_{ij}=0\). By setting \(x_{ij} = 0\) for all \(i\in I\) we get the required.

Consider the following problem, which we refer to as estimating problem for \((\mathcal L,\mathcal F)\). It is obtained from the problem \((\mathcal L, \mathcal {F})\) by adding the constraints (21) and removing the lower–level objective function. From Corollary 1 we conclude that the first modification does not change the optimal value of the objective function. The second modification increases the feasible region by relaxing the constraints on the lower–level variables to get values from the set of optimal solutions. Obviously, after this relaxation all lower–level variables can be set to be equal to zero. This allows us to remove them as well. Finally, the estimating problem is written as follows:

$$ \max _{(x_i),(x_{ij})}\Big \{-\sum _{i\in I}f_ix_i+\sum _{j\in J}\sum _{i\in I}p_{ij}x_{ij}\Big \}, $$
$$ \sum _{i\in I}x_{ij}\le 1,\quad j\in J; $$
$$ x_{ij}\le x_i,\quad i\in I, j\in J; $$
$$ \sum _{i\in I}x_{ij}\le \sum _{i\in I_j}x_i,\quad j\in J; $$
$$ x_i, x_{ij}\in \{0,1\},\quad i\in I, j\in J. $$

Denote the value of its objective function on the feasible solution \(X=((x_i),(x_{ij}))\) with B(X). Let \(X^0=((x^0_i),(x^0_{ij}))\) be an optimal solution of the estimating problem.

Theorem 2

Let \(X^0\) be an optimal solution of the estimating problem. For each pessimistic feasible solution of the problem \((\mathcal L,\mathcal F)\) the following inequality holds: \(L(\bar{X},\bar{Z})\le B(X^0)\).

Proof

Let \((\bar{X}^*, \bar{Z}^*)\) be a pessimistic optimal solution of the problem \((\mathcal L,\mathcal F)\). From the Corollary 1 we conclude that there exists a pessimistic feasible solution \((X^*, Z^*)\) satisfying (21) and such that \(L(X^*, Z^*) = L(\bar{X}^*, \bar{Z}^*)\). Since the value \(B(X^0)\) is an optimal value of the estimating problem, which is a relaxation of the problem \((\mathcal {L}, \mathcal {F})\) with additional constraint (21), we have \(B(X^0) \ge L(X^*, Z^*)\). The Theorem 2 is proved.

Thus computing the upper bound for the pseudo–Boolean function f(x) consists in solving a single–level mixed–integer programming problem.

5 Conclusions and Future Research

In this paper, we have introduced a new model of competitive facility location, which belongs to the class of Stackelberg games. Players called Leader and Follower maximizes their profit obtained from customers serving with deduction of the fixed costs of facilities opening. The model of customers’ behavior assumes that customer is captured by the side which opens the most preferable facility for him or her. The novelty of the model consists in ability of Follower to close Leader’s facility by paying some known price. It models the situation of unfair competition where discrediting and other forms of dishonest activities can be applied to Leader’s facilities in order to force them to close.

We propose the method to construct a pessimistic feasible solution corresponding to Boolean vector, representing Leader’s facilities location. Consequently, the Leader’s problem can be represented in a form of pseudo–Boolean function maximization. It allows to construct local search based methods and apply a large pool of metaheuristic schemes [7, 12] to obtain approximate solutions of the problem in reasonable time.

The proposed upper bound can be utilized in estimation of the inexact methods effectiveness. Valid inequalities presented by the Corollary 1 strengthen the formulation of the problem and can increase the convergence rate of bilevel solvers to come. Due to proximity of the estimating problem and the Leader’s problem, the optimal solution of the first one can be taken as a starting point of the search.

The next step of our research is incorporation of the fixed values of Leader’s location variables into the procedure of upper bound calculation. This modification is necessary for the implicit enumeration scheme development but coupled with difficulties caused by an uncertainty of the status of Leader’s facilities, which are fixed to be open in branching procedure, but are able to be closed by Follower. Another direction of research can be associated with protection planning, where Leader is able to protect some of his facilities from closing.