# Competing for the most profitable tour: The orienteering interdiction game

Eduardo Álvarez-Miranda<EMAIL_ADDRESS>Department of Industrial
Engineering, Faculty of Engineering, Universidad de Talca, Sede Curicó, Chile
Instituto Sistemas Complejos de Ingeniería, Chile  Markus Sinnl
<EMAIL_ADDRESS>Institute of Business Analytics and Technology
Transformation/JKU Business School, Johannes Kepler University Linz, 4040
Linz, Austria  Kübra Tanınmış<EMAIL_ADDRESS>Department of Industrial
Engineering, Koç University, 34742 İstanbul, Turkey

###### Abstract

The orienteering problem is a well-studied and fundamental problem in
transportation science. In the problem, we are given a graph with prizes on
the nodes and lengths on the edges, together with a budget on the overall tour
length. The goal is to find a tour that respects the length budget and
maximizes the collected prizes. In this work, we introduce the orienteering
interdiction game, in which a competitor (the leader) tries to minimize the
total prize that the follower can collect within a feasible tour. To this end,
the leader interdicts some of the nodes so that the follower cannot collect
their prizes. The resulting interdiction game is formulated as a bilevel
optimization problem, and a single-level reformulation is obtained based on
interdiction cuts. A branch-and-cut algorithm with several enhancements,
including the use of a solution pool, a cut pool and a heuristic method for
the follower’s problem, is proposed. In addition to this exact approach, a
genetic algorithm is developed to obtain high-quality solutions in a short
computing time. In a computational study based on instances from the
literature for the orienteering problem, the usefulness of the proposed
algorithmic components is assessed, and the branch-and-cut and genetic
algorithms are compared in terms of solution time and quality.

Keywords:  Interdiction games, Orienteering problems, Bi-level optimization

##  1 Introduction and problem definition

In recent years, _interdiction games (IGs)_ have received considerable
attention in the logistics literature, see, e.g., the surveys (Smith and Song,
2020), (Kleinert et al., 2021, Chapter 6) and (Beck et al., 2023, Chapter
4.2). IGs involve two decision makers, usually called the _leader_ and the
_follower_ who compete in a hierarchical manner. The follower solves an
optimization problem defined over a set of _assets_ such as facilities or arcs
on a network that the leader can interdict within an _interdiction budget_.
Depending on the concrete setting of the IG, interdicting an asset can either
deprecate its value for the follower or completely destroy the asset making it
unusable for the follower. The goal of the leader is to choose the assets to
interdict in such a way as to maximize the deterioration of the follower’s
objective function value. Interdiction games find applications in various
areas such as marketing (DeNegre, 2011), identifying and defending critical
infrastructure (Church et al., 2004; Brown et al., 2006), as well as
conservation planning (Sefair et al., 2017). Network interdiction is an
important class of IGs, involving the interdiction of some network components
at the upper level. Early examples in this area include the interdiction of
flows on arcs (Wollmer, 1964; Wood, 1993), and the interdiction of shortest
paths (Israeli and Wood, 2002). More recent works address, for example, multi-
commodity flow interdiction (Lim and Smith, 2007), traveling salesman problem
with interdiction (Lozano et al., 2017), and maximum clique interdiction
(Furini et al., 2019). Smith and Song (2020) provides a comprehensive survey
on network interdiction problems.

In this work, we consider an interdiction version of the well-known
_orienteering problem_ (OP). In the OP we are given a graph with prizes on the
nodes and lengths on the edges, along with a budget for the overall length of
the tour and a depot node. The goal is to find a tour that respects the length
budget, passes through the depot, and maximizes the prizes collected (a node
prize is collected if the node is part of the tour) (Golden et al., 1987). As
a result, the OP is a combination of the knapsack problem (Dantzig, 1957) and
the traveling salesperson problem (Dantzig et al., 1954), and it is also known
as the selective traveling salesperson problem (Laporte and Martello, 1990).
This fundamental problem in logistics and transportation is NP-hard and has
spawned countless variants and generalizations such as the team OP (Chao et
al., 1996), OP with time windows (Labadie et al., 2012), and the stochastic OP
(Ilhan et al., 2008). For an overview on the OP, we refer to the surveys
(Vansteenwegen et al., 2011; Gunawan et al., 2016).

In the interdiction version of the OP, which we call the _orienteering
interdiction game_ (OIG), initially the leader interdicts some of the nodes
within a budget. Then, the follower solves an OP where it is not possible to
collect prizes from the interdicted nodes. The aim of the leader is to choose
the nodes to interdict in such a way that the maximum possible prize that the
follower collects is minimized. A formal definition of OIG is given in the
following.

######  Definition 1 (Orienteering interdiction game (OIG)).

We are given an undirected complete graph $G=(V,E)$ with node set $V$, an edge
set $E$, a prize $p_{i}>0$ associated with each node $i\in V$, and a length
$d_{e}$ associated with each edge $e\in E$. When a node $i\in V$ is
interdicted by the leader, its prize is captured by the leader and cannot be
collected by the follower even if node $i$ is visited in the follower tour.
Therefore, the leader’s goal is to interdict a subset of nodes, whose total
cost does not exceed an interdiction budget ($Q_{\ell}$), so it minimizes the
maximum profit (that is, the sum of the prizes of the nodes in the tour) that
the follower can achieve by performing a tour, starting at the depot
$\rho_{f}\in V$, with a total distance not exceeding a total distance budget
$B_{f}$.

An illustration of the OIG is presented in Figure 1, on the bayg29 instance of
TSPLIB95 (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/). The
instance involves 29 cities in Bavaria and connections between all city pairs.
We arbitrarily determine city 1 as the depot node and consider unit prizes,
unit interdiction costs, and three levels of the interdiction budget, i.e.,
$Q_{\ell}\in\\{0,5,8\\}$. Note that with an interdiction budget of zero the
obtained problem is just the OP without interdiction. As budget we used
$B_{f}=0.5\nu$ where $\nu$ denotes the optimal TSP tour length which is
provided with the instances. In the figure, the optimal leader solution
consists of the green nodes, and the resulting follower tour is shown in each
figure. The total prizes collected by the follower are 16, 12, and 11,
respectively.

(a) $Q_{\ell}=0$ (i.e., the OP without interdiction)

(b) $Q_{\ell}=5$

(c) $Q_{\ell}=8$

Figure 1: The bayg29 instance from TSPLIB95 library, with a given depot node
(orange) and considering unit prizes and unit interdiction costs. The
interdicted nodes (green) and the resulting follower tour are shown under
different leader budget $Q_{\ell}$.

OIG can model several applications, such as preventing competitors from
effective canvassing, also known as door knocking, which is considered crucial
for political campaigns (Lupfer and Price, 1972; Bhatti et al., 2019; Nyman,
2017). In such a setting, the leader who wants to minimize the support to the
competitor via canvassing and who has limited resources should identify and
convince key groups of individuals. It can also be used to identify critical
locations for patrolling. While studies including (Keskin et al., 2012; Cruz-
García et al., 2021) focus on the maximization of patrol coverage, in the
interdiction version the leader’s problem could model an adversary who wants
to damage the benefit/coverage of patrolling. Solving this problem reveals
important locations whose interdiction undermines the security operations in
the worst possible way. Lastly, the leader can model security forces who want
to prevent criminal activities of a moving follower. An example is to find the
best spots in a touristic district to continuously monitor so that the
pickpockets who stroll around are restrained. To the best of authors’
knowledge, there is limited work considering interdiction within a routing
problem. In Section 1.2 we provide a literature review on existing problems
and studies in this area.

###  1.1 Contribution and outline

The OIG is a two-player Stackelberg game (Von Stackelberg, 1952) and thus it
can be modeled as a bilevel optimization problem (BOP). We first formulate the
OIG as a BOP and then propose a single-level reformulation based on so-called
_interdiction cuts_ to tackle this challenging problem. This technique was
introduced in Fischetti et al. (2019) for interdiction games fulfilling a
certain _monotonicity_ assumption and we show that cuts of this form can also
be used for the OIG. Based on this reformulation, we develop a branch-and-cut
algorithm to solve the OIG and introduce various enhancements for the
algorithm. For solving the lower level problem within this algorithm, we make
use of the branch-and-cut ideas proposed by Fischetti et al. (1998) for the
OP. The main contributions of our work can be summarized as follows:

  * •

We introduce the OIG, which is a competitive version of the well known OP and
can model various applications ranging from security games to campaign
planning.

  * •

We formulate the OIG as a zero-sum BOP with binary decision variables in both
levels. Then, we propose a single-level reformulation of the problem using
_interdiction cuts_. To the best of our knowledge, this method has not been
used for any other routing problem yet.

  * •

Based on this formulation, we propose an algorithmic framework to solve the
OIG exactly via branch-and-cut. This framework includes several components
such as cut pools and integrated heuristic procedures which could reduce the
computational burden.

  * •

We develop a genetic algorithm to heuristically solve the OIG.

  * •

We provide a computational study on OP instances from literature adapted to
the OIG to assess the efficacy of our solution algorithms and their
ingredients.

The paper is organized as follows. In Section 2 we introduce the BOP
formulation of the OIG and propose a single-level reformulation. We then
describe a branch-and-cut method together with several enhancement strategies.
In Section 3, we present our genetic algorithm. We evaluate the performance of
our solution approaches in Section 4. Finally, we draw conclusions and provide
possible future research directions in Section 5.

###  1.2 Literature review

In this section, we provide an overview of the literature on interdiction
games involving routing decisions and on routing problems in a bilevel
optimization setting. First, we focus our attention on studies that consider
routing interdiction. In one of them, Lozano et al. (2017) address a
fortification-interdiction variant of the traveling salesperson problem where
the arcs are subject to protection and interdiction. Unprotected arcs can be
interdicted by the attacker, which increases the cost of those arcs. They
propose an exact iterative algorithm based on sampling of feasible tours. In
(Kheirkhah et al., 2016a) the vehicle routing problem with complete arc
interdictions is considered, and a Benders decomposition algorithm is proposed
which is capable to solve small size problems. In (Kheirkhah et al., 2016b), a
hazmat routing interdiction problem is presented in which the leader aims to
minimize the risk and the follower minimizes the routing cost. They propose
metaheuristic methods to solve it. Several variants of arc interdiction
vehicle routing problem are addressed by Bidgoli and Kheirkhah (2018); Sadati
et al. (2020a, b) and Nadizadeh and Sabzevari Zadeh (2021), and are handled
via heuristic/metaheuristic methods. To the best of our knowledge, neither
node interdictions nor a follower solving an orienteering problem were
considered before.

Next, we review works addressing a bilevel optimization problem (BOP)
involving routing in its lower level, i.e., a more general setting. In BOPs
each player has his/her own objectives and constraints and the leader, who
acts first, anticipates the optimal follower response (see, e.g., Dempe and
Zemkoho (2020); Kleinert et al. (2021) for an overview on BOPs). An IG is a
special class of BOPs where the leader and the follower optimize the same
objective function in opposite directions, while the leader affects the
follower problem via interdictions of his/her assets. Regarding exact
approaches for BOPs with a routing component, Cerulli et al. (2023) introduce
the bilevel profitable tour problem where the leader is the logistics platform
assigning orders to carriers and the followers are the carriers solving a
profitable tour problem. They develop a branch-and-cut algorithm to solve the
problem exactly. Aside from this work which uses an exact algorithm, there are
also several works on BOPs with a routing component which propose
metaheuristic algorithms to solve the adressed problem: The paper
(Nikolakopoulos, 2015) addresses vehicle routing problem with backhauls and
time windows in a military context. The problem is formulated as a BOP where
the goal of the leader is to minimize the number of vehicles, and the follower
wants to minimize the total routing cost. Ning and Su (2017) consider a
vehicle routing problem with uncertain travel times. In the proposed bilevel
model, the leader minimizes the expected total waiting time, and each follower
(vehicle) minimizes its own waiting time. In the production-distribution
planning problem considered by Calvete et al. (2011), the distribution and
manufacturing companies act respectively as the leader and the follower of a
bilevel model. Each player seeks to minimize their costs. Camacho-Vallejo et
al. (2022) study a similar problem in which the distributor has $CO_{2}$
emission goals in addition to profit maximization. This leads to a bi-
objective leader problem. Parvasi et al. (2019) consider the problem of bus
stop location and school bus routing, which is modeled as a BOP.

Aside from these works, which model competitive settings with multiple agents,
sometimes routing problems just involving a single level (i.e., a single
decision maker) are also modeled as BOPs: Marinakis et al. (2007) formulate
the vehicle routing problem as a BOP such that in the first level customers
are assigned to vehicles and in the second level optimal routes of these
assignments are determined. Similarly, Marinakis and Marinaki (2008) model the
location routing problem with a BOP formulation whose leader makes the
strategic decisions (facility locations) and whose follower makes operational
decisions (routes). Both problems are solved via genetic algorithms. Jia et
al. (2021) formulates the capacitated electric vehicle routing problem as a
BOP whose upper level involves the routing decisions and the lower level
involves determining the charging schedule. They propose an ant colony
optimization algorithm.

Note that there are generic methods for solving interdiction games under
certain assumptions, such as the iterative bounding algorithms in Tang et al.
(2016); Lozano and Smith (2017); Tanınmış et al. (2022), or the branch-and-cut
method in Fischetti et al. (2019). Similarly, there exist methods for solving
integer bilevel linear programming problems (Wang and Xu, 2017; Fischetti et
al., 2017; Tahernejad et al., 2020). However, due to the inherent difficulty
of interdiction games and integer bilevel linear programming problems, these
generic methods usually are only capable of solving rather small-sized
(generic) instances. For this reason, we design an exact algorithm tailored to
the OIG (based on ideas from Fischetti et al. (2019)) and also propose a
genetic algorithm to heuristically obtain high-quality solutions within a
shorter running time compared to our exact approach.

##  2 An interdiction-cut-based exact solution method for the OIG

In order to formulate the OIG as a bilevel integer program, we introduce the
following notation. Let $\mathbf{z}\in\\{0,1\\}^{|V|}$ be a vector of decision
variables, so that $z_{i}=1$ if the leader interdicts node $i\in V$, and
$z_{i}=0$ otherwise; hence, $z_{i}=1$ implies that the leader prevents the
follower from getting the prize of node $i$. Likewise, let
$\mathbf{y}\in\\{0,1\\}^{|V|}$ be a vector of decision variables so that
$y_{i}=1$ if the follower visits node $i\in V$ in his/her tour, and $y_{i}=0$
otherwise; additionally, let $\mathbf{x}\in\\{0,1\\}^{|E|}$ be a vector of
decision variables so that $x_{e}=1$ if the follower traverses the edge $e$ in
the tour, and $x_{e}=0$ otherwise. Let $\tau(\mathbf{x},\mathbf{y})$ denote
the tour induced by a given pair $(\mathbf{x},\mathbf{y})$; and let
$\mathcal{T}$ be the set of all feasible tours, i.e., cycles that do not
contain subtours and that pass through the depot $\rho_{f}$, where each node
in the tour is visited at most once. Considering this notation, the OIG can be
formulated by the following (bilevel) MIP model:

$\displaystyle\mbox{(\hypertarget{OIGB}{OIGB})}\qquad\qquad{\phi}^{\ast}=\min_{\mathbf{z}\in\\{0,1\\}^{|V|}}\;\;\max_{(\mathbf{x},\mathbf{y})\in\\{0,1\\}^{|E|\times|V|}}\;\;$
$\displaystyle\sum_{i\in V}p_{i}(1-z_{i})y_{i}\qquad\qquad\qquad\qquad$ (OBJ)
s.t. $\displaystyle\sum_{i\in V}z_{i}\leq Q_{\ell}$ (IBUDGET)
$\displaystyle\sum_{e\in E}d_{e}x_{e}\leq B_{f}$ (DBUDGET)
$\displaystyle\tau(\mathbf{x},\mathbf{y})\in\mathcal{T}.$ (TOUR)

The objective function (OBJ) encodes the (bilevel) $\min\max$ optimization
goal, which is the minimization of maximum prize collected from the nodes that
are visited and non-interdicted. Constraint (IBUDGET) imposes that the total
number of interdictions does not exceed the interdiction budget $Q_{\ell}$.
Likewise, the constraint (DBUDGET) imposes that the total distance of the
follower’s tour does not exceed the follower’s distance budget $B_{f}$.
Finally, the constraint (TOUR) ensures that the vectors $\mathbf{x}$ and
$\mathbf{y}$ must induce a feasible tour that includes the depot $\rho_{f}$.

###  2.1 A single-level reformulation of the OIG

Before we present a single-level reformulation of the OIG, we first formulate
constraint (TOUR) using subtour elimination constraints. For a given subset of
nodes $S\subseteq V$, let $\delta(S)=\left\\{\\{i,j\\}:e\in E\mid i\in
S,\;j\in V\setminus S\right\\}$; i.e., $\delta(S)$ corresponds to the set of
edges that are incident to the nodes contained in set $S$. Using this
definition, $\tau(\mathbf{x},\mathbf{y})\in\mathcal{T}$ can be encoded by the
following set of constraints:

$\displaystyle\sum_{e\in\delta(j)}x_{e}=2y_{j},\;\forall j\in V$ (SEC.1)
$\displaystyle\sum_{e\in\delta(S)}x_{e}\geq 2y_{j},\;\forall j\in V\setminus
S,\;\forall S\subset V\mid_{\rho_{f}\in S}$ (SEC.2) $\displaystyle
y_{\rho_{f}}=1.$ (SEC.3)

Constraints (SEC.1) model the fact that if a node $j^{\prime}\in V$ is
included in the follower’s tour (i.e., $y_{j^{\prime}}=1$), then exactly two
of its adjacent edges must also be included in the tour
($\sum_{e\in\delta(j^{\prime})}x_{e}=2$). Constraints (SEC.2) are the so-
called _generalized subtour elimination constraints_ (GSECs) and they ensure
that the tour defined by $\mathbf{x}$ and $\mathbf{y}$ does not contain
subtours. Constraint (SEC.3) ensures that the depot $\rho_{f}$ is included in
the follower’s tour.

Let $\Phi(\mathbf{z})$ be the value function of the lower level problem for a
given interdiction decision $\mathbf{z}$, i.e.,

$\displaystyle\Phi(\mathbf{z})=\max_{(\mathbf{x},\mathbf{y})\in\\{0,1\\}^{|E|\times|V|}}\;\;$
$\displaystyle\sum_{i\in V}p_{i}(1-z_{i})y_{i}$ s.t. $\displaystyle\mbox{
\eqref{eq:iop3}, \eqref{eq:degree}, \eqref{eq:GSEC}, and \eqref{eq:depot}}.$

Then, we can write the value function reformulation of the OIG as follows:

$\displaystyle{\phi}^{\ast}=\min_{\mathbf{z}\in\\{0,1\\}^{|V|}}\;\;$
$\displaystyle t$ s.t. $\displaystyle t\geq\Phi(\mathbf{z})$
$\displaystyle\eqref{eq:iop2}.$

Note that the value function reformulation is non-convex, even when the binary
restrictions are relaxed, due to the value function constraint
$t\geq\Phi(\mathbf{z})$ which ensures that the objective function value of the
upper level is at least as large as the optimal objective function value of
the lower level for the selected interdiction decision. However, it can be
further reformulated by considering the feasible follower solutions as
follows. Let $\mathbf{Y}$ be the set of all vectors $\mathbf{\hat{y}}$ such
that there exists a tour
$\tau(\mathbf{\hat{x}},\mathbf{\hat{y}})\in\mathcal{T}$ for some
$\mathbf{\hat{x}}\in\\{0,1\\}^{|E|}$, satisfying the follower’s distance
budget $B_{f}$. Using this notation, we can obtain the following single-level
reformulation of the OIG.

$\displaystyle\mbox{(\hypertarget{OIGS}{OIGS})}\qquad\qquad{\phi}^{\ast}=\min_{\mathbf{z}\in\\{0,1\\}^{|V|}}\;$
$\displaystyle t$ s.t. $\displaystyle t\geq\sum_{i\in
V}p_{i}(1-z_{i})\hat{y}_{i},\;\forall\mathbf{\hat{y}}\in\mathbf{Y}$ (ICUT)
$\displaystyle\eqref{eq:iop2}$

In this formulation, (ICUT) corresponds to the set of _interdiction cuts_
(following the terminology of Fischetti et al. (2019)). These cuts model the
value function constraint $t\geq\Phi(\mathbf{z})$.

######  Proposition 1.

The formulation (OIGS) models the OIG.

###### Proof.

We have to show that for any interdiction decision $\mathbf{z}$ the set of
constraints (ICUT) ensures that $t$ will have the value of $\Phi(\mathbf{z})$
(taking into account that the objective function forces
$t=\max_{\mathbf{\hat{y}}\in\mathbf{Y}}\sum_{i\in
V}p_{i}(1-z_{i})\hat{y}_{i}$). Suppose this is not the case. This means there
exist an interdiction decision $\mathbf{\bar{z}}$ for which either
$\Phi(\mathbf{\bar{z}})>\sum_{i\in
V}p_{i}(1-\bar{z}_{i})\hat{y}_{i},\;\forall\mathbf{\hat{y}}\in\mathbf{Y}$ or
$\exists\mathbf{\hat{y}}\in\mathbf{Y}:\sum_{i\in
V}p_{i}(1-\bar{z}_{i})\hat{y}_{i}>\Phi(\mathbf{\bar{z}})$. We proceed by case
distinction.

  * •

Assume $\Phi(\mathbf{\bar{z}})>\sum_{i\in
V}p_{i}(1-\bar{z}_{i})\hat{y}_{i},\;\forall\mathbf{\hat{y}}\in\mathbf{Y}$: Let
$\mathbf{y}^{*}(\mathbf{\bar{z}})$ be an optimal solution of
$\Phi(\mathbf{\bar{z}})$. Clearly
$\mathbf{y}^{*}(\mathbf{\bar{z}})\in\mathbf{Y}$ and $\sum_{i\in
V}p_{i}(1-\bar{z}_{i})y^{*}(\mathbf{\bar{z}})_{i}=\Phi(\mathbf{\bar{z}})$.
Thus we arrive at a contradiction to our assumption.

  * •

Assume $\exists\mathbf{\hat{y}}\in\mathbf{Y}:\sum_{i\in
V}p_{i}(1-\bar{z}_{i})\hat{y}_{i}>\Phi(\mathbf{\bar{z}})$: Since the
interdiction decisions to not affect the feasibility of the lower level
problem, we have that $\mathbf{\hat{y}}$ is feasible for the lower level
problem given interdiction decision $\mathbf{\bar{z}}$. Consequently the value
of $\Phi(\mathbf{\bar{z}})$ must be at least $\sum_{i\in
V}p_{i}(1-\bar{z}_{i})\hat{y}_{i}$. Thus we we arrive at a contradiction to
our assumption.

We have arrived at a contradiction for both cases, which concludes our proof.
∎

###  2.2 A branch-and-cut algorithm

In order to solve the OIG, we propose a branch-and-cut (B&C) algorithm based
on (OIGS), where we drop (ICUT) and add those constraints _on-the-fly_. In the
remainder, we denote the linear programming (LP) relaxation of any B&C
subproblem by $\overline{\mbox{OIGS}}$, which includes a subset of (ICUT), in
addition to (IBUDGET), and branching decisions made to reach the current B&C
node. We note that in order to separate (ICUT) we employ another B&C algorithm
within our main B&C algorithm, details are given below.

####  2.2.1 Separation of interdiction cuts

In this section, we describe how we separate the inequalities (ICUT) while
implementing the B&C algorithm to solve the OIG. Let
$(\bar{t},\bar{\mathbf{z}})$ be a feasible solution to
$\overline{\mbox{OIGS}}$. We need to solve the following separation problem,
which is identical to the follower’s problem for
$\mathbf{z}=\bar{\mathbf{z}}$:

$\displaystyle\mbox{(\hypertarget{SEP}{SEP})}\qquad\qquad\Phi(\bar{\mathbf{z}})=\max_{(\mathbf{x},\mathbf{y})\in\\{0,1\\}^{|E|\times|V|}}$
$\displaystyle\;\sum_{i\in V}p_{i}(1-\bar{z}_{i})y_{i}$ s.t.
$\displaystyle\mbox{\eqref{eq:iop3},\leavevmode\nobreak\
\eqref{eq:degree},\leavevmode\nobreak\ \eqref{eq:GSEC}\leavevmode\nobreak\
and\leavevmode\nobreak\ \eqref{eq:depot}}.$

If $\bar{t}<\Phi(\bar{\mathbf{z}})$, then we need to add a violated
interdiction cut to separate the point $(\bar{t},\bar{\mathbf{z}})$.
Otherwise, $\bar{t}$ captures the optimal follower objective value correctly,
and we treat the current point as a feasible solution to our problem.

We enhance the formulation (SEP) by making use of two classes of valid
inequalities for the orienteering problem (Fischetti et al., 1998). The first
class of inequalities, that we refer to as _logical constraints_ , is given by

$\displaystyle x_{e}\leq y_{j},\qquad\forall e\in\delta(j),\;\forall j\in V.$
(Logical)

Basically, these constraints ensure that if a given node $j$ is not visited by
the follower’s tour ($y_{j}=0$), then none of the incident edges is part of
the tour ($x_{e}=0,\;\forall e\in\delta(j)$). The second class of inequalities
corresponds to the _cycle cover inequalities_ , which are given by

$\displaystyle\sum_{e\in E_{\tau}}x_{e}\leq\sum_{j\in V_{\tau}}y_{j}-1,$ (CC)

for a given tour $\tau$ that is encompassed by the nodes in $V_{\tau}$ and by
the edges in $E_{\tau}$, and with a total distance $\sum_{e\in E_{\tau}}d_{e}$
larger than $B_{f}$. These constraints ensure that if the follower’s tour
includes the nodes in $V_{\tau}$, then at least one of the edges in $E_{\tau}$
must be excluded from the tour in order to not violate the corresponding
follower’s distance budget constraint (DBUDGET).

####  2.2.2 Separation of follower cuts

To solve the separation problem (SEP), we carry out another B&C procedure
where we drop the subtour elimination constraints (SEC.2) from the initial
formulation and add violated ones once they are detected, on-the-fly. In
addition, we make use of the valid inequalities described in the previous
section. Suppose that we are given the (possibly infeasible) follower solution
$(\mathbf{\bar{x}},\mathbf{\bar{y}})$. In the following, we describe how we
separate the inequalities of each type at
$(\mathbf{\bar{x}},\mathbf{\bar{y}})$.

##### Generalized subtour elimination constraints.

These inequalities are obtained using the maximum flow-based approach proposed
by Fischetti et al. (1998). In this approach, given
$(\mathbf{\bar{x}},\mathbf{\bar{y}})$, first the so-called support graph is
first obtained which contains the nodes and edges of the original graph such
that $\bar{x}_{e}>0$ and $\bar{y}_{j}>0$, respectively. On this graph, a
minimum capacity cut separating the depot and any non-depot node leads to a
(possibly violated) GSEC. The nodes are considered one by one, according to
the non-decreasing order of $\bar{y}_{j}$ and then the maximum flow
computations are done. We refer the reader to Fischetti et al. (1998) for
further details.

##### Logical constraints.

These inequalities are obtained by complete enumeration of node-edge pairs
such that $\bar{x}_{e}>y_{j}$ where $e\in\delta(j)$, which can be done in
$O(|E|)$ time.

##### Cycle cover inequalities.

These inequalities are obtained via the heuristic procedure in Fischetti et
al. (1998). This heuristic takes $\mathbf{\bar{x}}$ as input and computes a
maximum-weight spanning tree. Then for each edge $e$ that is not in the tree,
if adding $e$ creates a cycle that passes through $\rho_{f}$, then the
violation of the cut for the resulting tour is checked.

At every (follower) B&C node with a fractional solution
$(\bar{\mathbf{x}},\bar{\mathbf{y}})$, we first look for all possible violated
valid inequalities (Logical). If none is found, then we try to find violated
inequalities (SEC.2). If violated cuts are not identified, then violated (CC)
are tried to be obtained. In case there are no violated inequalities of these
three types, no action is needed. For integer feasible
$(\bar{\mathbf{x}},\bar{\mathbf{y}})$, we only look for violated inequalities
of type (SEC.2). If there is none, $(\bar{\mathbf{x}},\bar{\mathbf{y}})$ is a
feasible solution to (SEP) and it replaces the incumbent solution if it is a
better one.

###  2.3 Enhancement strategies

While solving the OIG with the B&C approach that we propose, we make use of
some strategies that could help to speed up the algorithm, in particular the
separation procedure. Below we describe the algorithm components developed to
this end. In our computational experiments, we try different combinations of
these enhancement strategies. The details of these combinations including the
values used for the parameters which occur in some of the strategies described
in the following are given in Section 4.2.

##### Separation problem objective lower bound (lower cutoff).

For a given leader solution $(\bar{t},\bar{\mathbf{z}})$ that is the optimal
solution of the current B&C subproblem, the optimal objective value
$\Phi(\bar{\mathbf{z}})$ of the separation problem (SEP) cannot be less than
$\bar{t}$ since the interdiction cuts underestimate the follower objective
value. Therefore, we can set a lower cutoff value $\bar{t}$ on the objective
function value while solving (SEP), for more efficient pruning of nodes in the
B&C tree of (SEP).

##### Cut pool.

Every time (SEP) is solved, inequalities of type (CC) and (SEC.2) are
generated. We keep a pool of previously obtained inequalities of these types
to be used in later attempts to solve the separation problem. Based on
preliminary experiments, instead of including all the inequalities of the cut
pool in the initial formulation of (SEP), we iterate over the pool and add the
violated ones at the root node of the B&C tree, after each time the node
subproblem is solved.

##### Solution pool.

Every time (SEP) is solved for a given leader solution $\bar{\mathbf{z}}$,
which yields a feasible solution $(\bar{\mathbf{x}},\bar{\mathbf{y}})$, we
retrieve the obtained tour $c=\tau(\bar{\mathbf{x}},\bar{\mathbf{y}})$ and add
it to a (solution) pool denoted by $\mathcal{C}$. These solutions are utilized
to generate new feasible follower solutions that possibly yield violated
interdiction cuts, as described in the following paragraph. We denote by
$V_{c}=\\{j\in V:\bar{y}_{j}=1\\}$ and $E_{c}=\\{e\in E:\bar{x}_{e}=1\\}$ the
sets of nodes and edges, respectively, associated to tour $c$.

##### Heuristic follower solutions.

For the correctness of the overall B&C algorithm, it is necessary to have an
exact separation method for integer leader solutions, i.e., a method that
returns a violated interdiction cut when in the current solution
$(\bar{t},\bar{\mathbf{z}})$, $\bar{t}$ strictly underestimates the follower
objective value for $\bar{\mathbf{z}}$. On the other hand, it may be possible
to separate fractional solutions as well which could improve the dual bound
faster. Since it is usually costly to carry out an exact method for every
fractional solution encountered during B&C, the common approach is to use a
heuristic separation algorithm that can yield violated cuts (Fischetti et al.,
2019). To this end, we propose a heuristic separation scheme that can be used
for fractional and integer solutions, where we iterate over the solution pool
$\mathcal{C}$. As described in Algorithm 1, for each tour $c$ in the pool, we
first repair it by removing the nodes whose prizes cannot be collected under
the current interdiction strategy $\bar{\mathbf{z}}$, unless this makes the
path longer. Then, we apply 2-Opt and Insert operations until the objective
value cannot be improved, or the prize threshold is exceeded. The latter means
that we are able to find a follower solution yielding a violated cut.

Input : Solution $\bar{\mathbf{z}}$ to ($\overline{\mbox{OIP}}$) (associating
objective function $\bar{t}$), a solution pool $\mathcal{C}$

Output : Possibly a feasible follower solution
$(\bar{\mathbf{x}},\bar{\mathbf{y}})$ with a total prize larger than $\bar{t}$

1 for  _each $c$ in $\mathcal{C}$_ do

2 Define a new set $c^{\prime}\leftarrow c$;

3 for  _each node $i\in V_{c^{\prime}}$_ do

4 if  _$\bar{z}_{i}=1$ and removing $i$ from $V_{c^{\prime}}$ does not
increase the length of tour $c^{\prime}$_ then

5 Remove $i$ from $V_{c^{\prime}}$;

6

7 end if

8

9 end for

10 set $\pi^{\prime}=\sum_{i\in V_{c^{\prime}}}p_{i}$, and set
$\pi^{\prime\prime}\leftarrow 0$;

11 while  _$\pi^{\prime\prime} <\pi^{\prime}\leq\bar{t}$_ do

12 $\pi^{\prime\prime}\leftarrow\pi^{\prime}$;

13 $c^{\prime}\leftarrow$ 2OPT($c^{\prime}$);

14 $c^{\prime},\pi^{\prime}\leftarrow$ INSERT($c^{\prime}$);

15

16 end while

17 if  _$\pi^{\prime} >\bar{t}$_ then

18 Return the follower’s solution $(\bar{\mathbf{x}},\bar{\mathbf{y}})$
associated with $c^{\prime}$;

19

20 end if

21

22 end for

Algorithm 1 FindHeuristicFolSoln

##### Follower preprocessing.

Given a leader solution $\bar{\mathbf{z}}$, let $i^{\prime}$ be a node
selected by the leader, i.e., $\bar{z}_{i^{\prime}}=1$. If there exists no
pair $a,b\in V$ such that $d_{ai^{\prime}}+d_{i^{\prime}b}<d_{ab}$, it is safe
to assume that the follower would not visit $i^{\prime}$ in an optimal tour
since its prize is not available to the follower anymore. In this case, we can
fix $y_{i^{\prime}}=0$ in (SEP). Otherwise, one of the following conditions
could hold in an optimal follower tour: (i) $i^{\prime}$ is not visited, (ii)
$i^{\prime}$ is visited between a node pair $a$ and $b$ where
$d_{ai^{\prime}}+d_{i^{\prime}b}<d_{ab}$, or (iii) $i^{\prime}$ is visited
between a node pair $a$ and $b$ where $d_{ai^{\prime}}+d_{i^{\prime}b}\geq
d_{ab}$, i.e., visited although it does not make the tour the shorter. In the
last case, removing $i^{\prime}$ would not compromise the optimality of the
follower’s tour since prize $p_{i^{\prime}}$ is not collected anyway. So,
exactly one of the following conditions must hold: $(y_{i^{\prime}}=0)$,
$(x_{a_{1}i^{\prime}}+x_{i^{\prime}b_{1}}=2),\ldots,(x_{a_{k}i^{\prime}}+x_{i^{\prime}b_{k}}=2)$,
where $(a_{k},b_{k})$ are all pairs with
$d_{a_{k}i^{\prime}}+d_{i^{\prime}b_{k}}<d_{a_{k}b_{k}}$. This result can be
used to strengthen the formulation (SEP) with additional constraints. The
details are provided in Algorithm 2.

Input : Leader solution $\bar{\mathbf{z}}$

Output : A set of additional constraints $\mathcal{CS}$ to be added to (SEP)

1 for  _each $i\in V\mid\bar{z}_{i}=1$_ do

2 if  _$d_{ai}+d_{ib}\geq d_{ab}$ for all $a,b\in V\setminus\\{i\\}$_ then

3 set $\mathcal{CS}\leftarrow\mathcal{CS}\cup\\{x_{i}\leq 0\\}$;

4

5 else

6 compute $\mathcal{W}=\\{(a,b)\mid a,b\in
V\setminus\\{i\\},d_{ai}+d_{ib}<d_{ab}\\}$;

7 create binary variable $b_{i0}$, set
$\mathcal{CS}\leftarrow\mathcal{CS}\cup\\{y_{i}\leq 1-b_{i0}\\}$;

8 initialize $k=0$;

9 for  _each $(a,b)\in\mathcal{W}$_ do

10 $k\leftarrow k+1$;

11 create binary variable $b_{ik}$, set
$\mathcal{CS}\leftarrow\mathcal{CS}\cup\\{x_{ai}+x_{ib}\geq 2b_{ik})\\}$;

12

13 end for

14 set
$\mathcal{CS}\leftarrow\mathcal{CS}\cup\\{\sum_{k^{\prime}=0}^{k}b_{ik^{\prime}}=1\\}$;

15

16 end if

17

18 end for

Algorithm 2 FollowerPreprocessing

##  3 A genetic algorithm for the OIG

In this section, we propose a genetic algorithm to solve the OIG. In a genetic
algorithm, it is often helpful if the fitness value of an individual
$z^{\prime}$ of the population would be equal to the objective function value.
For the OIG this would mean that the fitness value should be
$\Phi(z^{\prime})$, which is the optimal objective value of the OP under the
interdiction decision $z^{\prime}$. Hence, to evaluate the fitness of an
individual, we would need to solve an NP-hard problem. Thus, in the design of
our algorithm, for better time efficiency, we opt for a faster and heuristic
method to calculate the fitness values. Procedure EstimateObjective is very
similar to Algorithm 1 and uses a follower solution pool to generate a good
follower solution for the current interdiction strategy. Unlike Algorithm 1 it
does not take a target objective as input, but instead iterates over all pool
solutions and returns the best new solution obtained and its total prize. Note
that the resulting pair of leader and follower solutions may not be bilevel
feasible as the follower tour that EstimateObjective outputs is only a
heuristic solution for the given interdiction strategy (i.e., leader
solution), and to be feasible, it needs to be an optimal solution for the
given leader solution. However, this is not a problem since we use the fitness
value only to lead our search towards a better leader solution. To ensure
bilevel feasibility of the final solution, a post-processing step is carried
out to obtain the optimal follower tour.

The pseudocode of the genetic algorithm is provided as Algorithm 3. It starts
with the generation of an initial set of follower solutions $\mathcal{C}$ to
be used within EstimateObjective in later steps. In this step, we use the
heuristic algorithm in (Fischetti et al., 1998) to solve the OP, which takes
the optimal solution of the LP relaxation of the OP at the current B&C node,
generates a feasible tour in the first stage, and improves it in the second
stage. We refer the interested reader to (Fischetti et al., 1998) for further
details. In our case, we implement this method $k_{0}$ times, i.e., we solve
the LP relaxation of the follower problem for $k_{0}$ randomly generated
feasible $\mathbf{z}$ values. For each of them, once we get a feasible tour
and improve it as described by Fischetti et al. (1998), we remove, in turn,
one of the tour nodes and reapply the improvement procedure. We add the
resulting tour to $\mathcal{C}$ if it is not obtained in the previous
iterations.

Input : An instance of the OIG

Output : A feasible solution to OIG and an upper bound on ${\phi}^{\ast}$

1

2Initialize the follower solution pool $\mathcal{C}$ with a set of feasible
tours;

3 initialize the population $P=\emptyset$;

4 for  _$m=1,\ldots,p_{0}$_ do

5 $\hat{z}\leftarrow\texttt{Greedy}()$;

6 $P\leftarrow P\cup\hat{z}$;

7

8 end for

9for  _$it=1,\ldots,n_{maxIter}$_ do

10 if  _$it\equiv 0\ (\mathrm{mod}\ 10)$_ then

11 re-evaluate the fitness values of the $k$ fittest individuals by
EstimateObjective;

12

13 end if

14 $parent_{1}\leftarrow\texttt{K-Tournament}(P)$,
$parent_{2}\leftarrow\texttt{K-Tournament}(P)$;

15 $z^{\prime}\leftarrow\texttt{Crossover}(parent_{1},parent_{2})$;

16 $z^{\prime}\leftarrow\texttt{Mutation}(z^{\prime})$;

17 $z^{\prime}\leftarrow\texttt{Repair}(z^{\prime})$;

18 evaluate the fitness of $z^{\prime}$ using EstimateObjective;

19 if  _$|P|=p_{max}$_ then

20 $P\leftarrow(P\setminus\arg\max_{\hat{z}\in
P}\texttt{EstimateObjective}(\hat{z},\mathcal{C}))\cup z^{\prime}$ (replace
the individual with the worst fitness value with $z^{\prime}$);

21 else

22 $P\leftarrow P\cup z^{\prime}$

23 end if

24

25 end for

26re-evaluate the fitness values of all individuals;

27 choose the fittest individual $z^{\ast}=\arg\min_{\hat{z}\in
P}\texttt{EstimateObjective}(\hat{z},\mathcal{C})$;

28 solve the follower problem to optimality to obtain $\Phi(z^{\ast})$;

return $z^{\ast}$ and $\Phi(z^{\ast})$

Algorithm 3 GeneticAlgorithm

After initializing $\mathcal{C}$, we initialize the population with $p_{0}$
interdiction strategies obtained with a randomized greedy algorithm Greedy. It
starts with the computation of initial marginal gains, i.e., an estimate of
the decrease in the follower objective, due to interdicting each node in $V$
and storing them in a sorted list in decreasing order of gains. Then we
iterate in a lazy fashion and pick the first node in the list. If its gain is
not updated after the last interdiction decision, we recompute it with
probability $1-p_{s}$ and re-sort the list. With the skipping probability
$p_{s}$ we remove the node from the list. If the first node in the list has a
newly computed gain value, we choose it to be the next node to interdict. We
iterate until the interdiction budget $Q_{\ell}$ is reached or the list is
empty. For the computation of marginal gains at any stage of Greedy we use
EstimateObjective. Due to the skipping probability, at each call to Greedy we
obtain a different interdiction strategy, i.e., an individual.

The selection of the parents is made according to a $K$-way tournament
selection. For each of the two parents, $K$ individuals are randomly chosen
and the fittest one is selected as a parent. A one-point crossover operator
Crossover() is applied to the parents to generate a single offspring. Then,
the mutation operator Mutation() applies zero, one, or two random bit flips
with equal probabilities. If the offspring does not represent a feasible
leader solution, we repair it by switching ones to zeros at the bits with
smallest prize until the budget constraint is satisfied, which is denoted by
Repair(). The fitness of the offspring is then computed via
EstimateObjective(). We use a _steady-state (incremental)_ population
structure, where an offspring replaces the individual with the worst fitness
value immediately if the maximum population size $p_{max}$ is reached.

The accuracy of EstimateObjective depends on the quality and diversity of the
solutions in $\mathcal{C}$. Therefore, every time we call this procedure, we
add the resulting tour to $\mathcal{C}$ considering an upper bound on the size
of the pool. Since it is dynamically updated, the fitness value of an
individual may change and get closer to the true value when it is re-
calculated after some iterations. To better estimate the true objectives, we
re-calculate the fitness values of the best $k$ individuals at every 10
iterations. Similarly, once the iterations are over, we re-calculate the
fitness of each individual to determine the fittest one. Finally, to have a
bilevel feasible solution, we solve the follower problem optimally for the
selected leader solution corresponding to the fittest individual.

##  4 Computational results and discussion

All the algorithms we propose are implemented in C++. Whenever we need to
solve some MIPs or LPs they are solved via IBM ILOG CPLEX 12.10 at the default
settings. We make use of CPLEX callbacks to implement our B&C algorithm
(including the B&C algorithm to solve (SEP)). During our experiments, we used
the single core of an Intel Xeon E5-2670v2 machine with 2.5 GHz processor and
3GB of RAM. We set a time limit of one hour for all of our experiments.

###  4.1 Description of the instances

Our data set consists of a subset of the symmetric traveling salesman problem
instances available at TSPLIB (http://comopt.ifi.uni-
heidelberg.de/software/TSPLIB95/). Among these 111 available instances, we
select 38 for which the single-level OP can be solved optimally in less than
15 minutes in our environment, as our test instances.

For determining the node prizes, we consider two options: unit prizes, denoted
by $u$; and pseudorandom prizes, denoted by $r$. For random prizes, we follow
the approach in Fischetti et al. (1998) and generate the values according to
the equation $p_{i}=1+(7141i+73)\mod{100}$. Two interdiction budget levels
$Q_{l}\in\\{5,8\\}$ are considered. The distance budget is determined as
$B_{f}=0.5\nu$ where $\nu$ denotes the optimal TSP tour length which is
provided with the instances. The resulting instance set is available at
https://msinnl.github.io/pages/instancescodes.html.

###  4.2 Results of the B&C algorithm

In our experiments with the B&C algorithm, we consider the following
algorithmic settings that are obtained by including a subset of the
enhancement strategies we propose in Section 2.3:

  * •

I: Only integer solutions are separated, in an exact way.

  * •

IF: Both integer (exact) and fractional (heuristic) solutions are separated.

  * •

IFH: Both integer (heuristic + exact) and fractional (heuristic) solutions are
separated.

  * •

IFHC: In addition to IFH we keep a (follower) cut pool.

  * •

IFHCP: In addition to IFHC we apply FollowerPreprocessing.

The lower cutoff strategy is applied in all settings by default. The follower
solution pool $\mathcal{C}$ is used in all settings except I, where we do not
generate heuristic follower solutions. In setting IFH, while separating
integer solutions, we first try the heuristic method shown in Algorithm 1. If
it does not yield a violated cut, then we solve the follower problem optimally
to obtain a violated cut if there exists one (exact separation). Note that
whenever we keep a (follower) cut pool, its size is bounded by 5000 cuts in
total. In the experiments with fractional separation, at any (leader) B&C node
with a fractional node solution at most 10 passes of cut generation are
allowed.

In Table 1 and Table 2 we show some numerical results of our experiments, as
averages over the instances with the same leader budget $Q_{\ell}$. In the
columns we show the algorithmic setting, total running time in seconds
($t(s.)$), time to generate the interdiction cuts including the time to solve
(SEP) ($t_{\text{SEP}}(s.)$), the optimality gap at the end of time limit
(Gap(%)), the optimality gap at the root node (rGap(%)), the number of
optimally solved instances out of all 38 (nOpt), the number of B&C nodes
generated (nBBnode), the number of interdiction cuts at integer solutions
(intCuts), and the number of interdiction cuts at fractional solutions
(fracCuts). The numbers are averages over 38 instances.

Table 1: Average results of the unit-prize instances $Q_{\ell}$ | Setting | $t(s.)$ | $t_{\text{SEP}}(s.)$ | Gap(%) | rGap(%) | nOpt | nBBnode | intCuts | fracCuts
---|---|---|---|---|---|---|---|---|---
5 | I | 1746.8 | 1742.6 | 3.2 | 6.6 | 25 | 992.1 | 167.7 | 0.0
IF | 1378.2 | 1376.0 | 3.1 | 6.3 | 26 | 63.1 | 44.9 | 49.4
IFH | 747.0 | 741.3 | 0.2 | 4.6 | 33 | 484.1 | 453.6 | 150.1
IFHC | 277.9 | 273.8 | 0.0 | 4.4 | 38 | 647.0 | 382.8 | 180.9
IFHCP | 270.1 | 261.2 | 0.0 | 4.3 | 38 | 546.0 | 473.0 | 155.1
8 | I | 2329.8 | 2317.4 | 2.1 | 7.5 | 16 | 5833.5 | 433.4 | 0.0
IF | 2005.8 | 1990.7 | 1.7 | 7.2 | 19 | 547.2 | 113.7 | 712.4
IFH | 1206.8 | 1024.5 | 0.6 | 9.0 | 29 | 5926.0 | 2034.3 | 2770.8
IFHC | 761.0 | 490.9 | 0.1 | 9.0 | 35 | 7279.9 | 2471.4 | 3306.1
IFHCP | 766.1 | 536.2 | 0.2 | 9.1 | 34 | 5942.3 | 2548.4 | 3350.7
Table 2: Average results of the random-prize instances $Q_{\ell}$ | Setting | $t(s.)$ | $t_{\text{SEP}}(s.)$ | Gap(%) | rGap(%) | nOpt | nBBnode | intCuts | fracCuts
---|---|---|---|---|---|---|---|---|---
5 | I | 2281.2 | 2277.9 | 1.1 | 5.3 | 15 | 824.0 | 112.7 | 0.0
IF | 1888.6 | 1885.4 | 0.7 | 4.4 | 23 | 349.4 | 39.3 | 224.3
IFH | 1756.4 | 1753.2 | 0.7 | 4.7 | 24 | 515.2 | 81.5 | 264.4
IFHC | 1259.9 | 1252.0 | 0.3 | 4.6 | 30 | 860.7 | 131.3 | 437.9
IFHCP | 1142.9 | 1134.0 | 0.3 | 4.7 | 30 | 852.2 | 138.1 | 447.8
8 | I | 2545.9 | 2538.2 | 3.1 | 9.7 | 14 | 4477.5 | 188.2 | 0.0
IF | 2170.1 | 2155.3 | 2.3 | 8.1 | 18 | 1006.9 | 51.5 | 826.1
IFH | 2110.9 | 2095.4 | 2.3 | 8.5 | 17 | 1234.3 | 144.0 | 930.3
IFHC | 1900.0 | 1838.5 | 1.3 | 8.4 | 23 | 3639.3 | 224.4 | 2125.2
IFHCP | 1773.0 | 1704.4 | 1.1 | 8.5 | 23 | 3735.7 | 245.0 | 2320.9

The results indicate that separating fractional solutions is very effective in
decreasing the solution time and tree size. For the unit-prize instances,
separating integer solutions in a heuristic way also seems to significantly
decrease the solution time, through a reduced number of times we need to solve
(SEP). This is not the case for the random-prize instances, which we explain
by the poor quality heuristic solutions. Solving (SEP) usually cannot be
avoided because of failing to find a violated cut via the heuristic, even
though there exists one. Keeping a follower cut pool on the other hand, is
effective under both prize choices. It reduces the overall solution time by
reducing the time spent to solve (SEP). Lastly, FollowePreprocessing brings
some improvement in terms of solution time of the random-prize instances,
although its marginal contribution is not as large as of the other components.

Figure 2 shows the cumulative distribution of the running times of all
instances under different algorithmic settings. While we are able to solve 44%
of the instances optimally in one hour under the basic setting I, this ratio
is reached in two minutes under the setting IFHCP which is the best performer
in terms of run time.

Figure 2: Cumulative distribution of running times of all instances under
different B&C settings.

###  4.3 Results of the genetic algorithm

For our genetic algorithm, we consider the following parameter values, which
we determined in preliminary tests: Before the main iterations we initialize
the follower solution pool $\mathcal{C}$ by applying the heuristic of
Fischetti et al. (1998) $k_{0}=10$ times. An initial population of $p_{0}=20$
individuals is created via Greedy using a skipping probability $p_{s}=0.4$. At
every iteration 3-way tournament is applied to choose the parents. We allow a
maximum population size of $p_{max}=100$, and limit the size of $\mathcal{C}$
by 2000 as the complexity of EstimateObjective increases with it. Every 10
iterations the objective value of the fittest individual is re-evaluated,
which is likely to change its rank. The maximum number of iterations is
$n_{maxIter}=5000$.

In Table 3, we compare the B&C results with the results of the genetic
algorithm given in Algorithm 3. The table displays the results of each
instance, in terms of run time in seconds ($t(s.)$), the best objective value
obtained via Algorithm 3 ($z_{GA}$), the best objective value obtained via the
B&C method ($z_{BC}$), and their relative difference
$\Delta=100(z_{GA}-z_{BC})/z_{BC}$. Since not all $z_{BC}$ values are optimal
objective values, $\Delta$ shows how much the heuristic solution objective
value is far away from the best primal bound we have. The average solution
time of the genetic algorithm is less than three minutes over all instances,
whereas it finds solutions which are only 2.46% away from the B&C objective
values, on the average. The maximum deviation from $z_{BC}$ is 10.42% for
unit-prize instances and 13.29% for random-prize instances. These results
indicate that our genetic algorithm performs well in case we need to obtain a
high-quality feasible solution in short time.

Table 3: Genetic algorithm results compared to the B&C results. Unit-prize | Random-prize
---|---
Instance | Q | $t(s.)$ | $z_{GA}$ | $z_{BC}$ | $\Delta$ | Instance | Q | $t(s.)$ | $z_{GA}$ | $z_{BC}$ | $\Delta$
att48 | 5 | 12.84 | 26 | 26 | 0.00 | att48 | 5 | 10.90 | 1219 | 1219 | 0.00
att48 | 8 | 21.00 | 23 | 23 | 0.00 | att48 | 8 | 14.59 | 1103 | 1038 | 6.26
bayg29 | 5 | 5.23 | 12 | 12 | 0.00 | bayg29 | 5 | 3.18 | 603 | 603 | 0.00
bayg29 | 8 | 8.89 | 11 | 11 | 0.00 | bayg29 | 8 | 5.60 | 476 | 474 | 0.42
bays29 | 5 | 6.81 | 13 | 13 | 0.00 | bays29 | 5 | 4.08 | 630 | 630 | 0.00
bays29 | 8 | 4.63 | 11 | 11 | 0.00 | bays29 | 8 | 6.04 | 463 | 463 | 0.00
berlin52 | 5 | 20.61 | 31 | 31 | 0.00 | berlin52 | 5 | 19.55 | 1583 | 1548 | 2.26
berlin52 | 8 | 31.69 | 28 | 28 | 0.00 | berlin52 | 8 | 24.46 | 1372 | 1318 | 4.10
bier127 | 5 | 242.67 | 98 | 97 | 1.03 | bier127 | 5 | 337.43 | 4892 | 4883 | 0.18
bier127 | 8 | 250.25 | 95 | 95 | 0.00 | bier127 | 8 | 483.29 | 4622 | 4621 | 0.02
brazil58 | 5 | 32.22 | 40 | 40 | 0.00 | brazil58 | 5 | 20.24 | 1909 | 1884 | 1.33
brazil58 | 8 | 33.21 | 37 | 37 | 0.00 | brazil58 | 8 | 30.61 | 1673 | 1664 | 0.54
ch130 | 5 | 238.00 | 76 | 73 | 4.11 | ch130 | 5 | 322.17 | 3969 | 3908 | 1.56
ch130 | 8 | 294.88 | 74 | 70 | 5.71 | ch130 | 8 | 350.66 | 3758 | 3706 | 1.40
ch150 | 5 | 311.83 | 83 | 81 | 2.47 | ch150 | 5 | 677.18 | 4433 | 4399 | 0.77
ch150 | 8 | 368.94 | 83 | 78 | 6.41 | ch150 | 8 | 797.05 | 4270 | 4197 | 1.74
dantzig42 | 5 | 9.08 | 21 | 21 | 0.00 | dantzig42 | 5 | 6.37 | 1005 | 1005 | 0.00
dantzig42 | 8 | 11.93 | 19 | 18 | 5.56 | dantzig42 | 8 | 11.17 | 817 | 802 | 1.87
eil101 | 5 | 107.61 | 60 | 59 | 1.69 | eil101 | 5 | 95.97 | 3160 | 3151 | 0.29
eil101 | 8 | 140.35 | 58 | 56 | 3.57 | eil101 | 8 | 131.83 | 2992 | 2944 | 1.63
eil51 | 5 | 13.51 | 25 | 24 | 4.17 | eil51 | 5 | 10.54 | 1471 | 1379 | 6.67
eil51 | 8 | 21.61 | 24 | 23 | 4.35 | eil51 | 8 | 18.04 | 1260 | 1214 | 3.79
eil76 | 5 | 35.49 | 42 | 41 | 2.44 | eil76 | 5 | 24.86 | 2211 | 2144 | 3.13
eil76 | 8 | 43.07 | 40 | 39 | 2.56 | eil76 | 8 | 60.23 | 2034 | 1954 | 4.09
fri26 | 5 | 3.43 | 9 | 9 | 0.00 | fri26 | 5 | 2.32 | 455 | 410 | 10.98
fri26 | 8 | 4.77 | 7 | 7 | 0.00 | fri26 | 8 | 2.16 | 341 | 301 | 13.29
gr120 | 5 | 161.26 | 73 | 69 | 5.80 | gr120 | 5 | 304.69 | 3861 | 3829 | 0.84
gr120 | 8 | 220.86 | 69 | 66 | 4.55 | gr120 | 8 | 338.55 | 3608 | 3604 | 0.11
gr17 | 5 | 1.55 | 6 | 6 | 0.00 | gr17 | 5 | 0.92 | 194 | 194 | 0.00
gr17 | 8 | 1.04 | 3 | 3 | 0.00 | gr17 | 8 | 1.18 | 118 | 118 | 0.00
gr21 | 5 | 1.96 | 7 | 7 | 0.00 | gr21 | 5 | 1.72 | 303 | 303 | 0.00
gr21 | 8 | 1.80 | 5 | 5 | 0.00 | gr21 | 8 | 1.57 | 191 | 191 | 0.00
gr24 | 5 | 2.58 | 8 | 8 | 0.00 | gr24 | 5 | 2.23 | 469 | 430 | 9.07
gr24 | 8 | 2.74 | 6 | 6 | 0.00 | gr24 | 8 | 2.04 | 304 | 304 | 0.00
gr48 | 5 | 16.35 | 25 | 25 | 0.00 | gr48 | 5 | 10.17 | 1139 | 1130 | 0.80
gr48 | 8 | 22.72 | 22 | 22 | 0.00 | gr48 | 8 | 17.55 | 985 | 985 | 0.00
hk48 | 5 | 14.99 | 24 | 24 | 0.00 | hk48 | 5 | 12.71 | 1174 | 1167 | 0.60
hk48 | 8 | 23.95 | 23 | 22 | 4.55 | hk48 | 8 | 18.35 | 1110 | 1027 | 8.08
kroA100 | 5 | 68.38 | 54 | 51 | 5.88 | kroA100 | 5 | 112.90 | 2838 | 2745 | 3.39
kroA100 | 8 | 108.76 | 52 | 48 | 8.33 | kroA100 | 8 | 107.58 | 2645 | 2521 | 4.92
kroA150 | 5 | 289.02 | 83 | 80 | 3.75 | kroA150 | 5 | 593.48 | 4566 | 4473 | 2.08
kroA150 | 8 | 779.43 | 80 | 78 | 2.56 | kroA150 | 8 | 763.48 | 4344 | 4237 | 2.53
kroB100 | 5 | 77.17 | 54 | 52 | 3.85 | kroB100 | 5 | 201.57 | 2782 | 2725 | 2.09
kroB100 | 8 | 126.44 | 52 | 49 | 6.12 | kroB100 | 8 | 169.17 | 2634 | 2559 | 2.93
kroB150 | 5 | 443.80 | 83 | 81 | 2.47 | kroB150 | 5 | 536.86 | 4560 | 4524 | 0.80
kroB150 | 8 | 586.91 | 80 | 78 | 2.56 | kroB150 | 8 | 604.61 | 4388 | 4346 | 0.97
kroC100 | 5 | 73.05 | 51 | 50 | 2.00 | kroC100 | 5 | 118.48 | 2667 | 2575 | 3.57
kroC100 | 8 | 112.67 | 50 | 47 | 6.38 | kroC100 | 8 | 193.43 | 2453 | 2411 | 1.74
kroD100 | 5 | 66.62 | 55 | 53 | 3.77 | kroD100 | 5 | 102.16 | 2965 | 2786 | 6.42
kroD100 | 8 | 82.87 | 51 | 50 | 2.00 | kroD100 | 8 | 141.12 | 2810 | 2583 | 8.79
kroE100 | 5 | 64.75 | 53 | 51 | 3.92 | kroE100 | 5 | 65.01 | 2934 | 2859 | 2.62
kroE100 | 8 | 97.38 | 50 | 49 | 2.04 | kroE100 | 8 | 102.79 | 2795 | 2648 | 5.55
lin105 | 5 | 111.21 | 61 | 60 | 1.67 | lin105 | 5 | 72.78 | 3147 | 3135 | 0.38
lin105 | 8 | 143.84 | 58 | 57 | 1.75 | lin105 | 8 | 99.07 | 2924 | 2901 | 0.79
pr107 | 5 | 51.18 | 53 | 48 | 10.42 | pr107 | 5 | 179.06 | 2189 | 2189 | 0.00
pr107 | 8 | 133.05 | 45 | 45 | 0.00 | pr107 | 8 | 180.22 | 1926 | 1926 | 0.00
pr124 | 5 | 137.90 | 69 | 69 | 0.00 | pr124 | 5 | 156.18 | 3390 | 3364 | 0.77
pr124 | 8 | 138.02 | 66 | 66 | 0.00 | pr124 | 8 | 110.76 | 3227 | 3129 | 3.13
pr136 | 5 | 197.26 | 67 | 66 | 1.52 | pr136 | 5 | 297.52 | 3922 | 3830 | 2.40
pr136 | 8 | 269.29 | 67 | 64 | 4.69 | pr136 | 8 | 349.70 | 3766 | 3693 | 1.98
pr144 | 5 | 339.57 | 72 | 71 | 1.41 | pr144 | 5 | 146.42 | 3781 | 3514 | 7.60
pr144 | 8 | 259.29 | 72 | 68 | 5.88 | pr144 | 8 | 587.87 | 3499 | 3261 | 7.30
pr152 | 5 | 200.72 | 75 | 71 | 5.63 | pr152 | 5 | 328.82 | 3826 | 3763 | 1.67
pr152 | 8 | 290.43 | 71 | 69 | 2.90 | pr152 | 8 | 385.70 | 3619 | 3539 | 2.26
pr76 | 5 | 46.95 | 44 | 43 | 2.33 | pr76 | 5 | 47.73 | 2254 | 2247 | 0.31
pr76 | 8 | 52.13 | 42 | 41 | 2.44 | pr76 | 8 | 56.53 | 2059 | 2025 | 1.68
rat99 | 5 | 103.53 | 50 | 47 | 6.38 | rat99 | 5 | 85.97 | 2650 | 2596 | 2.08
rat99 | 8 | 128.07 | 48 | 45 | 6.67 | rat99 | 8 | 144.29 | 2553 | 2438 | 4.72
rd100 | 5 | 75.95 | 55 | 55 | 0.00 | rd100 | 5 | 108.51 | 3086 | 3007 | 2.63
rd100 | 8 | 101.07 | 52 | 52 | 0.00 | rd100 | 8 | 140.61 | 2938 | 2809 | 4.59
st70 | 5 | 38.16 | 38 | 37 | 2.70 | st70 | 5 | 36.05 | 1924 | 1855 | 3.72
st70 | 8 | 48.81 | 36 | 34 | 5.88 | st70 | 8 | 44.46 | 1730 | 1672 | 3.47
swiss42 | 5 | 11.40 | 22 | 22 | 0.00 | swiss42 | 5 | 6.97 | 1004 | 1004 | 0.00
swiss42 | 8 | 15.97 | 20 | 19 | 5.26 | swiss42 | 8 | 9.80 | 810 | 810 | 0.00
u159 | 5 | 642.95 | 87 | 87 | 0.00 | u159 | 5 | 761.40 | 4636 | 4551 | 1.87
u159 | 8 | 434.90 | 88 | 84 | 4.76 | u159 | 8 | 816.76 | 4379 | 4374 | 0.11
Average | 127.57 | 46.36 | 45.04 | 2.46 | Average | 173.00 | 2378.91 | 2325.86 | 2.47

##  5 Conclusions and future work

In this work, we propose the orienteering interdiction game where two players
(leader and follower) compete in a hierarchical manner: The follower tries to
maximize the total profit collected by visiting nodes (i.e., the sum of the
prizes of the visited nodes) and the leader wants to minimize this amount by
interdicting nodes (if a node is interdicted, the follower does not gain the
prize of the node when visiting it). Such a setting may be encountered during
political campaign planning to damage the effectiveness of the competitor’s
canvassing, in security operations where the routing-based activities of an
adversary agent is prevented, or in the analysis of worst-case scenarios of
the attacks towards patrolling security forces. This zero-sum Stackelberg game
can be modeled as a bilevel optimization problem and further reformulated as a
single-level problem adapting the so-called _interdiction cuts_ which were
introduced in Fischetti et al. (2019) for interdiction games fulfilling a
certain monotonicity assumption. We propose such a reformulation and develop a
branch-and-cut algorithm to solve it exactly. In addition, we develop a
genetic algorithm in which the fitness value of an individual is estimated
heuristically using a solution pool. We conduct a computational study by
creating instances of OIG using a set of TSP instances in the literature. The
results show that the performance of the branch-and-cut method can be
drastically improved by means of the proposed enhancement strategies. The
genetic algorithm yields solutions that are similar to the B&C solutions in
terms of the objective function value, in reasonable time.

There are various avenues for further work: It could be interesting to try to
design other exact solution algorithms, which do not use a reformulation based
on interdiction cuts. Moreover, the development of other heuristic algorithms
could also be a fruitful direction for further work. In particular, the fact
that obtaining the objective function value of any feasible solution requires
the solution of the NP-hard orienteering problem presents an intriguing
challenge in this context. Moreover, the OIG could be extended by adding
(topological) constraints to the leader problem, e.g., it could be imposed
that the leader also needs to solve an orienteering problem, and the nodes
visited by the leader in her or his tour are the nodes which are then
interdicted for the follower. Finally, it could also be interesting to
consider other orienteering problems, such as the team orienteering problem,
the orienteering problem with time windows, and the multi-period orienteering
problem in a similar game-theoretic setting.

##### Acknowledgments

E. Álvarez-Miranda acknowledges the support of the National Agency of Research
and Development (ANID), Chile, through the grant FONDECYT N.1180670 and
through the Complex Engineering Systems Institute ANID PIA/BASAL AFB180003.

## References

  * Beck et al. (2023) Beck, Y., Ljubić, I., Schmidt, M., 2023.  A survey on bilevel optimization under uncertainty.  European Journal of Operational Research 311, 401–426.
  * Bhatti et al. (2019) Bhatti, Y., Dahlgaard, J., Hansen, J., Hansen, K., 2019\.  Is door-to-door canvassing effective in europe? evidence from a meta-study across six european countries.  British Journal of Political Science 49, 279–290.
  * Bidgoli and Kheirkhah (2018) Bidgoli, M.M., Kheirkhah, A., 2018\.  An arc interdiction vehicle routing problem with information asymmetry.  Computers & Industrial Engineering 115, 520–531.
  * Brown et al. (2006) Brown, G., Carlyle, M., Salmerón, J., Wood, K., 2006\.  Defending critical infrastructure.  Interfaces 36, 530–544.
  * Calvete et al. (2011) Calvete, H.I., Galé, C., Oliveros, M.J., 2011.  Bilevel model for production–distribution planning solved by using ant colony optimization.  Computers & Operations Research 38, 320–327.
  * Camacho-Vallejo et al. (2022) Camacho-Vallejo, J.F., López-Vera, L., Smith, A.E., González-Velarde, J.L., 2022\.  A tabu search algorithm to solve a green logistics bi-objective bi-level problem.  Annals of Operations Research 316, 927–953.
  * Cerulli et al. (2023) Cerulli, M., Archetti, C., Fernandez, E., Ljubic, I., 2023\.  A bilevel approach for compensation and routing decisions in last-mile delivery.  arXiv preprint arXiv:2304.09170 .
  * Chao et al. (1996) Chao, I.M., Golden, B.L., Wasil, E.A., 1996.  The team orienteering problem.  European Journal of Operational Research 88, 464–474.
  * Church et al. (2004) Church, R.L., Scaparra, M.P., Middleton, R.S., 2004.  Identifying critical infrastructure: the median and covering facility interdiction problems.  Annals of the Association of American Geographers 94, 491–502.
  * Cruz-García et al. (2021) Cruz-García, S., Martínez-Farías, F., Santillán-Hernández, A., Rangel, E., 2021.  Mathematical home burglary model with stochastic long crime trips and patrolling: Applied to Mexico City.  Applied Mathematics and Computation 396, 125865.
  * Dantzig et al. (1954) Dantzig, G., Fulkerson, R., Johnson, S., 1954.  Solution of a large-scale traveling-salesman problem.  Journal of the Operations Research Society of America 2, 393–410.
  * Dantzig (1957) Dantzig, G.B., 1957.  Discrete-variable extremum problems.  Operations Research 5, 266–288.
  * Dempe and Zemkoho (2020) Dempe, S., Zemkoho, A., 2020\.  Bilevel optimization.  Springer.
  * DeNegre (2011) DeNegre, S., 2011.  Interdiction and discrete bilevel linear programming.  Lehigh University PhD thesis.
  * Fischetti et al. (2017) Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M., 2017\.  A new general-purpose algorithm for mixed-integer bilevel linear programs.  Operations Research 65, 1615–1637.
  * Fischetti et al. (2019) Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M., 2019\.  Interdiction games and monotonicity, with application to knapsack problems.  INFORMS Journal on Computing 31, 390–410.
  * Fischetti et al. (1998) Fischetti, M., Salazar-Gonzalez, J., Toth, P., 1998.  Solving the orienteering problem through branch-and-cut.  INFORMS Journal on Computing 10, 133–148.
  * Furini et al. (2019) Furini, F., Ljubić, I., Martin, S., San Segundo, P., 2019\.  The maximum clique interdiction problem.  European Journal of Operational Research 277, 112–127.
  * Golden et al. (1987) Golden, B., Levy, L., Vohra, R., 1987.  The orienteering problem.  Naval Research Logistics 34, 307–318.
  * Gunawan et al. (2016) Gunawan, A., Lau, H.C., Vansteenwegen, P., 2016.  Orienteering problem: A survey of recent variants, solution approaches and applications.  European Journal of Operational Research 255, 315–332.
  * Ilhan et al. (2008) Ilhan, T., Iravani, S.M., Daskin, M.S., 2008.  The orienteering problem with stochastic profits.  IIE Transactions 40, 406–421.
  * Israeli and Wood (2002) Israeli, E., Wood, R.K., 2002\.  Shortest-path network interdiction.  Networks: An International Journal 40, 97–111.
  * Jia et al. (2021) Jia, Y.H., Mei, Y., Zhang, M., 2021.  A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem.  IEEE Transactions on Cybernetics 52, 10855–10868.
  * Keskin et al. (2012) Keskin, B.B., Li, S.R., Steil, D., Spiller, S., 2012\.  Analysis of an integrated maximum covering and patrol routing problem.  Transportation Research Part E: Logistics and Transportation Review 48, 215–232.
  * Kheirkhah et al. (2016a) Kheirkhah, A., Navidi, H., Bidgoli, M.M., 2016a.  An improved benders decomposition algorithm for an arc interdiction vehicle routing problem.  IEEE Transactions on Engineering Management 63, 259–273.
  * Kheirkhah et al. (2016b) Kheirkhah, A., Navidi, H., Messi Bidgoli, M., 2016b.  A bi-level network interdiction model for solving the hazmat routing problem.  International Journal of Production Research 54, 459–471.
  * Kleinert et al. (2021) Kleinert, T., Labbé, M., Ljubić, I., Schmidt, M., 2021\.  A survey on mixed-integer programming techniques in bilevel optimization.  EURO Journal on Computational Optimization 9, 100007.
  * Labadie et al. (2012) Labadie, N., Mansini, R., Melechovskỳ, J., Calvo, R.W., 2012\.  The team orienteering problem with time windows: An lp-based granular variable neighborhood search.  European Journal of Operational Research 220, 15–27.
  * Laporte and Martello (1990) Laporte, G., Martello, S., 1990\.  The selective travelling salesman problem.  Discrete Applied Mathematics 26, 193–207.
  * Lim and Smith (2007) Lim, C., Smith, J.C., 2007.  Algorithms for discrete and continuous multicommodity flow network interdiction problems.  IIE Transactions 39, 15–26.
  * Lozano et al. (2017) Lozano, L., Smith, J., Kurz, M., 2017.  Solving the traveling salesman problem with interdiction and fortification.  Operations Research Letters 45, 210–216.
  * Lozano and Smith (2017) Lozano, L., Smith, J.C., 2017\.  A backward sampling framework for interdiction problems with fortification.  INFORMS Journal on Computing 29, 123–139.
  * Lupfer and Price (1972) Lupfer, M., Price, D., 1972\.  On the merits of face-to-face campaigning.  Social Science Quarterly , 534–543.
  * Marinakis and Marinaki (2008) Marinakis, Y., Marinaki, M., 2008\.  A bilevel genetic algorithm for a real life location routing problem.  International Journal of Logistics: Research and Applications 11, 49–65.
  * Marinakis et al. (2007) Marinakis, Y., Migdalas, A., Pardalos, P.M., 2007.  A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm.  Journal of Global Optimization 38, 555–580.
  * Nadizadeh and Sabzevari Zadeh (2021) Nadizadeh, A., Sabzevari Zadeh, A., 2021\.  A bi-level model and memetic algorithm for arc interdiction location-routing problem.  Computational and Applied Mathematics 40, 1–44.
  * Nikolakopoulos (2015) Nikolakopoulos, A., 2015.  A metaheuristic reconstruction algorithm for solving bi-level vehicle routing problems with backhauls for army rapid fielding.  Military Logistics: Research Advances and Future Trends , 141–157.
  * Ning and Su (2017) Ning, Y., Su, T., 2017.  A multilevel approach for modelling vehicle routing problem with uncertain travelling time.  Journal of Intelligent Manufacturing 28, 683–688.
  * Nyman (2017) Nyman, P., 2017.  Door-to-door canvassing in the European elections: Evidence from a Swedish field experiment.  Electoral Studies 45, 110–118.
  * Parvasi et al. (2019) Parvasi, S.P., Tavakkoli-Moghaddam, R., Taleizadeh, A.A., Soveizy, M., 2019\.  A bi-level bi-objective mathematical model for stop location in a school bus routing problem.  IFAC-PapersOnLine 52, 1120–1125.
  * Sadati et al. (2020a) Sadati, M.E.H., Aksen, D., Aras, N., 2020a.  The r-interdiction selective multi-depot vehicle routing problem.  International Transactions in Operational Research 27, 835–866.
  * Sadati et al. (2020b) Sadati, M.E.H., Aksen, D., Aras, N., 2020b.  A trilevel r-interdiction selective multi-depot vehicle routing problem with depot protection.  Computers & Operations Research 123, 104996.
  * Sefair et al. (2017) Sefair, J.A., Smith, J.C., Acevedo, M.A., Fletcher Jr, R.J., 2017\.  A defender-attacker model and algorithm for maximizing weighted expected hitting time with application to conservation planning.  IISE Transactions 49, 1112–1128.
  * Smith and Song (2020) Smith, J.C., Song, Y., 2020\.  A survey of network interdiction models and algorithms.  European Journal of Operational Research 283, 797–811.
  * Tahernejad et al. (2020) Tahernejad, S., Ralphs, T.K., DeNegre, S.T., 2020.  A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation.  Mathematical Programming Computation 12, 529–568.
  * Tang et al. (2016) Tang, Y., Richard, J.P.P., Smith, J.C., 2016.  A class of algorithms for mixed-integer bilevel min–max optimization.  Journal of Global Optimization 66, 225–262.
  * Tanınmış et al. (2022) Tanınmış, K., Aras, N., Altınel, İ.K., 2022.  Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks.  European Journal of Operational Research 297, 40–52.
  * Vansteenwegen et al. (2011) Vansteenwegen, P., Souffriau, W., Van Oudheusden, D., 2011.  The orienteering problem: a survey.  European Journal of Operational Research 209, 1–10.
  * Von Stackelberg (1952) Von Stackelberg, H., 1952.  The theory of the market economy.  Oxford University Press.
  * Wang and Xu (2017) Wang, L., Xu, P., 2017.  The watermelon algorithm for the bilevel integer linear programming problem.  SIAM Journal on Optimization 27, 1403–1430.
  * Wollmer (1964) Wollmer, R., 1964.  Removing arcs from a network.  Operations Research 12, 934–940.
  * Wood (1993) Wood, R.K., 1993.  Deterministic network interdiction.  Mathematical and Computer Modelling 17, 1–18.