\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}
\usepackage{cite}



\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]





%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}


\def\udcs{519.8} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{90B80} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{144}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{statement}{Statement}



\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}




\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\renewcommand{\figurename}{Fig.}




\thispagestyle{empty}

\title[Upper bound for $(r|p)$-centroid problem]{\large Additional constraints for computing upper bounds for $(r|p)$-centroid problem's objective function}


\author[V.L. BERESNEV]{{\bf V.L. Beresnev}\protect\orcidicon{0000-0001-5598-3399}}
\author[A.A. MELNIKOV]{{\bf A.A. Melnikov}\protect\orcidicon{0000-0002-2401-2407}}



\address{Vladimir Leonidovich Beresnev  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{beresnev@math.nsc.ru}}%

\address{Andrey Andreevich Melnikov  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Sobolev Institute of Mathematics,
	\newline\hphantom{iii} pr. Koptyuga, 4,
	\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{melnikov@math.nsc.ru}}%


\thanks{\sc Beresnev, V.L. and Melnikov A. A.,
Upper bound procedure for dynamic competitive facility location problem with profit targeting}
\thanks{\copyright \ 2024 Beresnev V.L. and Melnikov A. A.}
\thanks{\rm The research was carried out within the state assignment of Sobolev Institute of Mathematics (project № FWNF–2022–0019). }
\thanks{\it Received January, 1, 2023, Published December, 31, 2023}%


\def\semrtop
{
	\vbox{
		\noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
				{\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
				{\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
				{\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
				{\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
				\raisebox{1ex}{ISSN 1813-3304 }
				\vspace*{-3mm}
				%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
				%     {\small Sobolev Institute of Mathematics SB RAS}
			\end{center}
		}
		\vspace{-1mm}
		\noindent
		\begin{tabular}{c}
			\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
			\hline\hline
		\end{tabular}
		
		\vspace{3mm}
		{\flushleft\it Vol. 20, No. 2, pp. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
		\newline  %Volume, pages in Russian, filled by Editorial board
		{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
	}%\vbox
}




\semrtop \vspace{1cm}
\maketitle {\small

\vspace{-12pt}
%\centerline{{\it Communicated by} {\sc P.P. Petrov}
%({\it filled by Editorial board})
%}

\bigskip
\bigskip

\begin{quote}
\noindent{\bf Abstract:} We consider an $(r|p)$-centroid problem formulated as a bilevel mathematical programming problem.
In the problem, two competing parties open, respectively, $r$ and $p$ facilities aiming to attract customers' demand and maximize the market share.
An approach for computing upper bounds for the first player's (Leader) objective function, is proposed based on generating additional con\-straints (cuts) for the high-point relaxation of the bi-level problem.
New types of additional constraints are introduced, which take into account the specific of the $(r|p)$-centroid problem.
A procedure of generating these constraints, is discussed, which allows to improve sequentially the upper bound's quality.
\medskip

\noindent{\bf Keywords:} Competitive facility location, optimal solution, bi-level programming, high-point relaxation, cut generation.
 \end{quote}
}

\bigskip

\section{Introduction}
An $(r|p)$-centroid problem \cite{Hakimi1983} is a well-known hard discrete optimization problem.
To find its optimal solution, multiple heuristic and some exact methods are developed. 
A review of results in this field one may find in works \cite{Alekseeva2015,Roboredo2013}.
The $(r|p)$-centroid problem can be regarded as a competitive facility location problem \cite{EiseltLaporte1997,Karakitsiou2015,Ashtiani2016,Drezner2022}.
In these models, two competing parties are considered (Leader and Follower), which sequentially open their facilities aiming to capture customers and get maximal profit from serving them.
Such models can be written in a form of discrete bi-level programming problem, consisting of an upper-level problem (Leader's problem) and a lower-level one (Follower's problem).
The key difference between the $(r|p)$-centroid problem and competitive facility location problems is a condition, which restricts the growth of open facilities' number.
In the $(r|p)$-centroid, this condition is straightforwardly provided in a form of numbers of Leader's and Follower's facilities, which must be equal to $r$ and $p$, respectively.
For competitive facility location models, the number of open facilities is regulated by setting fixed costs for opening a facility.

In the present work, we study a possibility to use an idea of cut generation for computing upper bounds for the $(r|p)$-centroid's objective function.
This method was developed to solve competitive facility location problems \cite{BeresnevMelnikov2019} and is based on a way to compute upper bounds for the bilevel problem's objective function using its high-point relaxation (HPR) \cite{Dempe2020}.
This relaxation is derived from the initial bilevel problem by removing the lower-level objective function from it.
To improve this trivial upper bound, represented by the optimal value of the HPR's objective function, a suggestion is to strengthen the relaxation with additional constraints.
These constraints must cut-off the relaxation's optimal solution and be satisfied by bilevel feasible solutions of the initial problem.
For the competitive facility location problems, a construction of such constraints (c-cuts) was based on comparison of fixed cost of opening a facility and lower bound of income generated by it.
In a case of $(r|p)$-centroid, a new class of cuts (b-cuts) is proposed, which are based on comparison of income's lower bound and average income of Follower's facility in the current best-known feasible solution.
Besides that, a modification is proposed for f-cuts, which are used along with c-cuts for computing upper bounds in competitive facility location. 
An augmented f-cut, being an f-cut coupled with weakened b-cuts, is proposed for the problem under consideration to stimulate the lower-level variables to take non-zero values.

The main contribution of the present work is a procedure of calculation upper bounds for the $(r|p)$-centroid's objective function, which is based on the additional constraints proposed.
The procedure consists of identical steps, where the strengthened relaxation's optimal solution is computed.  
In the following, new additional constraints (b-cuts and augmented f-cuts), cutting-off the solution obtained, are built.
Such procedure can be utilized for computing an optimal solution of the bi-level problem either in a branch-and-bound-like algorithm or in a cut-generation scheme.

\section{Problem formulation}
We consider a formulation of the $(r|p)$-centroid problem in a form of bilevel optimization problem similar to competitive facitlity location problems \cite{BeresnevMelnikov2019}.
In the formulation, we use the following notation:
\par\noindent
$I$ is a set of potential facilities (locations);
\par\noindent
$J$ is a set of customers;
\par\noindent
$d_j$, $j\in J$ is a value of income from serving the customer $j$;
\par\noindent
$x_i$, $i\in I$ is a binary variable equal to one, if Leader opens their facility $i$, and zero otherwise;
\par\noindent
$\chi_{ij}$, $i\in I$, $j\in J$ is a binary variable equal to one, if the customer $j$ is served by Leader's facility $i$, and zero otherwise;
\par\noindent
$z_i$, $i\in I$ is a binary variable equal to one if Follower opens their facility $i$, and zero otherwise;
\par\noindent
$\zeta_{ij}$, $i\in I$, $j\in J$ is a binary variable equal to one if the customer $j$ is served by Follower's facility $i$, and zero otherwise.

Given $j\in J$, a linear order $\succeq_j$ defined on the set $I$ would be used in the model to represent preferences of the customer $j$ when choosing a facility to be served by. 
A relation $i_1\succ_j i_2$ means that the customer $j$ prefers the facility $i_1$ to the facility $i_2$.
For example, the linear order $\succeq_j$ could be determined by the distances to the facilities, with the closer facility being considered better. This corresponds to a scenario where each customer is served by the closest open facility.
The notation $i_1\succeq_j i_2$ means that either $i_1\succ_j i_2$ or $i_1 = i_2$. 
In the model, it is assumed that a customer can be served by any party's facility, which is more preferable for that customer than all the competitor's ones.

Using the notation introduced, the $(r|p)$-centroid problem can be written as follows:
\begin{equation}
	\label{1}
	\max_{(x_i), (\chi_{ij})} \sum_{j\in J}\sum_{i\in I} d_j \chi_{ij},
\end{equation}
\begin{equation}
	\label{2}
	\sum_{i\in I} x_i = r,
\end{equation}
\begin{equation}
	\label{3}
	x_i\geq \chi_{ij}, \quad i\in I, j\in J,
\end{equation}
\begin{equation}
	\label{4}
	z_i^0 + \sum_{k|i\succeq_j k} \chi_{kj} \leq 1, \quad i\in I, j\in J,
\end{equation}
\begin{equation}
	\label{5}
	x_i, \chi_{ij}\in \{0, 1\}, \quad i\in I, j\in J,
\end{equation}
\begin{equation}
	\label{6}
	\text{where $(z_i^0)$, $i\in I$ is a part of an optimal solution of the problem \eqref{7}--\eqref{12}}
\end{equation}
\begin{equation}
	\label{7}
	\max_{(z_i), (\zeta_{ij})} \sum_{j\in J}\sum_{i\in I} d_j \zeta_{ij}
\end{equation}
\begin{equation}
	\label{8}
	x_i + z_i \leq 1, \quad i\in I,
\end{equation}
\begin{equation}
	\label{9}
	\sum_{i\in I} z_i = p,
\end{equation}
\begin{equation}
	\label{10}
	z_i\geq \zeta_{ij}, \quad i\in I, j\in J,
\end{equation}
\begin{equation}
	\label{11}
	x_i + \sum_{k|i\succeq_j k} \zeta_{kj} \leq 1, \quad i\in I, j\in J,
\end{equation}
\begin{equation}
	\label{12}
	z_i, \zeta_{ij}\in \{0, 1\}, \quad i\in I, j\in J,
\end{equation}
Let us denote the upper-level problem \eqref{1}--\eqref{6} (Leader's one) as $\mathcal{L}$, while the problem \eqref{7}--\eqref{12} (Follower's one) as $\mathcal{F}$.
Whole the problem \eqref{1}--\eqref{12} would be denoted as $(\mathcal{L}, \mathcal{F})$.

A pair $(X, Z)$, where $X = \left((x_i), (\chi_{ij})\right)$, $Z = \left((z_i), (\zeta_{ij})\right)$, is called a \textit{feasible solution} of the problem $(\mathcal{L}, \mathcal{F})$, if, given $Z$, $X$ is a feasible solution of the problem $\mathcal{L}$ and, given $X$, $Z$ is an optimal solution of the problem $\mathcal{F}$.
The value of the Leader's objective function on a feasible solution $(X, Z)$ would be denoted by $L(X, Z)$. 
Notice that, if $(X, Z)$, where $X = \left((x_i), (\chi_{ij})\right)$, is a feasible solution, when the values of the objective function of the problems $(\mathcal{L}, \mathcal{F})$ and $\mathcal{F}$ are induced by the binary vector $x = (x_i)$.
Since that, we would say that the solution $(X, Z)$ is induced by the vector $x = (x_i)$, and a corresponding objective function's value would be denoted by $L(x)$ as well.
Given binary vector $x = (x_i)$, if $Z = \left((z_i), (\zeta_{ij})\right)$ is a feasible solution of the problem $\mathcal{F}$ then the value of the objective function of the problem $\mathcal{F}$ on this solution would be denoted by $F(x, Z)$.

\section{Additional constraints for the problem $(\mathcal{L}, \mathcal{F})$}
As like as for competitive facility location problems, the basement of the proposed way of computation upper bounds for the problem is a so-called high-point relaxation (HPR). 
This problem is obtained from the initial bi-level one, $(\mathcal{L}, \mathcal{F})$, by removing the objective function of the problem $\mathcal{F}$.
Notice that, in the case of the problem $(\mathcal{L}, \mathcal{F})$, one could remove lower-level assignment variables $(\zeta_{ij})$ as well. 
Thus, the HPR could be written as follows:

\begin{equation*}
	\max_{(x_i), (\chi_{ij}), (z_i)} \sum_{j\in J}\sum_{i\in I} d_j \chi_{ij},
\end{equation*}
\begin{equation*}
	\sum_{i\in I} x_i = r,
\end{equation*}
\begin{equation*}
	x_i\geq \chi_{ij}, \quad i\in I, j\in J,
\end{equation*}
\begin{equation*}
	z_i + \sum_{k|i\succeq_j k} \chi_{kj} \leq 1, \quad i\in I, j\in J,
\end{equation*}
\begin{equation*}
	x_i + z_i \leq 1, \quad i\in I,
\end{equation*}
\begin{equation*}
	\sum_{i\in I} z_i = p,
\end{equation*}
\begin{equation*}
	x_i, \chi_{ij}, z_i \in \{0, 1\}, \quad i\in I, j\in J,
\end{equation*}
An optimal solution of this problem's objective function provides a trivial upper bound for the objective function of the problem $(\mathcal{L}, \mathcal{F})$.
The idea of additional cuts' generation method is in supplementing the HPR with additional constraints, which are satisfied by feasible solutions of the initial problem $(\mathcal{L}, \mathcal{F})$ and stimulate variables of the problem $\mathcal{F}$ to take values, which are less desirable for the upper-level's objective function.
The resulting problem would still provide an upper bound for the objective for the problem $(\mathcal{L}, \mathcal{F})$ and would further referred to as \textit{strengthened estimating problem} (SEP) for $(\mathcal{L}, \mathcal{F})$.

Our goal is to construct a finite sequence of SEPs with monotonically decreasing optimal values of the objective function.
If an optimal solution of the final SEP in this sequence is a feasible solution of the problem $(\mathcal{L}, \mathcal{F})$, then the upper bound obtained is tight and the feasible solution is optimal.

\subsection{b-cuts}
Let us consider a family of additional constraints having the following property.
If $(X^*, Z^*)$ is a currently best (record) feasible solution of the problem $(\mathcal{L}, \mathcal{F})$ and an additional constraint is used to strengthen the SEP, then the current SEP's optimal solution violates the constraint, but any feasible solution $(X^0, Z^0)$ of the problem $(\mathcal{L}, \mathcal{F})$ such that $L(X^0, Z^0) > L(X^*, Z^*)$, satisfies it.

The following notation is used in construction of the additional constraints.
Let $x = (x_i)$, $i\in I$, be a non-zero binary vector, $J'$ be a non-empty subset of $J$, and let $k\in I$, $j\in J$.
Then we set
\par\noindent 
$I^1(x) = \{i\in I| x_i = 1\}$;
\par\noindent
$I^0(x) = \{i\in I| x_i = 0\}$;
\par\noindent
$\alpha_j(x)$ is such element $i\in I^1(x)$, that $i\succeq_j k$ for any $k\in I^1(x)$;
\par\noindent
$N_j(x) = \{i\in I| i\succ_j \alpha_j(x)\}$;
\par\noindent
$N_{J'}(x) = \bigcup_{j\in J'}N_j(x)$;
\par\noindent
$\bar{N}_j(x) = \{i\in I| i\succeq_j \alpha_j(x)\}$;
\par\noindent
$\bar{N}_{J'}(x) = \bigcup_{j\in J'}\bar{N}_j(x)$.

Let the record solution $(X^*, Z^*)$ be induced by vector $x^*$, and let $(X', z')$, $X' = \left((x_i'), (\chi_{ij}')\right)$, $z' = (z_i')$ be an optimal solution of the current SEP.
Let $J_0 = \{j\in J| \alpha_j(x') \succ_j \alpha_j(z')\}$.

To construct additional constraints suggested, along with vectors $x^*$ and $x'$, we use an element $k\in I^0(x' + z')$.
Consider the subset $J_0(k) = \{j\in J_0| k\succ_j\alpha_j(x')\}$, and let the following inequality holds for it

\begin{equation}
	\label{13}
	\sum_{j\in J_0(k)} d_j \geq \frac{1}{p}F(x^*, Z^*).
\end{equation}

Let $J'\subseteq J_0(k)$ be a subset, for which a similar inequality holds 
\begin{equation}
	\label{14}
	\sum_{j\in J'} d_j \geq \frac{1}{p}F(x^*, Z^*).
\end{equation}
Then, the following constraint
\begin{equation}
	\label{15}
	\sum_{j\in N_{J'}(x')}z_i \geq 
	1 + 
	\sum_{j\in J'}\max_{k\succ_j i\succeq_j\alpha_j(x')}(x_i - 1) - 
	\sum_{i\in \bar{N}_{J'}(k)}x_i
\end{equation}
would be called a b-cut of the solution $(X', z')$, generated by the element $k$ and subset $J'$.

From the form of inequality \eqref{15}, its right-hand side equals to one on the vector $x'$, while the left-hand side equals to zero on the vector $z'$.
This results in that the inequality is violated on the optimal solution of the current SEP.
Along with that, the constraint \eqref{15} possesses the key property of additional constrains and does not cut-off feasible solutions of the problem $(\mathcal{L}, \mathcal{F})$, which are better than the record one.

Let $(X, Z)$, $X = \left((x_i), (\chi_{ij})\right)$, $Z = \left((z_i), (\zeta_{ij})\right)$ be a feasible solution of the problem $(\mathcal{L}, \mathcal{F})$, and it is induced by vector $x = (x_i)$, $i\in I$. 
For any $i\in I^1(z)$, let $D_i = \{j\in J| \zeta_{ij} = 1\}$.
Then, we get $F(x, Z) = \sum_{i\in I^1(z)}\sum_{j\in D_i}d_j$.
\begin{statement}
	Let $(X^*, Z^*)$ be a record solution of the problem $(\mathcal{L}, \mathcal{F})$, which is induced by vector $x^*$, and let $(X, Z)$, $X = \left((x_i), (\chi_{ij})\right)$, $Z = \left((z_i), (\zeta_{ij})\right)$ be a feasible solution of the problem $(\mathcal{L}, \mathcal{F})$, induced by vector $x$, such that $L(x) > L(x^*)$. 
	Then the inequality \eqref{15} is satisfied by the solution $(X, Z)$.
\end{statement}
\begin{proof}
	Let binary vector $x = (x_i)$ be such that, for some $j\in J'$, we have $x_i = 0$ for all $i$ such that $k\succ_j i \succeq_j \alpha_j(x)$, or $x_i = 1$ for some $i\succeq_j k$.
	Then the constraint \eqref{15} is satisfied since its right-hand side is non-positive.
	
	Let, for any $j\in J'$, we have, firstly, $x_i = 1$ for some $i\in I$ satisfying $k\succ_j i \succeq_j \alpha_j(x')$, and, secondly, $x_i = 0$ for any $i\in I$ satisfying $i\succeq_j k$.
	Then, the right-hand side of the inequality \eqref{15} equals to one.
	Assume that the inequality is violated.
	Then, $z_i = 0$ for all $i\in N_{J'}(x')$ and, in particular, $z_k = 0$.
	
	For non-zero components of the vector $z = (z_i)$, consider values $\sum_{j\in D_i}d_j$, and choose an index $i_0$ for which this value is the smallest.
	Notice that, since for the solution $(X, Z)$ under consideration, it holds $L(x) > L(x^*)$, then $F(x, Z) < F(x^*, Z^*)$.
	Then, considering the inequality \eqref{14}, we get
	\begin{multline*}
		\sum_{j\in J'} d_j \geq 
		\frac{1}{p} F(x^*, Z^*) > 
		\frac{1}{p} F(x, Z) = 
		\frac{1}{p} \sum_{i| z_i = 1}\sum_{j\in D_i} d_j \geq
		\sum_{j\in D_{i_0}} d_j.
	\end{multline*}
	Thus, for the solution $(X, Z)$, among non-zero components of the vector $z = (z_i)$, there exists one with the index $i_0$ such that $\sum_{j\in J'} d_j > \sum_{j\in D_{i_0}}d_j$.
	Then, for the given vector $x = (x_i)$, let us consider a feasible solution $Z^0 = \left((z^0_i), (\zeta_{ij}^0)\right)$ of the problem $\mathcal{F}$, which differs from the solution $Z = \left((z_i), (\zeta_{ij})\right)$ in that $z_{i_0}^0 = 0$ and $z_k^0 = 1$.
	Notice that, for any $j\in J'$, we have $x_i = 0$ for $i\succ_j k$, $z_i = 0$ for $i\succeq_j \alpha_j(x')$, and $x_i = 1$ for some $i$ such that $k\succ_j i \succeq_j \alpha_j(x)$.
	Then, we can set $\zeta_{kj}^0 = 1$ for $j\in J'$.
	Considering that, we get
	\[
	F(x, Z^0) - F(x, Z) \geq \sum_{j\in J'}d_j - \sum_{j\in D_{i_0}}d_j > 0.
	\]
	Consequently, $Z = \left((z_i), (\zeta_{ij})\right)$ is not an optimal solution of the problem $\mathcal{F}$, and an initial solution $(X, Z)$ is not a feasible solution of the problem $(\mathcal{L}, \mathcal{F})$.
\end{proof}

Notice that the constructed additional constraint \eqref{15} cuts-off not only an optimal solution of SEP, but also solutions from some subset of its variations, which can be feasible solutions of the current or subsequent SEPs.
The number of these solutions, which can be cut-off, depends on the subset $J'$, and, in particular, on the number of elements in the subset $N_{J'}(k)$.
Thus, when choosing the subset $J'$, one should apply a procedure ensuring the smallest number of elements in the $N_{J'}(k)$.
Such procedure can be, for example, consist in solving of auxiliary optimization problem finding a subset $J'$ with the smallest $N_{J'}(k)$.

\begin{figure}
	\centering	
	\includegraphics[width=0.6\textwidth]{iter_2 cut_1.png}
	\caption{Visualization of a b-cut's structure.}
	\label{fig:1}
\end{figure}

Figure \ref{fig:1} demonstrates the structure of b-cuts. 
In the example, randomly generated points of the square represent places, where customers are located.
The same locations are suitable for opening facilities.
Customers' preferences are induced by Euclidean distances between the locations. 
The current solution of SEP is shown by red squares (Leader's facilities $x'$) and green stars (Follower's ones $z'$).
The customers captured by the Follower are are shown by small dark green circles.
There are only three such customers, and the rest are captured by the Leader.

The element $k$ generating the b-cut is shown by a blue diamond, and the corresponding set $J'$ is shown by small blue circles.
Big red circles indicate the locations $i\in I$ such that $k\succ_j i\succeq_j \alpha_j(x')$ for some $j\in J'$.
The small blue circle $j$ is connected by line segments with the corresponding big red circles.
The more connections we get, the more general a b-cut would be, since more variations of the vector $x'$ would make the sum $\sum_{j\in J'}\max_{k\succ_j i\succeq_j\alpha_j(x')}(x_i - 1)$ from \eqref{15} equal to zero, what retains the cut active.
Big gray circles together with big red ones indicate the set $N_{J'}(x')$, where Follower's facility must appear to satisfy \eqref{15} if it is active due to the choice of $x'$.

One could see that the current $x'$ shown on the figure activates the cut, and the sum of $z_i$ over the set of locations shown by big circles must be at least one.
The location of Follower's facilities violates this demand, what cuts-off the present solution of SEP along with some of its variations.
\subsection{Augmented f-cuts}
In a case, when a b-cut cannot be found for an optimal SEP's solution $(X', Z')$, we would apply other additional constraints proposed in \cite{BeresnevMelnikov2019} for the competitive facility location problem and called f-cuts.
To build that cut, one is to compute a feasible solution $(X^0, Z^0)$ of $(\mathcal{L}, \mathcal{F})$.
Let the vector inducing this solution is denoted by $x'$.
Then, one needs to write constraints forcing variables $z_i$, $i\in I$ to take values $z_i^0$ when the variables $x_i$, $i\in I$ equal to $x_i'$, $i\in I$.
For $(\mathcal{L}, \mathcal{F})$, this constraints can be written as follows:
\begin{equation}
	\label{16}
	p\left(
	\sum_{i\in I^1(x')}(1 - x_i)
	+
	\sum_{i\in I^0(x')}x_i
	\right)
	\geq
	\sum_{i\in I^1(z^0)}(1 - z_i^0).
\end{equation}
Let us refer it by an f-cut of the solution $(X', Z')$ generated by $(X^0, Z^0)$.

This inequality cuts-off any SEP's solution $(X, z)$, for which $x = x'$ and $z\neq z^0$. 
Along with that, it is satisfied by any solution $(X, z)$ with $x\neq x'$.
For this reason, on the following step after a generation of an f-cut, the optimal solution of the SEP can be very similar to the previous solution, and then proper b-cuts can be not found once again.

Consider augmented f-cuts by supplementing the inequality \eqref{16} with \textit{weakened b-cuts}, which do not cut-off optimal solution $(X', z')$, but stimulate variables $(z_i)$ to take non-zero values for broad set of variations of the vector $x' = (x_i')$. 

The process of weakened b-cut's construction for the f-cut of $(X', z')$ generated by $(X^0, Z^0)$ is analogous to a construction of a b-cut of $(X', z')$.
The difference is that, in the construction of the weakened b-cut, the vector $z' = (z_i')$ equals to zero.

The initial information in the cut generation is the index $k \in I^0(x')$.
Let, for the subset $J(k) = \{j\in J|k\succ_j\alpha_j(x')\}$, the following inequality holds:
\begin{equation}
	\label{17}
	\sum_{j\in J(k)}d_j \geq \frac{1}{p} F(x^*, Z^*),
\end{equation}
and let the inequality \eqref{14} holds for some subset $J'\subseteq J(k)$.
Then, the constraint \eqref{15} would be called \textit{weakened b-cut} generated by the index $k$ and subset $J'$ for the f-cut of $(X', z')$ generated by $(X^0, Z^0)$.

\begin{statement}
	Let $(X', z')$ be optimal solution of SEP, and $(X^0, Z^0)$ is a feasible solution of $(\mathcal{L}, \mathcal{F})$ induced by vector $x' = (x_i')$.
	Then, the set of indices $k\in I^1(z^0)$, for which the inequality \eqref{17} holds, is non-empty.
\end{statement}

\begin{proof}
	First of all, let us notice that $L(x^0)\leq L(x^*)$, since, if the feasible solution $(X^0, Z^0)$, which was used to generate the f-cut, is better than the record $(X^*, Z^*)$, then $(X^0, Z^0)$ must replace it and become record.
	Then, $F(x', Z^0) \geq F(x^*, Z^*)$.
	
	For the solution $Z^0$ of $\mathcal{F}$, let us consider subsets $D_k$, $k\in I^1(z^0)$, and, among the indices $k\in I^1(z^0)$, choose an index $k_0$, for which the value $\sum_{j\in D_k}d_j$ is the greatest.
	Then, it holds
	\[
	\sum_{j\in J(k_0)}d_j \geq 
	\sum_{j\in D_{k_0}}d_j \geq
	\frac{1}{p} \sum_{k\in I^1(z^0)}\sum_{j\in D_k}d_j =
	\frac{1}{p} F(x', Z^0) \geq
	\frac{1}{p} F(x^*, Z^*).
	\]
	Thus, we conclude that an f-cut along with weakened b-cuts not only cut-off the optimal SEP's solution $(X', z')$, but also stimulate variables $(z_i)$, affecting the SEP's objective function's value, to take non-zero values.
\end{proof}

\section{Overall cut generation scheme}
The cut generation procedure computing upper bounds for the objective function of the problem $(\mathcal{L}, \mathcal{F})$, as earlier mentioned, is an iterative process composed of an initial step and some number of identical common steps.

\textbf{On the initial step}, we define a record solution $(X^*, Z^*)$ of the problem $(\mathcal{L}, \mathcal{F})$ and construct initial SEP for $(\mathcal{L}, \mathcal{F})$.
For this, using heuristic procedure, we select some binary vector $x^0 = (x^0_i)$ and calculate a feasible solution $(X^0, Z^0)$ induced by $x^0$.
We set $X^* = X^0$, $Z^* = Z^0$ and supplement the HPR of the problem $(\mathcal{L}, \mathcal{F})$ with f-cut, induced by $(X^0, Z^0)$.
Further, considering $L(X^0, Z^0) \leq L(X^*, Z^*)$, we build a weakened b-cuts for this f-cut. 
This is done by enumerating indices $k\in I^0(x^0)$ and checking the condition \eqref{17} for the subset $J(k)$.
If the condition is satisfied, then we select a subset $J'\subseteq J(k)$ for which \eqref{14} is valid.
After it, a constraint \eqref{15}, represented in a form of linear inequalities, is added to the current SEP.
When the indices $k\in I$ are enumerated, the initial SEP's construction is finished, and the common steps begin.

\textbf{On each common step}, we have SEP obtained on the previous step and calculate its optimal solution $(X', z')$.
In result, we get an improved upper bound $UB(X', z')$ equal to the SEP's objective function's value on the solution $(X', z')$.
If $UB(X', z') = L(x^*)$ or a termination criteria is met, then the procedure terminates.
Otherwise, a generation of b-cuts of the solution $(X', z')$ begins.
For this, indices $k\in I^0(x'+z')$ are enumerated.
Given index $k$, we construct a subset $J_0(k)$ and check if the inequality \eqref{13} is satisfied.
In a positive case, a subset $J'\subseteq J_0(k)$, for which the inequality \eqref{14} holds, is selected aiming to minimize the size of $N_{J'}(k)$.
Then, we add a constraint \eqref{15}, formulated in term of linear inequalities, to the SEP and move to the next common step.
If we failed to find $k\in I^0(x' + z')$ generating a b-cut of $(X', z')$, then an f-cut of $(X', z')$ is generated.
For this purpose, we compute a feasible solution $(X^0, Z^0)$ of $(\mathcal{L}, \mathcal{F})$ induced by $x' = (x'_i)$.
The constraint \eqref{16} is added into SEP and, if $L(X^0, Z^0) > L(X^*, Z^*)$, we set $X^* = X^0$, $Z^* = Z^0$.
Further, considering $L(X^0, Z^0) \leq L(X^*, Z^*)$, we build weakened b-cuts for the f-cut generated by $(X^0, Z^0)$, introduce the constraints obtained into the SEP, and the next common step begins.

\section{Conclusion}
In the present work, we propose an approach to compute upper bounds for the $(r|p)$-centroid problem's objective function.
The basement of the proposed procedure is formed by the idea, which was used for computing upper bounds for competitive facility location problems.
The idea consists in strengthening the high-point relaxation of the initial bi-level problem using additional constraints.
While local properties of the lower-level problem's optimal solution are used for constructing additional constraints, for the $(r|p)$-centroid, the optimal solution as a whole is compared with those one from the current record solution of the bi-level problem.
This approach, when getting further development, could be used for competitive facility location problems having knapsack-like resource constraints within.

The nearest goal of the further research is to develop algorithms for finding optimal solutions of the $(r|p)$-centroid problem, using the proposed upper bound computing procedure. 
Preliminary numerical experiments show that the new b-cuts successfully cut-off the optimal solution of the high-point relaxation and increase the convergence of the lower-bound in a cut generation procedure. 
At the same time, the overall performance of the procedure and its final design need further improvement before detailed discussion.
Considering that similar algorithms proposed for competitive facility location problems have demonstrated satisfactory results in many computational experiments, one could hope on similar achievements with respect to the $(r|p)$-centroid problem.

%
% ---- Bibliography ----
%
% BibTeX users should specify bibliography style 'splncs04'.
% References will then be sorted and formatted in the correct style.
%
\begin{thebibliography}{1}
	\providecommand{\doi}[1]{https://doi.org/#1}
	
	\bibitem{Hakimi1983}
	Hakimi, S.: On locating new facilities in a competitive environment. European J. Oper. Res.  \textbf{12},  29--35 (1983)
	
	
	\bibitem{Alekseeva2015}
	Alekseeva, E., Kochetov, Y., Plyasunov, A.: {An exact method for the discrete
		$(r|p)$-centroid problem}. Journal of Global Optimization  \textbf{63}(3),
	445--460 (nov 2015). \doi{10.1007/S10898-013-0130-6}
	
	\bibitem{Roboredo2013}
	Roboredo, M.C., Pessoa, A.A.: A branch-and-cut algorithm for the discrete
	$(r|p)$-centroid problem. Eur. J. Oper. Res.  \textbf{224}(1),  101 -- 109
	(2013). \doi{10.1016/j.ejor.2012.07.042}
	
	\bibitem{EiseltLaporte1997}
	Eiselt, H., Laporte, G.: {Sequential location problems}. Eur. J. Oper. Res.
	\textbf{96}(2),  217--231 (1997). \doi{10.1016/S0377-2217(96)00216-0}
	
	\bibitem{Karakitsiou2015}
	Karakitsiou, A.: Modeling discrete competitive facility location. Springer,	SpringerBriefs in Optimization (2015). \doi{10.1007/978-3-319-21341-5}
	
	\bibitem{Ashtiani2016}
	Ashtiani, M.: Competitive location: A state-of-art review. International
	Journal of Industrial Engineering Computations  \textbf{7}(1),  1--18 (2016).
	\doi{10.5267/j.ijiec.2015.8.002}
	
	\bibitem{Drezner2022}
	Drezner, T.: Competitive facilities location. The Palgrave Handbook of Operations Research pp. 209--236 (2022). \doi{10.1007/978-3-030-96935-6\_7}
	
	
	\bibitem{BeresnevMelnikov2019}
	Beresnev, V., Melnikov, A.: Approximation of the competitive facility location
	problem with mips. Computers \& Operations Research  \textbf{104},  139--148
	(2019). \doi{10.1016/j.cor.2018.12.010},
	
	\bibitem{Dempe2020}
	Dempe, S.: Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography, pp. 581--672. Springer International Publishing, Cham (2020).
	\doi{10.1007/978-3-030-52119-6\_20}
						
\end{thebibliography}


\end{document}
