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



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

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




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




\thispagestyle{empty}

\title[Upper bound for dynamic competitive facility location problem]{\large Upper bound procedure for \\dynamic competitive facility location \\ problem with profit targeting}


\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 work was supported by Russian Science Foundation (project No. 23-21-00082). }
\thanks{\it Received January, 1, 2023, Published December, 31, 2023}%


\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 a dynamic competitive facility location problem, where two competing parties (Leader and Follower) aim to capture customers in each time period of the planning horizon and get a profit from serving them.
The Leader's objective function represents their regret composed of the cost of open facilities and a total shortage of income computed with respect to some predefined target income values set for each of the time periods.
The Follower's goal is to maximize their profit on the whole planning horizon.
In the model, the Leader makes their location decision once at the beginning of the planning horizon, while the Follower can open additional facilities at any time period.

In the present work, a procedure computing upper bounds for the Leader's objective function is proposed.
It is based on using a high-point relaxation of the initial bi-level mathematical program and strengthening it with additional constraints (cuts).
New procedures of generating additional cuts in a form of c-cuts and d-cuts, which are stronger than the ones proposed in earlier works, are presented.
\medskip

\noindent{\bf Keywords:} Competitive facility location, dynamic decision-making model, bi-level programming.
 \end{quote}
}

\bigskip

\section{Introduction}
We consider a problem from the family of competitive facility location models constructed on the base of the simple facility location problem and Stackelberg game. 
In such models, there are two competing parties, called Leader and Follower, who sequentially open their facilities aiming to capture customers and maximize a profit from servicing them.

Dynamic competitive facility location problems (DCompFLP models) generalize their static counterparts, CompFLP models, on a case, when substantial parameters, affecting the parties' decisions, are not fixed, but could change during the planning horizon under consideration. 
It is assumed, that the horizon is split into time intervals or periods, and the parties' interaction happens in each of them.

In \cite{BM2023}, a dynamic problem is considered, where Leader opens their facilities at the very first period and does not change their decision later. 
Follower, at the opposite, could extend their set of open facilities at any time period.
The parties' aim in the mentioned problem is getting a maximal total profit.
To construct an algorithm, computing a pessimistic optimal solution of the problem, the authors use an approach developed in works \cite{BM2019} for the CompFLP problem.
The base of this approach is a branch, bound and cut scheme, where upper bound's calculation is done using a so-called high-point relaxation (HPR) \cite{HS2016,FLMS2017,RY2017} of the initial bi-level model.
To provide bounds of a reasonable quality, such relaxation is to be strengthened by additional constraints.

In the present work, we continue the study of dynamic competitive models. 
The work's subject is different from the model considered in \cite{BM2023} in a form of the objective function of the Leader's problem. 
The function suggests that, for each planning horizon's period, a value of target income, which must be reached, is set.
Leader aims to choose locations of their facilities so that the regret computed as the cost of open facilities plus the highest income deficit over all the periods is minimized.
This optimization criteria reflects the business planning process, where a specific rate of service growth must be achieved over a planning period, during which the demand is expected to experience noticeable but predictable changes.

As like as in other competitive facility location models CompFLP and DCompFLP, in the model under study, the pessimistic optimal solution is considered to be the best one.
The major element of the approach developed to find such solutions \cite{D2020} is a procedure computing upper bounds for the objective function's values.
In \cite{BM2023}, to strengthen the HPR of the problem considered, additional constraints called c-cuts and d-cuts are proposed.
In the present work, we propose modified c-cuts and d-cuts, which take into account the form of the Leader's objective function and which are stronger than the initially proposed counterparts.

\section{Problem formulation}
To formalize the dynamic problem under consideration, we use the following index sets:
\par\noindent
$I$ is the set of candidate sites suitable for opening a facility;
\par\noindent
$T$ is the finite set of time periods of the planning horizon;
\par\noindent
$J_t$, $t\in T$ is the set of customers at the time period $t$. 
For the sake of convenience, we assume that $J_{t_1}\cap J_{t_2} = \emptyset$ for any $t_1, t_2\in T$ such that $t_1\neq t_2$.
Notice that it does not affects the generality since any customer, who presents at several time periods, could be replaced with an appropriate number of its copies having different indices.
$J$ would denote the set of all the customers present during the planning horizon, i.e. $J = \cup_{t\in T} J_t$.

The parameters of the model are the following:
\par\noindent
$f_i$, $i\in I$, is a fixed cost of opening the Leader's facility $i$;
\par\noindent
$g_{it}$, $i\in I$, $t\in T$, is a fixed cost of opening the Follower's facility $i$ at the period $t$. 
For each $i\in I$, we assume that $g_{it}$ decreases as $t$ grows.
\par\noindent
$p_{ij}$ and $q_{ij}$, $i\in I$, $j\in J$ are income values obtained by, respectively, Leader's and Follower's facility $i$ from serving the customer $j$;
\par\noindent
$D_t$, $t\in T$ is a target value of the Leader's income for the period $t$.

In the model, the following binary variables are used:
\par\noindent
$x_i$, $i\in I$ equals to one, if Leader opens their facility $i$, and zero otherwise;
\par\noindent
$z_{it}$, $i\in I$, $t\in T$ equals to one, if Follower opens their facility $i$ at the period $t$, and zero otherwise;
\par\noindent
$\chi_{ij}$ and $\zeta_{ij}$, $i\in I$, $j\in J$ are equal to one, if Leader's and, respectively, Follower's facility $i$ is assigned to service the customer $j$, and zero otherwise.

We assume that the choice of serving facility is subordinated to customer's preferences represented by a linear order on the set $I$.
Given $i_1, i_2\in I$ and $j\in J$, the relation $i_1\succeq_j i_2$ means that either $i_1 = i_2$ or $i_1$ is more preferable for $j$ than $i_2$.
The notation $i_1 \succ_j i_2$ means that $i_1\succeq_j i_2$ and $i_1\neq i_2$.

Using the introduced notation, the dynamic competitive facility location problem with profit targeting can be written as the following bi-level mathematical model.

\begin{eqnarray}
	\label{1}
	\sum_{i\in I}f_ix_i + \max_{t\in T}\left(D_t - \sum_{j\in J_t}\sum_{i\in I}p_{ij}\chi_{ij}\right)\to\min_{(x_i), (\chi_{ij})}\\
	\label{2}
	\sum_{\tau = 1}^{t} z_{i\tau}^0 + \sum_{k\in I|i\succeq_j k}x_{kj} \leq 1, \quad i\in I, t\in T, j\in J_t\\
	\label{3}
	x_i\geq \chi_{ij},\quad i\in I, j\in J\\
	\label{4}
	x_i, \chi_{ij}\in \{0, 1\}, \quad i\in I, j\in J\\
	\label{5}
	\mbox{$(z_{it}^0), (\zeta_{ij}^0)$ is an optimal solution of the Follower's problem:}\\
	\label{6}
	\sum_{t\in T}\sum_{i\in I}\left(-g_{it}z_{it} + \sum_{j\in J_t}q_{ij}\zeta_{ij}\right)\to\max_{(z_{it}), (\zeta_{ij})}\\
	\label{7}
	x_i + \sum_{t\in T}z_{it} \leq 1,\quad i\in I\\
	\label{8}
	x_i + \sum_{k\in I|i\succeq_j k}z_{kj}\leq 1, \quad i\in I, j\in J\\
	\label{9}
	\sum_{\tau = 1}^{t}z_{i\tau} \geq \zeta_{ij},\quad i\in I, t\in T, j\in J_t\\
	\label{10}
	z_{it}, \zeta_{ij}\in \{0, 1\}, i\in I, t\in T, j\in J.
\end{eqnarray}
The objective function \eqref{1} expresses the Leader's ``regret'' or losses aggregating the cost of open facilities and the highest income deficit over the planning horizon.
The objective function \eqref{6} represents the total profit obtained by the Follower during that time.
For each customer, the constraints \eqref{2} and \eqref{8} ensure that each party assigns only those facilities, which are more preferable for the customer, than any competitor's one. 
Inequalities \eqref{3} and \eqref{9} mean that only open facility can be assigned to service a customer.
Finally, the constraints \eqref{7} states that Follower can open their facilities only in locations which are not occupied by Leader's ones.

Let $D_0 = \max_{t\in T} D_t$ and $R_t = D_0 - D_t$, for each $t\in T$.
The objective function \eqref{1} of the problem DCompFLP can be rewritten as follows:

\begin{multline*}
	\min_{(x_i), (\chi_{ij})}\left(\sum_{i\in I}f_ix_i + \max_{t\in T}\left(D_0 - R_t - \sum_{j\in J_t}\sum_{i\in I}p_{ij}\chi_{ij}\right)\right) = \\
	D_0 + \min_{(x_i), (\chi_{ij})}\left(\sum_{i\in I}f_ix_i - \min_{t\in T}\left(R_t + \sum_{j\in J_t}\sum_{i\in I}p_{ij}\chi_{ij}\right)\right) = \\
	D_0 - \max_{(x_i), (\chi_{ij})}\left(-\sum_{i\in I}f_ix_i + \min_{t\in T}\left(R_t + \sum_{j\in J_t}\sum_{i\in I}p_{ij}\chi_{ij}\right)\right)
\end{multline*}

Then, the problem DCompFLP can be written as a bi-level problem with an objective function 
\begin{equation}
	\tag{\ref{1}'}\label{1prime}
	\max_{(x_i), (\chi_{ij})}\left(-\sum_{i\in I}f_ix_i + \min_{t\in T}\left(R_t + \sum_{j\in J_t}\sum_{i\in I}p_{ij}\chi_{ij}\right)\right)
\end{equation}
and constraints \eqref{2}--\eqref{10}.

This problem would be further the central object of our study.
Let the problem \eqref{1prime}, \eqref{2}--\eqref{5}, which is the Leader's one, is denoted by $\mathcal{L}$, and the Follower's problem \eqref{6}--\eqref{10} by $\mathcal{F}$.
The whole problem \eqref{1prime}, \eqref{2}--\eqref{10} would be denoted by $(\mathcal{L}, \mathcal{F})$.

A pair $(X, Z)$, where $X = ((x_i), (\chi_{ij}))$, is called a \textit{feasible solution} of the problem $(\mathcal{L}, \mathcal{F})$ induced by the binary vector $x = (x_i)$, if $X$ is a feasible solution of the problem $\mathcal{L}$, and $Z$ is an optimal solution of the problem $\mathcal{F}$ for the given $x$.
Let $L(X, Z)$ denotes the value of the Leader's objective function on the solution $(X, Z)$.
A feasible solution $(X, Z)$ induced by a vector $x$ is called a \textit{pessimistic feasible solution} if $L(X, Z) \leq L(X', Z')$ for any feasible solution $(X', Z')$ induced by vector $x$.
The problem to find a pessimistic optimal solution of the problem $(\mathcal{L}, \mathcal{F})$, i.e. its the best pessimistic feasible solution, can be considered as a problem to optimize an implicitly given function $L(x)$, since, for any binary vector $x$, the value of the Leader's objective function on a pessimistic feasible solution induced by $x$ is uniquely specified.
One could also consider an optimistic formulation of the problem $(\mathcal{L}, \mathcal{F})$, where the Leader's objective function is optimized with respect to lower-level variables as well, provided that these variables deliver optimal value to the Follower's objective function.
For bi-level programming problems, their pessimistic variants are often more complicated, so we concentrate on finding a pessimistic optimal solution of the problem $(\mathcal{L}, \mathcal{F})$, but further constructions can be easily transformed for the optimistic variant.

\section{Additional constraints for the $(\mathcal{L}, \mathcal{F})$'s relaxation}
As it is mentioned above, the problem $(\mathcal{L}, \mathcal{F})$ can be considered as a problem of maximizing a function $L(x)$ depending on Leader's location variables.
A subset of solutions, for which the upper bound would be computed, can be specified by a partial binary vector $y = (y_i)$, $i\in I$, where $y_i \in \{0, 1, *\}$.
The partial solution $y$ defines the fixed components of binary vectors $x = (x_i)$, $i\in I$.
If $y_i = *$ for some $i\in I$, then the value of $x_i$ is not fixed and can be either zero or one. 
Let $I^0(y) = \{i\in I| y_i = 0\}$ and $I^1(y) = \{i\in I| y_i = 1\}$.
Then the subset of solutions of the problem $(\mathcal{L}, \mathcal{F})$ defined by a partial solution $y$ is the set of solutions specified by binary vectors $x = (x_i)$, satisfying 
\begin{equation}
	\label{11}
	x_i = y_i, \quad i\in I^0(y)\cup I^1(y).
\end{equation}
The problem $(\mathcal{L}, \mathcal{F})$, where the problem $\mathcal{L}$ is supplemented with additional constraints \eqref{11}, would be denoted by $(\mathcal{L}(y), \mathcal{F})$.

The basis of an upper bound's computation procedure for the problem $(\mathcal{L}, \mathcal{F})$, as like as for other bi-level problems, could be formed by its high-point relaxation (HPR for short) \cite{D2020}.
HPR results from the initial bi-level model be removing the lower-level objective function and, consequently, the constraint on the lower-level variables to take optimal values.
Regarding the DCompFLP, it is clear that Follower's assignment variables $(\zeta_{ij})$, $i\in I$, $j\in J$ and lower-level constraints can be removed from the HPR without affecting the optimal value of the objective function and upper-level variables.
The HPR of the $(\mathcal{L}(y), \mathcal{F})$ problem can be written as follows.

\begin{eqnarray*}
	\max_{(x_i), (\chi_{ij})} \left( -\sum_{i\in I} f_i x_i + \min_{t\in T}\left(R_t + \sum_{j\in J_t}\sum_{i\in I} p_{ij}\chi_{ij}\right)\right)\\
	\sum_{\tau = 1}^t z_{i\tau} + \sum_{k| i\succeq_j k} x_{kj} \leq 1,\quad i\in I, t\in T, j\in J_t;\\
	x_i\geq \chi_{ij},\quad i\in I, j\in J;\\
	x_i + \sum_{t\in T}z_{it}\leq 1, \quad i\in I;\\
	x_i = y_i,\quad i\in I^0(y)\cup I^1(y);\\
	x_i, \chi_{ij}, z_{it}\in \{0, 1\}, \quad i\in I, j\in J, t\in T.
\end{eqnarray*} 

Clearly, the optimal value of the HPR's objective function provides a loosened upper bound for the problem $(\mathcal{L}(y), \mathcal{F})$. 
The quality of this bound can be improved by supplementing the HPR with additional constraints stimulating the lower-level variables $(z_{it})$, $i\in I$, $t\in T$, to take non-zero values.
The resulting problem would be referred to as \textit{strengthened estimating problem} (SEP for short) for the problem $(\mathcal{L}(y), \mathcal{F})$.

Let us consider a general scheme of the upper bound's calculation via generation of additional cuts for the HPR.
The value of the upper bound on a subset of solutions specified by a partial solution $y$ would be denoted by $UB(y)$.

If a partial solution $y$ is a binary vector and does not have components equal to *, then the calculation of the upper bound is reduced to finding a pessimistic feasible solution of the problem $(\mathcal{L}, \mathcal{F})$ induced by the vector $y$.
In this case, we assume $UB(y) = L(y)$.

In a general case, when the partial solution is not a binary vector, the upper bound's calculation is an iterative process consisting of an initial iteration and some number of general ones.

On the initial iteration, we consider an HPR of the problem $(\mathcal{L}(y), \mathcal{F})$ and form an initial SEP by constructing initial strengthening cuts.

On each general iteration, we consider the SEP from the previous iteration and compute its optimal solution.
Then, we try to construct all possible additional inequalities cutting-off this solution.
If the additional cuts are constructed, they are introduced into the SEP and the next iteration begins. 
Otherwise, the value of the upper bound $UB(y)$ is set to be equal to the optimal value of the SEP's objective function, and the upper bound's calculation terminates. 


\section{Cut generation procedures}

In \cite{BM2023}, additional constraints of two types are introduced for DCompFLP problem. 
The constraints are called c-cuts and d-cuts and are constructed to be violated by the current optimal solution of the SEP, what allows to tighten the upper bound during the general iterations.
Below, we consider new modifications of these constraints.
The new constraints and procedures constructing them allow to generate stronger cuts when compared to those proposed earlier.

To describe the construction of additional constraints, the following notations would be used.
Let $x = (x_i)$, $i\in I$ is a non-zero binary vector; $J'\subseteq J$, $J'\neq \emptyset$; $j\in J$ and $k\in I$.

Let 
\par\noindent
$I^1(x) = \{i\in I| x_i = 1\}$, $I^0(x) = \{i\in I| x_i = 0\}$;
\par\noindent
$\alpha_j(x)$ is such an element $i'\in I^1(x)$ that $i'\succeq_j i$ for all $ i\in I^1(x)$; 
\par\noindent
$\alpha_{J'}(x) = \{\alpha_j(x)| j\in J'\}$
\par\noindent
$N_{j}(k) = \{i\in I| i\succ_j k\}$;
\par\noindent
$N_{J'}(k) = \cup_{j\in J'}N_j(k)$;
\par\noindent
$N_{j}(x) = N_j(\alpha_j(x))$;
\par\noindent
$N_{J'}(x) = \cup_{j\in J'}N_j(x)$.

\subsection{Additional cuts on general iterations}
Let $(X', z')$, $X' = ((x_i'), (\chi_{ij}'))$, $z' = (z_{it}')$ be an optimal solution of the current SEP.
Also, let $u_{it}' = \sum_{\tau = 1}^t z_{i\tau}'$.
Denote the vectors $x' = (x_i')$ and $u_t' = (u_{it}')$.
For each $t\in T$, let $J_{0t} = J_t$, if $u_t' = 0$, and $J_{0t} = \{j\in J_t|\alpha_j(x')\succ_j\alpha_j(u_t')\}$ otherwise.

A c-cut of the solution $(X', z')$ is constructed based on a number $k\in I$ satisfying $x_k' = 0$ and $\sum_{t\in T}z_{kt}' = 0$.
Given $k$, consider subsets
\[
J_{0t}(k) = \{j\in J_{0t}| k\in N_j(x')\}, t\in T.
\]
Let $t_2\in T$ be the smallest index such that, for some $t_1\in T$, $1\leq t_1\leq t_2$, for a subset $J_0 = \cup_{t = t_1}^{t_2}J_{0t}(k)$ it holds

\begin{equation}
	\label{12}
	\sum_{j\in J_0} q_{kj} \geq g_{kt_1}, \quad \sum_{j\in J_0} p_{\alpha_{j}(x'), j} > 0.
\end{equation}

Let $J'\subseteq J_0$ is a subset, for which a similar condition holds: $\sum_{j\in J'}q_{kj} \geq g_{kt_1}$ and $\sum_{j\in J'} p_{\alpha_{j}(x'), j} > 0$.
Then, the inequality

\begin{equation}
	\label{13}
	\sum_{i\in N_{J'}(x')}u_{it_1} \geq 1 + \sum_{i\in \alpha_{J'}(x')}(x_i - 1) - \sum_{i\in N_{J'}(k)}x_i
\end{equation}
would be called a \textit{c-cut of the solution $(X', z')$ generated by an index $k$ and subset $J'$}.
The constraint \eqref{13} is stronger than those one used in our previous works, since the last sum is made over a set of indices $N_{J'}(k)$ instead of $N_{J'}(x')$.
Both variants are valid, but the first one would lead to more general cuts due to the inclusion $N_{J'}(k)\subseteq N_{J'}(x')$, which is often strict in practice.

Notice that the inequality \eqref{13} possesses the key property of the additional constraint.
\begin{proposition}
	Let $(X, Z)$ be a pessimistic feasible solution of the problem $(\mathcal{L}(y), \mathcal{F})$.
	Then, it satisfies the inequality \eqref{13}.
\end{proposition}
To convince ourselves that the Proposition holds, let us consider a vector $x = (x_i)$, generating the solution $(X, Z)$, such that $x_i = 0$ for some $i\in \alpha_{J'}(x')$.
Then, the right-hand side of the inequality \eqref{13} is not positive and, consequently, the inequality holds.

Let $x_i = 1$ for $i\in \alpha_{J'}(x')$ and $x_i = 0$ for $i\in N_{J'}(k)$.
Then, the right-hand side of the inequality \eqref{13} equals to one.
Assume that the inequality \eqref{13} is violated and its left-hand side equals to zero.
In this case, since $k\succ_j \alpha_j(x)\succeq_j\alpha_j(x')$ for each $j\in J'$, we have $x_i = 0$ for $i\succeq_j k$ and $\sum_{t = 1}^{t_2} z_{it} = 0$ for $i \succ_j \alpha_j(x)$.

Given vector $x$, let us consider a feasible solution $Z' = ((z_{it}'), (\zeta_{ij}'))$ of the problem $\mathcal{F}$, which differs from the solution $Z =((z_{it}), (\zeta_{ij}))$ only in that $z_{kt_1} = 1$.
Notice that, in this case, we can set $\zeta_{kj} = 1$ for $j\in J'$ due to the fact that $x_i = 0$ for $i\succ_j k$ and $\sum_{t = 1}^{t_2} z_{it} = 0$ for $i\succ_j\alpha_j(x)$.
For feasible solutions $Z$ and $Z'$ of the problem $\mathcal{F}$, the condition \eqref{12} implies that, for the Follower's objective function $F$, it holds
\begin{equation*}
	F(Z')-F(Z) \geq \sum_{j\in J'} q_{kj} - g_{kt_1} \geq 0.
\end{equation*}
It means that the solution $Z$ either is not an optimal solution of the problem $\mathcal{F}$ or it is not the least profitable Follower's optimal response from the Leader's point of view.
The later comes from the second part of the condition \eqref{12} demanding that $\sum_{j\in J_0} p_{\alpha_{j}(x'), j} > 0$, i.e. the Leader's income is smaller in a case of Follower's response $Z'$.
Consequently, the solution $(X, Z)$ is not a pessimistic feasible solution of the problem $(\mathcal{L}, \mathcal{F})$.

In addition, notice that, for the solution $(X', z')$, the left-hand side of the constraint \eqref{13} equals to zero, while the right-hand side equals to one.
Consequently, the inequality cuts-off the optimal solution $(X', z')$ of the SEP.
For any binary vector $x = (x_i)$, $i\in I$, such that $x_i = 1$ for $i\in \alpha_{J'}(x')$ and $x_i = 0$ for $i\in N_{J'}(x')$, the constraint \eqref{13} stimulates the values $u_{it}$, $i\in N_{J'}(x')$ to take non-zero values. 
The number of binary vectors $x$ satisfying these conditions depends on the size of subsets $\alpha_{J'}(x')\backslash I^1(y)$ and $N_{J'}(k)\backslash I^0(y)$, which depend on the choice of $J'$.

Depending on the number of elements in subsets $\alpha_{J'}(x')$ and $N_{J'}(k)$, the c-cut \eqref{13} can be restricting for different subsets of Boolean vectors $x = (x_i)$, $i\in I$, and, generally speaking, the larger the subsets $\alpha_{J'}(x')$ and $N_{J'}(k)$, the less restrictive the c-cut \eqref{13} is.
Consequently, one could aim at finding the strongest c-cuts by minimizing the size of these subsets.
Consider an auxiliary optimization problem whose solution defines a subset $J'$ generating the strongest c-cut.

Introduce the following notation:
\par\noindent
$a_{ij}$, $i\in I$, $j\in J_0$ is a parameter equal to one, if $i\in N_j(k)$, and zero otherwise;
\par\noindent
$b_{ij}$, $i\in I$, $j\in J_0$ is a parameter equal to one, if $i = \alpha_j(x')$, and zero otherwise;
\par\noindent
$c_j$, $j\in J_0$ is a parameter equal to one, if $p_{\alpha_j(x'), j} > 0$, and zero otherwise;
\par\noindent
$u_j$, $j\in J_0$ is a variable defining the subset $J'$ and equal to one, if $j\in J'$, and zero otherwise;
\par\noindent
$v_i$, $i\in I$ is a variable defining the subset $N_{J'}(k)$ and equal to one if $i\in N_{J'}(k)$, and zero otherwise;
\par\noindent
$w_i$, $i\in I$ is a variable defining the subset $\alpha_{J'}(x')$ and equal to one, if $i\in \alpha_{J'}(x')$ and zero otherwise.

Using the notations above, an auxiliary problem to choose the subset $J'$ can be written as follows:
\begin{eqnarray}
	\label{14}
	\min_{(u_j), (v_i), (w_i)}\left(\sum_{i\in I\backslash I^0(y)}v_i + \sum_{i\in I\backslash I^1(y)}w_i\right)\\
	\label{15}
	\sum_{j\in J_0}q_{kj}u_j\geq g_{kt_1};\\
	\label{16}
	\sum_{j\in J_0}c_ju_j\geq 1;\\
	\label{17}
	v_i \geq a_{ij}u_j,\quad i\in I, j\in J_0;\\
	\label{18}
	w_i\geq b_{ij}u_j,\quad i\in I, j\in J_0;\\
	\label{19}
	u_j, v_i, w_i \in \{0, 1\}, \quad i\in I, j\in J_0.
\end{eqnarray}
The inequality \eqref{13}, for which the subset $J'$ is computed using the auxiliary problem \eqref{14}--\eqref{19} would be called a \textit{c-cut of the solution $(X', z')$ generated by the index $k$}.

As it follows from the structure a constraint \eqref{13}, it stimulates the variables $u_{it}$ to take non-zero values.
Nevertheless, since the objective function of the SEP is maximized over variables $(z_{it})$, the value one would be taken by the variable $z_{it_1}$.
That makes the upper bound more ``optimistic'' and less accurate, which is unwanted.
When an optimal solution of the SEP has $z_{kl} = 1$ for some $l > 1$, an additional constraint from the family of d-cuts can be generated to force a variable $z_{kt}$ with $t < l$ to take a value equal to one.

Let $(X', z')$ be an optimal solution of the SEP satisfying that $z_{kl} = 1$ for some $l > 1$ and $k\in I$.
For this $k$, let us consider subsets $J_{0t}(k) = \{j\in J_{0t}| k\in N_j(x')\}$, $t\in T$.
Let $t_2\in T$, $t_2 < l$ be the smallest index such that there exists some $t_1$, $1 \leq t_1 < t_2$ such that, for a subset $J_0 = \cup_{t = t_1}^{t_2}J_{0t}(k)$, it holds 
\begin{equation}
	\label{20}
	\sum_{j\in J_0} q_{kj} \geq g_{kt_1} - g_{kt_2}, \quad \sum_{t = t_1}^{t_2}\sum_{j\in J_0\cap J_t}p_{\alpha_j(x'), j} > 0.
\end{equation}

Let $J'\subseteq J_0$ be a subset satisfying a similar condition: $\sum_{j\in J'} q_{kj} \geq g_{kt_1} - g_{kt_2}$, $\sum_{t = t_1}^{t_2}\sum_{j\in J_0\cap J_t}p_{\alpha_j(x'), j} > 0$.
Then, the inequality
\begin{equation}
	\label{21}
	\sum_{i\in N_{J'}(x')}u_{it_2}\geq 1 + (u_{kl} - 1) + \sum_{i\in \alpha_{J'}(x')}(x_i - 1) - \sum_{i\in N_{J'}(k)}x_i
\end{equation}
would be called a d-cut of the solution $(X', z')$ generated by the index $k$ and subset $J'$.

This inequality, as like as the inequality \eqref{13}, satisfies the key property of additional constraints
\begin{proposition}
	Let $(X, Z)$ be a pessimistic feasible solution of the problem $(\mathcal{L}(y), \mathcal{F})$.
	Then, it satisfies the inequality \eqref{21}.
\end{proposition}

Clearly, the solution $(X', z')$ violates the constraint \eqref{21}, so it would be cut-off after supplementing the SEP with this constraint.

To generate the strongest d-cut, analogously to the generation of c-cuts, an auxiliary optimization problem can be utilized.
This problem differs from the problem \eqref{14}--\eqref{19} only at the constraint \eqref{15}, which must be replaced by the following one:
\begin{equation}
	\label{22}
	\sum_{j\in J'} q_{kj} \geq g_{kt_1} - g_{kl}.
\end{equation}
The constraint \eqref{21}, where the subset $J'$ is found from the solution of the auxiliary optimization problem, would be referred to as a \textit{d-cut of the solution $(X', z')$, generated by the index $k$}.

\subsection{Additional constraints on the initial iteration}
On the initial iteration, an optimal solution of the SEP for the $(\mathcal{L}(y), \mathcal{F})$ problem is not computed yet. 
Thus, in a case, when $I^1(y)\neq \emptyset$, initial c-cuts of the feasible solution $(X', z')$ such that $x_i' = 1$ for $i\in I^1(y)$, $x_i' = 0$ otherwise, and $z_{it} = 0$ for $i\in I$, $t\in T$, are constructed.

To construct a c-cut, let us consider an index $k\in I$, $k\not\in I^1(y)$, and corresponding subsets $J_{0t}(k) = \{j\in J_t| k\in N_j(x')\}$, $t\in T$.
Let $t_2$ be the smallest index such that there exists an index $t_1\in T$, $1\leq t_1 \leq t_2$ such that, for a subset $J_0 = \cup_{t = t_1}^{t_2} J_{0t}(k)$ the conditions \eqref{12} hold.
Let $J'\subseteq J_0$ be a subset, for which similar conditions holds as well.
Then the constraint
\begin{equation}
	\label{23}
	\sum_{i\in N_{J'}(x')} u_{it_2} \geq 1 - \sum_{i\in N_{J'}(x')}x_i
\end{equation}
would be called an \textit{initial c-cut generated by index $k$ and subset $J'$}.

An auxiliary problem to choose a subset $J'$ for the initial c-cut has a form
\begin{eqnarray*}
	\min_{(u_j), (v_i)} \sum_{i\in I\backslash I^0(y)}v_i\\
	\sum_{j\in J_0}q_{kj} u_j \geq g_{kt_1}\\
	\sum_{j\in J_0}c_j u_j \geq 1\\
	v_i\geq a_{ij}u_j,\quad i\in I, j\in J\\
	v_i, u_j\in \{0, 1\}, \quad i\in I, j\in J.
\end{eqnarray*}
The constraint \eqref{23}, where the subset $J'$ computed within the auxiliary problem, would be called an \textit{initial c-cut generated by the index $k$}.

To conclude, the overall scheme of the upper bound $UB(y)$ calculation consists of the following steps.
On the initial iteration, we sequentially consider indices $k\in I$, $k\not\in I^1(y)$ aiming to construct an initial c-cut generated by the index $k$.
Given $k$, this procedure includes a proper choice of elements $t_2$ and $t_1\in T$, constructing a respective subset $J_0$, and checking of the conditions \eqref{12}. 
Successful result of the checking is necessary and sufficient condition of existence of a c-cut generated by the index $k$.
If the condition is satisfied, then we compute an optimal solution of the corresponding auxiliary problem and supplement the current SEP with additional cuts generated.
When all the indices $k\in I$, $k\not\in I^1(y)$, are considered, regardless whether the initial c-cuts are generated or not, the first general iteration begins.

On a general iteration, we consider the current SEP and its optimal solution $(X', z')$.
Further, we sequentially consider indices $k\in I$, $k\not\in I^1(y)$ aiming to construct a c-cut of the solution $(X', z')$, generated by the index $k$.
Given $k$, the procedure of construction of such a c-cut consists of the same steps as the procedure of initial c-cuts construction.
Initially, the elements $t_1$ and $t_2\in T$ are chosen, and a subset $J_0$ is built, for which the condition \eqref{12} is checked.
If it holds, then the optimal solution of the auxiliary problem provides a c-cut of the solution $(X', z')$.
This inequality is supplemented to the current SEP, and the next general iteration begins.
If none of the indices $k\in I$, $k\not\in I^1(y)$ generates a c-cut, then d-cuts are tried to be constructed.
In this purpose, we consider elements $k\in I$, for which $z_{kl} = 1$, $l > 1$.
Given $k$, the procedure of a d-cut construction is organized similarly to the c-cuts' one.
Firstly, the elements $t_1$ and $t_2$ are chosen, and then, for subset $J_0$, a necessary and sufficient condition of d-cut's existence is checked for this $k$.
In a case of success, an optimal solution of the corresponding auxiliary problem is computed, and the d-cut generated by $k$ is being introduced into the current SEP.
After the extension of the SEP, the next general iteration begins.

If there are no indices $k\in I$, $k\in I^1(y)$ generating additional constraints, the procedure of upper bound's calculation is terminated along with setting the value $UB(y)$ equal to the SEP's optimal value of the objective function.


%
% ---- Bibliography ----
%
% BibTeX users should specify bibliography style 'splncs04'.
% References will then be sorted and formatted in the correct style.
%
% \bibliographystyle{splncs04}
% \bibliography{mybibliography}
%
\begin{thebibliography}{8}
	\bibitem{BM2023}
	Beresnev, V.L., Melnikov, A.A. \href{https://doi.org/10.1134/S199047892303002X}{\it Additional Constraints for Dynamic Competitive Facility Location Problem}. J. Appl. Ind. Math. {\bf 17} (2023), 483–-490. 
	
	
	\bibitem{BM2019}
	Beresnev, V., Melnikov, A. \href{https://doi.org/10.1016/j.cor.2018.12.010}{\it Approximation of the competitive facility location problem with MIPs}. Comp. Oper. Res. {\bf 104} (2019), 139--148. 
	
	\bibitem{HS2016}
	Hemmati, M., Smith, J. C. \href{https://doi.org/10.1016/j.disopt.2016.04.001}{\it A mixed-integer bilevel programming approach for a competitive prioritized set covering problem}. Disc. Optim. {\bf 20} (2016), 105--134. 
	
	\bibitem{FLMS2017}
	Fischetti, M., Ljubi?, I., Monaci, M., Sinnl, M. \href{https://doi.org/10.1287/opre.2017.1650}{\it A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs}. Oper. Res. {\bf 65}:6 (2017), 1615-1637. 
	
	\bibitem{RY2017}
	Rahmani, A., Majid, Y. \href{https://doi.org/10.4995/ijpme.2017.6512}{\it An effective branch-and-cut algorithm in order to solve the mixed integer bi-level programming}. Inter. J. Prod. Man. Eng. {\bf 5}:1 (2017), 1--10. 
	
	\bibitem{D2020}
	Dempe, S. (2020). \href{https://doi.org/10.1007/978-3-030-52119-6_20}{\it Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography}. In: Dempe, S., Zemkoho, A. (eds) Bilevel Optimization. Springer Optimization and Its Applications, vol 161. Springer, Cham.
\end{thebibliography}
\end{document}
