# Models and Algorithms for the Minimum Spanning Tree Interdiction Problem

Luis Salazar-Zendeja

<figure><img src="image_1.png" /></figure>

## To cite this version:

Luis Salazar-Zendeja. Models and Algorithms for the Minimum Spanning Tree Interdiction Problem. Operations Research [math.OC]. Centrale Lille Institut, 2022. English. NNT: tel-04413097

HAL Id: tel-04413097

https://inria.hal.science/tel-04413097

Submitted on 23 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
CENTRALE LILLE

THÈSE

présentée en vue d'obtenir le grade de

DOCTEUR

en

Spécialité : Informatique

par

SALAZAR ZENDEJA Luis Alberto

DOCTORAT DELIVRE PAR CENTRALE LILLE

Titre de la thèse :

Modèles et Algorithmes pour le Problème d'Interdiction de
l'Arbre Couvrant de Poids Minimal

Models and Algorithms for the Minimum Spanning Tree
Interdiction Problem

Soutenue le 28 novembre 2022 devant le jury d'examen :

<table><tr><td>Présidente</td><td>Safia KEDAD-SIDHOUM</td><td>Professeure, CNAM</td></tr><tr><td>Rapporteur</td><td>François CLAUTIAUX</td><td>Professeur, Université de Bordeaux</td></tr><tr><td>Rapporteure</td><td>Yasmín Á. RÍOS SOLÍS</td><td>Professeure, Tecnológico de Monterrey</td></tr><tr><td>Examinatrice</td><td>Carmen GALÉ POLA</td><td>Professeure, Universidad de Zaragoza</td></tr><tr><td>Directeur de thèse</td><td>Frédéric SEMET</td><td>Professeur, Centrale Lille</td></tr><tr><td>Co-directrice de thèse</td><td>Martine LABBÉ</td><td>Professeure, Université Libre de Bruxelles</td></tr><tr><td>Co-Encadrant</td><td>Diego CATTARUZZA</td><td>MCF, Centrale Lille</td></tr></table>

Thèse préparée dans le laboratoire CRISTAL

École Doctorale MADIS-631 - Center Inria University of Lille - Centrale Lille
À mes parents,
à toute ma famille,
à mes professeurs,
et à mes chèr(e)s ami(e)s.
Acknowledgements

Many people were essential to the culmination of this four years adventure. I
would like to thank my esteemed supervisors Frédéric Semet, Diego Cattaruzza
and Martine Labbé for their invaluable supervision, support and tutelage during
my PhD degree. Thank you Diego for the countless talks and your continuous
advice, you have made me improve every time. Thank you Fédéric for pointing
out the small details of the research and your great expertise, which has helped
our work to progress. Thank you Martine for your insight and expertise, your
theoretical observations were certainly invaluable. Thank you again my supervi-
sors, all of you taught to become a good researcher and person. Working with
you was one of the best experiences of my life.

My gratitude extends to the CONACyT and Université de Lille for the funding
opportunity to undertake my studies at Centrale Lille.

I'd like to deeply thank my partner Valentin for all his support during the past
couple of years. Without him, this would not have been possible. I would like
to thank my friends, lab mates, colleagues and research team Tifaout, Matteo,
Natalia, Juan, Wenjiao, Wenjuan, Yuan, Mathieu, Arnaud, Sylvain, Raphaël,
Kaba, Francesco, Luce, Maxime, Helène, Pablo T., Pablo E., Pablo H., Pamela
and Edouard for a cherished time spent together in the lab, and in social settings.
Especially, to Tifaout for all our talks and advice and to Matteo for being a good
friend and roommate. Lastly, I would like to thank my parents, my family and
Valentin's family, whose endless support has given me the opportunity to focus
on my work.

Every one of you made my life better. I'll cherish all these memories forever.

Villeneuve d'Ascq, France

November, 2022

Luis Alberto SALAZAR ZENDEJA
ACKNOWLEDGEMENTS
# Contents

<table><tr><td>Acknowledgements</td><td>i</td></tr><tr><td>Table of Contents</td><td>ii</td></tr><tr><td>List of Figures</td><td>vi</td></tr><tr><td>List of Tables</td><td>viii</td></tr><tr><td>Abbreviations</td><td>xi</td></tr><tr><td>1 Introduction</td><td>1</td></tr><tr><td>1.1 Context</td><td>1</td></tr><tr><td>1.2 Interdiction Games</td><td>1</td></tr><tr><td>1.3 Thesis Objective and Organization</td><td>3</td></tr><tr><td>2 Literature Review</td><td>7</td></tr><tr><td>2.1 Deterministic Network Interdiction Problems</td><td>7</td></tr><tr><td>2.2 Literature Review on IGs</td><td>11</td></tr><tr><td>2.2.1 Maximum Flow Interdiction Problem</td><td>11</td></tr><tr><td>2.2.2 Shortest Path Interdiction Problem</td><td>13</td></tr><tr><td>2.2.3 Minimum Spanning Tree Interdiction Problem</td><td>14</td></tr><tr><td>2.2.4 Variants and Extensions</td><td>16</td></tr><tr><td>2.2.5 Applications</td><td>18</td></tr><tr><td>3 Formulations for the MSTI Problem</td><td>21</td></tr><tr><td>3.1 Bazgan et al. (2012) Formulation for the MSTI Problem</td><td>22</td></tr><tr><td>3.2 MSTI Formulation Based on Martin (1991) MST Formulation</td><td>24</td></tr><tr><td>3.3 Reformulation using Optimality Constraints</td><td>26</td></tr></table>
CONTENTS

<table>
  <tbody>
    <tr>
      <td>3.4</td>
      <td>Dual Formulations</td>
      <td>30</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>Total Interdiction Formulation</td>
      <td>32</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>Parameter Analyses and Illustrative Problem</td>
      <td>36</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>Valid Inequalities</td>
      <td>38</td>
    </tr>
    <tr>
      <td>3.7.0.1</td>
      <td>First Set of Valid Inequalities</td>
      <td>38</td>
    </tr>
    <tr>
      <td>3.7.0.2</td>
      <td>Second Set of Valid Inequalities</td>
      <td>40</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>Extension of the B̄-edge Connected Certificate</td>
      <td>41</td>
    </tr>
    <tr>
      <td>3.9</td>
      <td>Computational Experiments</td>
      <td>42</td>
    </tr>
    <tr>
      <td>3.9.1</td>
      <td>Instance Specifications</td>
      <td>42</td>
    </tr>
    <tr>
      <td>3.9.2</td>
      <td>Tuning Phase for Valid Inequalities</td>
      <td>42</td>
    </tr>
    <tr>
      <td>3.9.3</td>
      <td>Final Experimentation</td>
      <td>44</td>
    </tr>
    <tr>
      <td>3.10</td>
      <td>Conclusions</td>
      <td>54</td>
    </tr>
    <tr>
      <td>4</td>
      <td>A Branch-and-Price Algorithm for the MSTI Problem</td>
      <td>57</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Dantzig-Wolfe Decomposition</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>B&P Algorithm</td>
      <td>60</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Branching</td>
      <td>60</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Pricing Problem</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.2.2.1</td>
      <td>Strengthening of the Pricing Problem</td>
      <td>62</td>
    </tr>
    <tr>
      <td>4.2.2.2</td>
      <td>Heuristic for the Pricing Problem</td>
      <td>63</td>
    </tr>
    <tr>
      <td>4.2.3</td>
      <td>Lower Bound</td>
      <td>64</td>
    </tr>
    <tr>
      <td>4.2.4</td>
      <td>Overall presentation of the algorithm</td>
      <td>66</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Computational Experiments</td>
      <td>69</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Conclusions</td>
      <td>71</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Benders Decomposition for the MSTI Problem</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>A Benders Decomposition</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Lifted Optimality Cuts</td>
      <td>76</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Set Covering Constraints</td>
      <td>77</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Initialization of T̂ and the initial solution</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Upper and Lower Bounds of [MP(T̂)]</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Revised Benders Decomposition Algorithm</td>
      <td>79</td>
    </tr>
    <tr>
      <td>5.6.1</td>
      <td>Enhanced Master Problem</td>
      <td>79</td>
    </tr>
    <tr>
      <td>5.6.2</td>
      <td>Separation Procedure for the Lifted Optimality Cuts</td>
      <td>80</td>
    </tr>
    <tr>
      <td>5.6.3</td>
      <td>Implementation of the Revised BD Algorithm</td>
      <td>83</td>
    </tr>
  </tbody>
</table>
CONTENTS

<table><tr><td>5.7 Computational Experiments</td><td>86</td></tr><tr><td>5.7.1 Instance Generation</td><td>86</td></tr><tr><td>5.7.2 Computational Results</td><td>87</td></tr><tr><td>5.8 Conclusions</td><td>95</td></tr><tr><td><b>6 Conclusion and Recommendations</b></td><td><b>97</b></td></tr><tr><td>6.1 Thesis Summary</td><td>97</td></tr><tr><td>6.2 Future Research</td><td>99</td></tr><tr><td><b>References</b></td><td><b>102</b></td></tr><tr><td><b>Résumé Etendu</b></td><td><b>112</b></td></tr></table>
# CONTENTS
List of Figures

<table><tr><td>3.1 Comparison of formulation solutions</td><td>34</td></tr><tr><td>3.2 Illustrative example of G = (4, 6)</td><td>37</td></tr><tr><td>5.1 Example of lifting procedure</td><td>82</td></tr></table>
LIST OF FIGURES
# List of Tables

<table><tbody><tr><td>2.1</td><td>Main attributes of Interdiction Problems</td><td>20</td></tr><tr><td>3.1</td><td>Instance cases</td><td>36</td></tr><tr><td>3.2</td><td>Preliminary results of the first set of valid inequalities</td><td>43</td></tr><tr><td>3.3</td><td>Names of formulations with valid inequalities.</td><td>43</td></tr><tr><td>3.4</td><td>Preliminary results of the second set of valid inequalities</td><td>44</td></tr><tr><td>3.5</td><td>Computational results considering total interdiction and cardinality constraint.</td><td>48</td></tr><tr><td>3.6</td><td>Computational results considering partial interdiction and cardinality constraint.</td><td>49</td></tr><tr><td>3.7</td><td>Computational results considering total interdiction and knapsack constraint.</td><td>50</td></tr><tr><td>3.7</td><td>Computational results considering total interdiction and knapsack constraint. (continued)</td><td>51</td></tr><tr><td>3.8</td><td>Computational results considering partial interdiction and knapsack constraint.</td><td>52</td></tr><tr><td>3.8</td><td>Computational results considering partial interdiction and knapsack constraint. (continued)</td><td>53</td></tr><tr><td>4.1</td><td>Computational results for Cardinality Budget Constraint</td><td>70</td></tr><tr><td>4.2</td><td>Computational results for Knapsack Budget Constraint</td><td>71</td></tr><tr><td>5.1</td><td>Computational results for Type 1, 2 and 4 instances under total interdiction and cardinality budget constraint.</td><td>88</td></tr><tr><td>5.2</td><td>Computational results for Type 1, 2 and 4 instances under partial interdiction and cardinality budget constraint.</td><td>90</td></tr></tbody></table>
LIST OF TABLES

<table><tr><td>5.3</td><td>Computational results for Type 1, 2 and 4 instances under total interdiction and knapsack budget constraint.</td><td>91</td></tr><tr><td>5.4</td><td>Computational results for Type 1, 2 and 4 instances under partial interdiction and knapsack budget constraint.</td><td>92</td></tr><tr><td>5.5</td><td>Computational results for Type 3 instances considering a cardinality budget constraint.</td><td>93</td></tr><tr><td>5.6</td><td>Computational results for Type 3 instances considering a knapsack budget constraint.</td><td>94</td></tr></table>
Abbreviations

<table><tr><td>IG</td><td>Interdiction Game</td></tr><tr><td>MFI</td><td>Maximum Flow Interdiction</td></tr><tr><td>SPI</td><td>Shortest Path Interdiction</td></tr><tr><td>MST</td><td>Minimum Spanning Tree</td></tr><tr><td>MSTI</td><td>Minimum Spanning Tree Interdiction</td></tr><tr><td>B&P</td><td>Branch-and-Price</td></tr><tr><td>BD</td><td>Benders Decomposition</td></tr><tr><td>MP</td><td>Master Problem</td></tr></table>
# Chapter 1

# Introduction

## 1.1 Context

Prevention is an important aspect of any operation to ensure its proper functioning. Some processes where prevention plays a key role are transportation, deliveries or production. Natural disasters and man-made disruptions are examples of what can cause them to malfunction which, in most cases, leads to undesired results or even to no results at all. For instance, a manufacturing company must know how to react when a machine failure compromises its supply chain. It must anticipate no production, delays, lost of profits, among others. An analysis in operations within an optimization framework is a must.

The modeling of these situations under an Interdiction Game (IG) setting is one of the most practical ways to guarantee the best results. An IG seeks a strategy that causes the most damage to the operations of a process. It is possible to decide whether to invest in additional security measures at critical points or to deploy alternate procedures once the worst-case scenario that operations may encounter is known.

## 1.2 Interdiction Games

An IG involves two non-cooperative entities interacting with each other. The first entity, called the *interdictor*, seeks to disrupt the optimization processes or settings of the second entity, called the *defender*. In the normal setting of an IG, the interdictor acts first then the defender reacts with full knowledge of the
interdictor's actions. The scope of the interdictor ranges from modifying the defender's assets to their total destruction in order to worsen the objective of the defender.

IGs have received a lot of attention because of their practical setting. Military operations (Wollmer (1964)), critical infrastructure of electric grids (Salmeron et al. (2004), Yuan et al. (2011)), law enforcement (Tsai et al. (2010)) and prevention of natural disasters (Yuan et al. (2016)) are some application domains in which the IGs are applied.

One of the most studied problems is the one presented in Morton et al. (2007). The authors model a situation in which an individual who carries nuclear material travels through a network between an origin and a destination. Each link of the network is associated with a probability of traverse it without being detected. The smuggler's objective is to traverse the network undetected while the nuclear plant security personnel attempts to intercept him. Detection is done by installing radiation sensors over the links of the network such that their probabilities to be traversed are diminished. This problem is often referred to in the literature as the most reliable path, as the defender tries to find the path that maximizes the chance of escape.

The work of Wood (1993) studies the Maximum Flow Interdiction (MFI) problem. The defender wishes to compute the maximum flow on a capacitated network. The objective of the interdictor is to minimize the maximum flow of the network by eliminating some of its arcs. However, the interdictor has limited resources to do so. This work is motivated by the direct application of the MFI problem to the degradation of drug flows in South America.

The Shortest Path Interdiction (SPI) problem is considered in Israeli & Wood (2002). The shortest path in a network between the source and sink nodes is computed by the defender while the interdictor, constrained by a budget, disrupts the network by altering the weight of the arcs. The proposed formulations can handle partial interdiction, i.e. an increment on the weight of the arc, as well as complete destruction of the arc, that is, total interdiction.

The Minimum Spanning Tree Interdiction (MSTI) problem is defined similarly as the two previous problems. The interdictor seeks to allocate the available resources in order to modify the network topology in which the defender computes the minimum spanning tree so that its weight has the largest increment.
The maximum number of edges the interdictor can interdict is imposed by a bud-
get constraint. The budget constraint can be defined as cardinality constraint,
the interdiction weight of each edge is the same, or a knapsack constraint, the
interdiction weights are different. The first work related to the MSTI problem is
Hsu et al. (1991). They consider a special case where the interdictor eliminates
only one edge of the network. In Jan et al. (1992), the work is extended so that
the interdictor removes an arbitrary number of edges. The most recent work on
the MSTI problem is Wei et al. (2021) where different mathematical formulations
are introduced and compared. The presented models take advantage of the MSTI
problem structure. The authors also identify a family of valid inequalities which
under a processing of the instance parameters provides an even stronger formula-
tion. The articles addressing the MSTI problem provide a variety of models and
resolution methods. However they all consider some special cases. For instance,
Bazgan et al. (2012) introduces an efficient algorithm that solves the MSTI prob-
lem when the interdictor eliminates a fixed number of edges. Wei et al. (2021)
focuses on the same case as well. The partial interdiction variant, i.e., the inter-
dictor only increases the weight of the edges, has received little attention. The
research in Frederickson & Solis-Oba (1999) and Baïou & Barahona (2008) pro-
pose algorithms that solve this variant but a study on mathematical formulations
is missing.

1.3 Thesis Objective and Organization

To the best of our knowledge, no algorithm has been explicitly designed to solve
the general MSTI problem. This thesis proposes models and algorithms for a
generalization of MSTI problem. The latter is obtained by considering both types
of interdiction, total and partial interdiction. In addition, the interdictor can be
limited by a budget constraint, modeled as a knapsack constraint. A cardinality
constraint, which is a special case, is also considered. The work presented in this
thesis is structured as follows.

A literature review of the MFI, SPI and MSTI problems is presented in Chap-
ter 2. We start by introducing the concept of Stackelberg games and bilevel opti-
mization. Afterwards, their relation to IGs is explained. A general formulation for
deterministic network interdiction problems is stated. The literature of the three
network problems considered is discussed. Mainly, the discussion focuses in the special cases that were treated and the different algorithms that were designed. Variants and applications of each of the network problems are also reviewed.

Chapter 3 introduces seven mathematical models for the MSTI problem. A first formulation retrieved from the literature is recalled. A second original model based on a linear formulation of the MST problem (Martin (1991)) is presented. The latter formulation is a max – min non-linear problem. Therefore, it is reformulated and linearized to obtain a single-level linear problem. In addition, valid inequalities are developed to strengthen the model. Two additional based on the dual problem of the max – min non-linear problem are proposed. All formulations handle both types of interdiction. A last model that only considers total interdiction case is presented. Instances are generated as those from the literature and used to compare the efficiencies of our formulations.

The MSTI problem is then solved by a Branch-and-Price algorithm in Chapter 4. The most compact formulation defined in Chapter 3 is used to define the restricted master problem and the pricing problem. The latter is obtained by applying a Dantzig-Wolfe decomposition. A family of constraints that rules out irrelevant interdiction strategies is developed and added to the pricing problem. Then, a column generation algorithm embedded in a Branch-and-Bound scheme is presented. Computational experiments are carried out on the instance set generated in Chapter 3.

The main contribution of this thesis is presented in Chapter 5. A Benders Decomposition algorithm is developed to tackle the MSTI problem. A MSTI formulation is decomposed into a Master Problem (MP) and a sub-problem. A family of valid inequalities is also proposed to tighten the linear relaxation of the MP. The sub-problem, parameterized by the solution of the MP, consists only on the computation of a MST. The Benders Decomposition algorithm is implemented through a commercial solver. The MP is solved to optimality only once and the sub-problem is solved in user-defined methods that are given to the solver. Four types of instances are generated. Instances differentiate from each other in the range of the weight of the edges and the density of the network. The algorithm is assessed for each of the four possible configurations according to the type of interdiction and budget constraints.
The manuscript concludes in Chapter 6 with general conclusions of the thesis.
Limitations and future works are also discussed.
# 1. INTRODUCTION
# Chapter 2

## Literature Review

This chapter presents the literature related to Interdiction Games (IG). We begin by discussing Stackelberg Games, which provide a general structure of problems to which IGs belong. The concept of bilevel optimization is introduced and its relation to IGs is explained. A general structure for several network interdiction problems is presented. Results of the latter problems is discussed. The chapter concludes with applications of these problems.

### 2.1 Deterministic Network Interdiction Problems

The individual who has final authority over a decision process is called the decision-maker. A Stackelberg Game is a problem in which several decision-makers interact in a hierarchical structure (Von Stackelberg (1934)). In the most simple case of a Stackelberg Game, there are two parties, commonly referred to as leader and follower. They play a two-turn game in which the leader makes decisions first and the follower acts later. The leader's strategy is to anticipate the follower's actions whereas the follower is limited to react to the leader's decisions.

Bilevel programming or bilevel optimization are optimization paradigms in which only two decision makers play a Stackelberg Game (Dempe (2002)). The general bilevel optimization problem is defined as follows:

$$ \min_{x \in X, y \in Y} F(x, y) \qquad (2.1a) $$

s.t.
$$G_h(\mathbf{x}, \mathbf{y}) \geq 0 \qquad \forall h \in \mathcal{H} \qquad (2.1b)$$

$$\mathbf{y} \in \Psi(\mathbf{x}) \qquad (2.1c)$$

where $n_x$ denotes the number of variables of the leader and $n_y$ the number of variables of the follower, $\mathbf{x} \in \mathbb{R}^{n_x}$, $\mathbf{y} \in \mathbb{R}^{n_y}$, $F: \mathbb{R}^{n_x} \times \mathbb{R}^{n_y} \to \mathbb{R}$ and $G_h: \mathbb{R}^{n_x} \times \mathbb{R}^{n_y} \to \mathbb{R}$ for all $h \in \mathcal{H}$. $\mathcal{X} \subseteq \mathbb{R}^{n_x}$ defines the domain of variables $\mathbf{x}$. $\Psi(\mathbf{x})$ is a set parameterized by $\mathbf{x}$. This set contains the optimal solutions of the next problem:

$$\begin{array}{ll}
\min_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y}) & (2.2a) \\
\text{s.t.} \quad g_j(\mathbf{x}, \mathbf{y}) \geq 0 & \forall j \in \mathcal{J}
\end{array}$$

where $f: \mathbb{R}^{n_x} \times \mathbb{R}^{n_y} \to \mathbb{R}$, and $g_j: \mathbb{R}^{n_x} \times \mathbb{R}^{n_y} \to \mathbb{R}$ for all $j \in \mathcal{J}$ and $\mathcal{Y} \subseteq \mathbb{R}^{n_y}$ denote the domain of variables $\mathbf{y}$. The leader controls variables $\mathbf{x}$ and the follower variables $\mathbf{y}$. Thus, the leader's (or upper level) and follower's (or lower level) problems are (2.1) and (2.2), respectively.

Bilevel problems can model a variety of hierarchical problems. Either the upper level or lower level can represent linear, mixed-integer, quadratic problems, etc. This makes bilevel problems complicated to solve and even in its simplest form, i.e. where both upper level and lower level are linear problems, are NP-hard (Kleinert et al. (2021)). The reader is referred to Dempe et al. (2015), Vicente & Calamai (1994), Lachhwani & Dwivedi (2018) for surveys on bilevel optimization.

An IG is a special case of bilevel programming. The leader and the follower take on the roles of interdictor and defender, respectively. Both entities play a Stackelberg game in which the objective of both players is the same but optimized in opposite directions. During the first turn, the leader selects his interdiction plan, i.e. a set of decisions that will restrict the follower's actions. In the second turn, the follower knows the interdictor's actions and he reacts optimally. Throughout this manuscript, leader, upper level and interdictor are used interchangeably. Similarly, for follower, lower-level and defender.

The defender has no control over the actions of the interdictor. For example, a transportation company cannot control the closure of roads or highways by the government during a crisis. Moreover, the only purpose of the interdictor is to
worsen the defender's objective. This means that given a solution $\mathbf{x}$ of the upper level problem, any optimal solution of the lower level problem has the same effect on the leader's objective. Therefore, a general IG formulation is defined as:

$$ \max_{\mathbf{x} \in \mathcal{X}} \min_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y}) \qquad (2.3) $$

where $\mathcal{X} := \{\mathbf{x} \in \bar{\mathcal{X}} \subseteq \mathbb{R}^{n_x} | G_h(\mathbf{x}, \mathbf{y}) \ge 0, \forall h \in \mathcal{H}\}$ and $\mathcal{Y} := \{\mathbf{y} \in \bar{\mathcal{Y}} \subseteq \mathbb{R}^{n_y} | g_j(\mathbf{x}, \mathbf{y}) \ge 0, \forall j \in \mathcal{J}\}$. Sets $\bar{\mathcal{X}} \subseteq \mathbb{R}^{n_x}$ and $\bar{\mathcal{Y}} \subseteq \mathbb{R}^{n_y}$ determine the nature of the variables, i.e. binary, integer, continuous, etc.

In this thesis, we tackle problems where formulation (2.3) is applied on networks. These problems are known as Network Interdiction problems and are the most studied type of IGs. Formally, the classical network interdiction problem is a game in which the defender optimizes a process over a network, i.e. the space $\mathcal{Y}$ defines a shortest path, maximum flow or minimum spanning tree problem and the interdictor, constrained by a budget, deletes or modifies the network topology to optimize the defender's objective in the opposite direction.

We now define the general notation for the following sections. Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be an undirected graph, where $\mathcal{V}$ represents the set of nodes and $\mathcal{E}$ the set of edges. Each edge $e \in \mathcal{E}$ is associated with:

* a non-negative weight/length/capacity indicated with $c_e$; this is the value of the edge $e$ when it does not suffer from interdiction;

* an non-negative interdiction cost indicated with $b_e$, that has to be paid to interdict the corresponding edge;

* an interdiction augmentation (or decrement) indicated with $d_e$: if the edge $e$ is interdicted, its weight/length/capacity becomes $c_e + d_e$.

Total interdiction and partial interdiction are the two types of interdiction considered. Total interdiction is defined as the complete destruction of the edge while partial interdiction modifies the weight of the edge. If $d_e = \pm\infty$, the edge value becomes $\pm\infty$ and the interdiction action equals to edge removal. The interdiction on the edge implies that it does not exist anymore in the graph and cannot be used by the defender. If $d_e$ is finite, the edge value is increased (or
decreased) by $d_e$ units and is still present in the graph: it then might be utilized by the defender at a cost $c_e + d_e$.

This thesis focuses on deterministic network interdiction problems with the following structure:

$$ \max_{\mathbf{x} \in \mathcal{X}} \min_{\mathbf{y} \in \mathcal{Y}} \sum_{e \in \mathcal{E}} (c_e + d_e x_e) y_e \quad (2.4) $$

The objective function of (2.4) calculates the cost or weight of the structure defined by $\mathcal{Y}$ on graph $\mathcal{G}$ with augmented weights. Throughout this manuscript, the feasible space of the interdicator is defined as $\mathcal{X} := \{\mathbf{x} \in \{0, 1\}^{|\mathcal{E}|} \mid \sum_{e \in \mathcal{E}} b_e x_e \le B\}$ where $B$ is the budget of the interdicator. An element $\mathbf{x} \in \mathcal{X}$ is referred to as interdiction plan or interdiction strategy. When $b_e = 1$ for all $e \in \mathcal{E}$, the constraint $\sum_{e \in \mathcal{E}} b_e x_e \le B$ is referred as cardinality constraint, since it basically imposes an upper bound on the number of edges that can be interdicted. On the other hand, we refer to it as knapsack constraint when there exist at least one edge $\bar{e} \in \mathcal{E}$, such that $b_{\bar{e}}$ is different from 1 for its similarity with the capacity constraint in the knapsack problem.

The minimum cut value of $\mathcal{G}$ calculated with respect to $b_e$ values is referred to as connectivity number. Large values of $B$, i.e. values greater or equal to the connectivity number, allow the interdicator to disconnect the network when assuming total interdiction. As a consequence, any of the aforementioned network problems have a solution and the instance becomes trivial. In the rest of the paper, we will assume that the budget is not large enough for this to happen when considering total interdiction.

The above notation is edge-based. To treat arc-based problems the notation is modified as follows. Let $\mathcal{D} = (\mathcal{V}, \mathcal{A})$ define a digraph where $\mathcal{A}$ is a set of $(i, j)$ arcs. For each arc $(i, j) \in \mathcal{A}$, parameters $c_{ij}$, $d_{ij}$ and $b_{ij}$ are defined analogously. Arcs of the form $(i, i)$ do not exist in $\mathcal{D}$. Denote by $\delta^+(i)$ and $\delta^-(i)$ the sets of outgoing and incoming arcs of node $i$, respectively.
## 2.2 Literature Review on IGs

Three of the problems introduced in Chapter 1 fall under the modeling scheme (2.4), i.e. the Maximum Flow Interdiction (MFI), Shortest Path Interdiction (SPI) and the Minimum Spanning Tree Interdiction (MSTI) problems. The main results and variants of these problems are presented below. Whenever the problem contains a special node as a source (resp. sink), it will be indicated by $s$ (resp. $t$).

We start by defining the special cases of network interdiction problems that are commonly found in the literature. The most basic case of interdiction problem (2.4), assuming total interdiction, is the most vital edge (or link) and it is obtained by setting $b_e = 1$ for all $e \in \mathcal{E}$ and by defining $B = 1$. Thus the interdictor looks to disrupt the edge that causes the largest increment (or decrement) in the objective function of the defender. A generalization of the most vital edge problem is the $\bar{B}$-most vital edges (links). It is defined by considering a cardinality constraint ($b_e = 1$ for all $e \in \mathcal{E}$) and a budget strictly greater than one, $\bar{B} = B > 1$. The goal is to remove $\bar{B}$ edges (links) of the network that worsen the most the objective value of the defender.

Partial interdiction is defined as a finite increase (or decrease) of $c_e$. Thus, the defender problem is redefined in a graph with modified weights. The latter can be modeled in two different ways: the discrete and continuous version. The discrete version consists in deciding whether to increase the edge weight exactly by $d_e$ units or not. The weight of the edges in the continuous version of partial interdiction are defined as $c_e + x_e$ where $x_e \ge 0$. The latter version of partial interdiction is out of the scope of formulation (2.4), however this specific way to model is the one considered in the literature when dealing with partial continuous interdiction. In the following sections, we present how these variants are treated in the literature for the MFI, SPI and MSTI problems.

### 2.2.1 Maximum Flow Interdiction Problem

The MFI problem is a network interdiction problem in which the interdictor selects a set of edges to interdict in order to minimize the maximum network flow that is computed by the defender. Let $\mathcal{Y}$ define a maximum flow problem. The MFI problem cannot be directly model by (2.4) since it is a min-max
problem. Therefore, the senses of the objectives are simply interchanged since we can model a decrement on the flow of the edges by defining negative values of $d_e$. In addition, the MFI problem is usually formulated in an arc-based notation, therefore we consider the corresponding arc-based notation introduced above. The MFI problem is proven to be strongly NPN-Complete in Wood (1993) even when $b_{ij} = 1$ for all $(i, j) \in A$. The works of Wollmer (1963) and Lubore et al. (1971) address the most vital link for the MFI. Lubore et al. (1971) improves the work of Wollmer (1963) by introducing a labeling algorithm that reduces the number of candidates to be the most vital link. Basically, their algorithms calculates the maximum flow on $D_{ij} = (V, A \setminus \{(i, j)\})$ for each arc $(i, j)$ in the candidate list.

The work of Wollmer (1964) tackles the $\bar{B}$-most vital links for the MFI problem. Their solving method reduces the $\bar{B}$-most vital links of the MFI problem to a problem related to the $\bar{B}$-most vital links of the SPI problem due to the equivalence between the minimum cut and the computation of the shortest path in the topological dual of the network. This approach is only valid for planar graphs. Ratliff et al. (1975) characterizes the $\bar{B}$ links to remove as a particular cut of $D$. This cut is obtained by sequentially modifying the network based on disconnecting sets of $D$ so that this cut becomes the one with the lowest capacity.

The research in McMasters & Mustin (1970) solves a version the MFI problem considering partial interdiction where the interdictor spends resources per unit of reduced arc capacity. The latter is done by redefining $X := \{\mathbf{x} \in \mathbb{R}^{|A|} \mid \sum_{(i,j) \in A} b_{ij}(c_{ij} - x_{ij}) \le B, x_{ij} \ge 0 \ \forall (i,j) \in A\}$ and by modifying one of the defender's constraints to $y_{ij} \le c_{ij} - x_{ij}$, i.e. the flow cannot exceed the reduced capacity of the arc. In Wood (1993) the decrement of an arc's capacity is determined by $(1 - x_{ij})c_{ij}$. The author in Phillips (1993) analyses the complexity of the latter problem. She proved the strongly NPN-Completeness of the problem for general graphs. For bandwidth-$i$ graphs ($i \ge 3$), grid graphs, series-parallel graphs and Halin graphs the complexity becomes weakly NPN-Complete.

Formulation (2.4) where $Y$ defines a maximum flow problem is proposed in Wood (1993). The formulation is then transformed into a linear single-level problem. The adaptability of this formulation to different variants, such as multiple sources and sinks, multiple commodities, undirected networks or multiple resources, is the main contribution of his work. Finally, he proposes valid inequal-
ities to strengthen the LP relaxation of the model. Two more families of valid inequalities are presented in Altner et al. (2010). In addition, they also show that the optimality gap of the MFI problem is not bounded from below by a constant. Two equivalent formulations and a family of valid inequalities under the cardinality constraint are presented in Afshari Rad & Kakhki (2017). Their work proved to provide better LP relaxations than those of Wood (1993) and Altner et al. (2010).

### 2.2.2 Shortest Path Interdiction Problem

In the SPI problem the defender calculates the shortest path between the source node $s$ and the sink node $t$, whereas the interdictor, with her limited budget, modifies the topology of the graph to maximize the length of the shortest $s-t$ path. The work of Ball et al. (1989) shows that the $\bar{B}$-most vital links is $\mathcal{NP}$-hard, therefore the general SPI problem defined by (2.4) is $\mathcal{NP}$-hard as well.

A first algorithm of complexity $O(|V|^4)$ of the most vital link for the SPI problem is presented in Corley & Sha (1982). Implicitly, they calculate the shortest path on the graph $(V, E \setminus \{e\})$ for each $e$ of the common edges of the shortest paths of $G$. In Malik et al. (1989), the authors start by formally stating that the most vital link is one of the arcs of the shortest $s-t$ path. They use this result and Dijkstra's algorithm for the shortest path problem to develop an algorithm of complexity $O(|V|^2)$.

The exact algorithm proposed in Malik et al. (1989) for the $\bar{B}$-most vital links of the SPI problem consists in generating and ordering all $s-t$ paths in non-decreasing lengths. The interdiction is attempted on the graph formed by the union of the first $l$ paths. The latter is done sequentially until the interdiction becomes infeasible. Then, the longest path generated is the optimal solution. The complexity of this algorithm is $O(Cr)$ where $C$ and $r$ represent the number of generated paths and $r$ the complexity of finding all paths from $s$ to all other nodes, respectively. In Ball et al. (1989), it is shown that a problem related to the SPI problem, which is solved in polynomial time, provides a lower bound for the optimal value of the SPI problem.

The continuous version of the SPI problem is first addressed in Fulkerson & Harding (1977). The author provides a formulation of this version of the SPI problem and then, its equivalence to a minimum-cost flow problem is determined.
Golden (1978) treats a similar problem where the weight of the path is to be increased by a minimum of $τ$ units. The objective function is to minimize the cost needed to obtain such increment since the increment is given. Again, this problem is shown to be reduced to a minimum-cost flow problem therefore it is solved in polynomial time.

In Israeli & Wood (2002), it is presented the formulation (2.4) for the SPI problem, i.e. the constraints in set $Y$ are those of a shortest path problem. The authors present a Benders decomposition approach where the restricted master problem maximizes the lengths of paths that belong to a restricted collection of $s-t$ paths by interdicting at least one of the arcs of each path. Given a solution of the master problem, the sub-problem solves a shortest path problem parameterized by the interdiction plan defined by the master problem's solution. The master problem and sub-problem are iteratively solved until the lower and upper bounds are equal. A set covering based decomposition is also considered. The idea of this decomposition is that for a given feasible solution of the SPI problem with value $v'$, the optimal interdiction plan has to interdict at least one arc on all $s-t$ paths that have a length less than $v'$. If one of these paths is not interdicted by the optimal interdiction plan then the defender can choose this path as his optimal solution which has a worst objective value. Super valid inequalities are introduced, i.e. valid inequalities that eliminate integer feasible solutions, except for optimal ones. Basically, as the Benders decomposition algorithm finds better lower bounds, super valid inequalities are defined to force certain interdiction variables to be positive in order to force the master problem to give a solution of at least the value of the lower bound. Finally, an enhanced Benders decomposition which includes both super valid inequalities and covering cuts is presented. The covering cuts follow the same idea of the set covering based decomposition in which paths that have a length less than the lower bound have to be interdicted.

### 2.2.3 Minimum Spanning Tree Interdiction Problem

In this section, the related literature with respect to the MSTI problem is presented. In this network problem, the defender seeks to calculate the Minimum Spanning Tree (MST) of $G$. As in the previous problems, the interdictor uses a limited amount of resources to alter the topology of the network in order to worsen the defender's objective. The MSTI problem was proven to be $NP$-Hard
in Lin & Chern (1993). As in the SPI problem, it is proven that the edge that, when removed, causes the largest increase in the weight of the MST is one of its own edges. Let $T_0$ be the edge set that defines the MST of $\mathcal{G}$. A replacement edge of an edge $e \in T_0$ is an edge $e' \in \mathcal{G} \setminus T_0$ such that $T_0 \setminus \{e\} \cup \{e'\}$ defines a spanning tree and this replacement induces the least increment on the weight of $T_0$. Two algorithms that use this result are proposed in Hsu et al. (1991) for the most vital edge problem. The first algorithm takes advantage of the construction of spanning forests embedded in Kruskal's algorithm to compute the replacement edges. The complexity of the latter algorithm is of $O(|\mathcal{E}|\log|\mathcal{E}|)$. Similarly, a second algorithm of complexity $O(|\mathcal{E}|^2)$ but based on Prim's algorithm is as well presented. The work of Iwano & Katoh (1993) introduces two more algorithms that improve the previous complexities. One of them calculates the replacement edges in $O(|\mathcal{E}|\alpha(|\mathcal{E}|, |\mathcal{V}|))$ where $\alpha(|\mathcal{E}|, |\mathcal{V}|)$ represents a functional inverse of Ackermann's function (Calude et al. (1979)). The second time-amortized algorithm of complexity $O(|\mathcal{E}| + |\mathcal{V}|\log|\mathcal{V}|)$ consists of reducing the set of edges where the replacement edges are searched.

An important property of the $\bar{B}$-most vital edges for the MSTI problem that prunes edges of $\mathcal{G}$ is first stated in Liang & Shen (1997). Let $T_0$ be the edge set of the MST of $\mathcal{G}$ and $T_i$ the MST of $\mathcal{G}_i = \mathcal{G} \setminus \cup_{j=0}^{i-1} T_j$. Let $\mathcal{G}_{\bar{B}} = \cup_{i=0}^{\bar{B}} T_i$, the union of the spanning trees $T_i$, $i = 0, ..., \bar{B}$. The reduced graph $G_{\bar{B}}$ is named the sparse weighted $\bar{B}$-edge connected certificate of $\mathcal{G}$. A property of this certificate reads as follows:

**Lemma 2.1.** (Liang & Shen (1997)) For any edge set $S$, $S \subseteq \mathcal{E}$ and $|S| < \bar{B}$, the edges of MST of $\mathcal{G}(\mathcal{V}, \mathcal{E} \setminus S)$ belong to $\mathcal{G}_{\bar{B}}$.

The MSTI problem is then equivalently defined on $\mathcal{G}_{\bar{B}}$ instead of $\mathcal{G}$. Liang & Shen (1997) also introduce a sequential algorithm that runs in $O(|\mathcal{V}|^{\bar{B}+1})$. The algorithm consists of interdicting a subset of edges of $T_0$ and then removing this edge set of $\mathcal{G}$ and recalculating the MST on the new graph, then the algorithm interdicts another subset of edges of the new tree and starts over. Once the $\bar{B}$ edges are interdicted, the algorithm verifies if the interdiction plan and the corresponding tree provide a better increment on the weight of the tree. The latter steps are done on all possible subsets of edges of $T_0$.
In Shen (1999), the author proposes two-random algorithms. The first one has a time complexity of $O(|\mathcal{E}||\mathcal{V}|)$ with $\exp(-\frac{\sqrt{2B}}{B-2})$ of probability of success. The second one is in fact an approximation algorithm that runs in $O(|\mathcal{E}||\mathcal{V}|+B^2|\mathcal{V}|\log|\mathcal{V}|)$ time complexity with $\exp(-\frac{\sqrt{2B}}{B-2})$ probability of success; it provides solutions within a factor of 2 with respect to the optimal solution. The randomness of the algorithms comes from the fact that the replacement edges for the edges in $T_0$ are chosen randomly and uniformly from $\mathcal{G} \setminus T_0$.

The work of Frederickson & Solis-Oba (1999) introduces a greedy algorithm of $O(|\mathcal{E}|^2|\mathcal{V}|^3 \log(|\mathcal{V}|^2/|\mathcal{E}|))$ time complexity for the continuous version. The interdictor consumes resources per unit of weight augmentation of each edge. The coverage of an edge set $S$ is defined as the minimum amount of edges that any MST has to share with the edge set $S$. The greedy algorithm begins by choosing an edge set $S$, then the weights of the edges of $S$ are increased so that its coverage decreases. Once this happens, a new edge set $S$ is chosen, and the process is repeated until the budget is consumed. Baïou & Barahona (2008) extends this version by using piece-wise linear functions for weight augmentations. The authors adapt the algorithm of Frederickson & Solis-Oba (1999) and also present a combinatorial mathematical formulation for this extension.

A Branch-and-Bound-like enumerative algorithm for the $\bar{B}$-most vital edges is introduced in Bazgan et al. (2012). The authors take advantage of the particular structure provided by Lemma 2.1 to develop a Branch-and-Bound scheme that only enumerates the relevant interdiction plans and MSTs associated to them. The algorithm is improved by defining upper and lower bounds for each node of the Branch-and-Bound search tree, so that other nodes can be fathomed. In addition, mathematical formulations for the $\bar{B}$-most vital edges are proposed. However, they proved to be inefficient when compared to their enumerative algorithm.

### 2.2.4 Variants and Extensions

In Section 2.1, the most pertinent literature of the MFI, SPI and MSTI problems is presented. Two types of interdiction and two definitions of the interdictor's budget constraint are identified as a key aspect when it comes to proposing a resolution method. However, the problem is essentially the same, i.e. the interdiction of links as to worsen the network operator's objective. In the current
section, we present variants and extensions of the three considered interdiction problems and point out the main differences with respect to the classical network interdiction problems.

Wood (1993) and Israeli & Wood (2002) present a straightforward extension to deal with undirected networks in the MFI and SPI problems, respectively. The authors reduce the problems to work with a directed network by defining the problems on the sets $A' = \{(i, j) | \{i, j\} \in \mathcal{E}\}$ and $A'' = \{(j, i) | (i, j) \in A'\}$. Furthermore, the research in Wood (1993) and Israeli & Wood (2002) also extend the MFI and SPI problems to consider multiple interdiciton resources. Multiple resource extension is defined in two different ways. We can consider that a link can be interdicted by any one of the resources available to the interdictor. Let $\mathcal{R}$ be the number of different resources and $x_{ijr}$ a decision variable that is equal to one if arc $(i, j)$ is interdicted using resource $r$ and zero, otherwise. The feasible set of the interdictor then extends to $\mathcal{X} := \{\mathbf{x} \in \{0, 1\}^{|A| \times |\mathcal{R}|} | \sum_{(i,j) \in A} b_{ijr} x_{ijr} \le B_r\}$. We may consider as well that an edge needs a number of different resources in order to be interdicted. In that case, we define $\mathcal{X} := \{\mathbf{x} \in \{0, 1\}^{|\mathcal{E}|} | \sum_{e \in \mathcal{E}} b_{er} x_e \le B_r, \forall r \in \mathcal{R}\}$.

The removal of a node together with all its incident links is named node interdiction. The MFI and SPI problems subject to node interdiction are considered in Corley & Chang (1974) and Corley & Sha (1982), respectively. Both articles use the same approach. It is proven that node interdiction can be solved as a $\bar{B}$-most vital links problem in an augmented network. The construction of the augmented graph consists in replacing each node $i \in \mathcal{N}$, except for the source and sink nodes, by two new nodes $i'$ and $i''$ along with a dummy arc $(i'', i')$. An arc $(i', j'')$ is defined with capacity or length $c_{i'j''} = c_{ij}$ for each arc in $(i, j) \in A$. For the dummy arcs, $c_{i''i'} = 0$ in the SPI problem or $c_{i''i'} = \min\{\sum_{(i,j) \in \delta^+(i)} c_{ij}, \sum_{(i,j) \in \delta^-(i)} c_{i,j}\}$ for the MFI problem. Node interdiction is then reduced to find the dummy arcs whose removal maximizes/minimizes the defender's objective. A second type of node interdiction, named node-wise limited interdiction, is defined in Khachiyan et al. (2006) and Khachiyan et al. (2008). In this variant, a fixed number of $k$ outgoing arcs are to be removed for each node in the network. Node removal in the MSTI problem is not considered since the removal of a node disconnects the graph which disables the defender of finding a MST.
A multi-objective problem consists in optimizing several objective functions simultaneously. The authors in Royset & Wood (2007) and Rocco S. et al. (2010) treat the bi-objective variants of the MFI and SPI problems, i.e. the minimization of the interdiction costs and the maximization of the maximum flow or the minimization of the shortest path are optimized at the same time. The research in Rocco S. & Ramirez-Marquez (2010) considers the same problem. In addition, the authors of the article introduce a new follower behavior in which the follower wishes to restore the flow lost after interdiction over time, then a tri-objective MFI problem is defined where the third objective maximizes flow restoration.

The fortification of network links drawn attention from the scholars in the last decade (Brown et al. (2006), Sadeghi et al. (2017), Wu & Conejo (2017), Wu et al. (2021)). The network user, limited by a budget, selects a subset of edges to reinforce, i.e. edges that are impossible to destroy by the interdictor. This variant makes it possible to protect some of the most important links for the follower.

Stochastic optimization is the domain of optimization research where randomness is present in functions or variables. Cormican et al. (1998) and Janjarassuk & Linderoth (2008) consider that the leader's decision to interdict a given arc may result in failure. For each link in the network, there is an independent random variable that is equal to one with given probability, i.e. the arc is destroyed, and equal to zero with the complement, i.e. the arc remains intact. The latter is called uncertain interdiction and is one of several stochastic variants of interdiction problems. Asymmetric information (Sullivan et al. (2014)), uncertainty of arc capacities (Cormican et al. (1998)), stochastic networks (Hemmecke et al. (2003), Held et al. (2005a)) and uncertainty of source/destinations nodes (Pan (2005), Morton (2010)) are some more examples of such variants.

### 2.2.5 Applications

The main application of IGs is to identify critical infrastructure in a system that would cause considerable losses if destroyed. Vulnerability analyses of electrical grids is carried out in Salmeron et al. (2009), Delgadillo et al. (2010) and Yuan et al. (2014). The research of Wood (1993), Jabarzare et al. (2019) and Malaviya et al. (2012) plays a role in the combat against drug trafficking. Protection of crucial sites or infrastructure against terrorist attacks or natural disasters are the
research objective of Salmeron et al. (2004), Powell (2007) and Zhuang & Bier (2007).

The radio communication interdiction problem is addressed in Tanergüçlü et al. (2019) where, in a war-like context, the objective is to place transmitters on the battlefield to secure communication and thus mitigate the damage caused by radio jamming attacks committed by enemy forces.

The vulnerability of cyber-physical networks or systems is the scope of Baycik et al. (2018) and Etesami & Başar (2019). Internet and smart grids became an intrinsic part of communication networks. Therefore, the authors model this type of systems in order to protect them against disruption such as hackers, terrorism or information leakage.

The research in Konrad et al. (2017) analyze solutions to tackle human trafficking from the perspective of the discipline of operation research. The contribution of their work is the analysis of the issue of human trafficking and the different techniques, such as network interdiction, that can be employed.

To end this section, we present in Table 2.1 a summary of the most pertinent articles. Additionally, the literature is classified by the main assumptions and similarities of interdiction problems.

This thesis focuses on the MSTI problem. The works on the interdiction version of the MST are fairly scarce compared to those of SPI and MFI problems. Furthermore, most of them focus in specific cases such as the $\bar{B}$-most vital edges. The work presented in this manuscript is located among the literature in Table 2.1 as follows. The mathematical formulations and algorithms presented in the following sections are all capable of solving instances with any type of edge interdiction and with any budget constraint. The majority of studies have neglected both partial interdiction and knapsack budget constraint assumptions for the MSTI problem. Therefore, up to some extent, our resolution methods are able to solve the generalization of the MSTI problem.
<table><caption>Table 2.1: Main attributes of Interdiction Problems</caption><thead><tr><th rowspan="2">Problem</th><th rowspan="2">Reference</th><th colspan="3">Type of Interdiction</th><th colspan="2">Type of Network</th><th colspan="2">Approach followed</th><th colspan="2">Budget constraint</th><th colspan="4">Underlying Formulation</th></tr><tr><th>ER</th><th>EA</th><th>NR</th><th>Di</th><th>U</th><th>D</th><th>S</th><th>C</th><th>K</th><th>LP</th><th>MIP</th><th>BP</th><th>MO</th><th>N/A</th></tr></thead><tbody><tr><td rowspan="8">Shortest Path</td><td>Wollmer (1964)</td><td>★</td><td></td><td></td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td></td><td>★</td></tr><tr><td>Corley & Chang (1974)</td><td></td><td></td><td>★</td><td></td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td>★</td></tr><tr><td>Wood (1993)</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Cormican et al. (1998)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td><td></td></tr><tr><td>Burch et al. (2003)</td><td>★</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td></td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Brown et al. (2005)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Lim & Smith (2007)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Bertsimas et al. (2016)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td rowspan="10">Maximum Flow</td><td>Fulkerson & Harding (1977)</td><td></td><td>★</td><td></td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Ball et al. (1989)</td><td></td><td>★</td><td></td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td><td></td><td></td><td>★</td></tr><tr><td>Israeli & Wood (2002)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td>Hemmecke et al. (2003)</td><td>★</td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td>Bayrak & Bailey (2008)</td><td>★</td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td>★</td><td></td></tr><tr><td>Khachiyan et al. (2008)</td><td></td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td>Rocco S. & Ramirez-Marquez (2010)</td><td>★</td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td>Sefair & Smith (2016)</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td></td><td>★</td></tr><tr><td>Sadeghi et al. (2017)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td>Pay et al. (2019)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td rowspan="5">Minimum Spanning Tree</td><td>Hsu et al. (1991)</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td></td><td>★</td></tr><tr><td>Lin & Chern (1993)</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td></td><td>★</td></tr><tr><td>Liang & Shen (1997)</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Frederickson & Solis-Oba (1999)</td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Bazgan et al. (2012)</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td rowspan="8">Others</td><td>Wei et al. (2021)</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td></td><td>★</td><td></td><td></td><td></td></tr><tr><td>Pan et al. (2003)</td><td></td><td>★</td><td>★</td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Church et al. (2004)</td><td></td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Held et al. (2005b)</td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Morton et al. (2007)</td><td></td><td>★</td><td></td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Scaparra & Church (2008)</td><td></td><td></td><td>★</td><td>★</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Dinitz & Gupta (2013)</td><td>★</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Yates & Sanjeevi (2013)</td><td></td><td>★</td><td></td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr><tr><td>Furini et al. (2019)</td><td></td><td></td><td>★</td><td>★</td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td>★</td><td>★</td><td></td><td></td></tr></tbody></table>

ER: Edge Removal

EA: Edge Augmentation

NR: Node Removal

Di: Directed

U: Undirected

D: Deterministic

S: Stochastic

C: Cardinality

BP: Bilevel Programming

LP: Linear Problem

K: Knapsack

MO: Multiobjective

MIP: Mixed Integer Problem
# Chapter 3

## Formulations for the MSTI Problem

For the MSTI problem, the bulk of research presented in Chapter 2 have disregarded both the partial interdiction and knapsack budget constraint assumptions. This chapter presents different mathematical formulations of the MSTI problem that generalizes it by being able to consider both types of edge interdiction and both types of budget constraints.

The first formulation presented in this chapter is proposed in Bazgan et al. (2012) and is based on the directed multi-commodity flow model of the MST. The second model uses the linear MST formulation of Martin (1991) to propose a max – min model for the MSTI problem. Constraints that characterize optimal spanning trees given the comparison of every two edges in $\mathcal{E}$ and the reaction with respect to interdiction are defined. We called them optimality constraints and are used to redefine the latter model into a single-level problem.

The max – min formulation is redefined by computing the dual of the inner minimization problem which allows to define a single-level maximization problem. Additionally, a more compact version of the max – min formulation is obtained by modifying and removing unnecessary constraints. This gives place to define a more compact version of the single-level maximization problem.

A model in which only total interdiction is allowed is proposed as well. The latter model is equivalent to the rest of the formulations only under a specific parameter setting. The chapter ends with numerical experiments on instances defined on graphs of different sizes, as well as with all types of interdiction and budget constraints.
## 3.1 Bazgan et al. (2012) Formulation for the MSTI Problem

Two mathematical formulations for the $\bar{B}$-most vital edges interdiction problem are presented in Bazgan et al. (2012). We begin this chapter by reintroducing them. The present formulation is based on the directed multi-commodity flow model (Magnanti & Wolsey (1995)) for the MST. In this MST formulation, node 1 is chosen as root node and a commodity is associated with any other node $l$. One unit of commodity $l$ is sent from the root node to each other node $l$. The flow starts in node 1 and travels to all commodities, i.e. each node $l \neq 1$. Let variables $f_{ij}^l$ represent the flow of commodity $l$ in arc $(i, j)$. The spanning tree is defined by variables $y_{ij}$. Binary variables $x_{ij}$ define the interdiction plan. Lastly, let $n = |\mathcal{V}|$. The mixed-integer formulation that describes the MSTI problem reads as follows:

$$[\text{MSTI}_{\text{Ba}}] \max_{\mathbf{x}} \min_{\mathbf{f},\mathbf{y}} \sum_{\{i,j\} \in \mathcal{E}} (c_{ij} + d_{ij}x_{ij})(y_{ij} + y_{ji}) \quad (3.1a)$$

s.t.

$$\sum_{(j,1) \in \mathcal{A}} f_{j1}^l - \sum_{(1,j) \in \mathcal{A}} f_{1j}^l = -1 \quad : \{\alpha_1^l\} \quad \forall l \in \mathcal{V} \setminus \{1\} \quad (3.1b)$$

$$\sum_{(j,i) \in \mathcal{A}} f_{ji}^l - \sum_{(i,j) \in \mathcal{A}} f_{ij}^l = 0 \quad : \{\alpha_i^l\} \quad \forall i, l \in \mathcal{V} \setminus \{1\}, i \neq l \quad (3.1c)$$

$$\sum_{(j,l) \in \mathcal{A}} f_{jl}^l - \sum_{(l,j) \in \mathcal{A}} f_{lj}^l = 1 \quad : \{\alpha_l^l\} \quad \forall l \in \mathcal{V} \setminus \{1\} \quad (3.1d)$$

$$f_{ij}^l \le y_{ij} \quad : \{\sigma_{ij}^l\} \quad \forall (i,j) \in \mathcal{A}, \forall l \in \mathcal{V} \setminus \{1\} \quad (3.1e)$$

$$\sum_{(i,j) \in \mathcal{A}} y_{ij} = n - 1 \quad : \{\mu\} \quad (3.1f)$$

$$\sum_{\{i,j\} \in \mathcal{E}} b_{ij}x_{ij} \le B \quad (3.1g)$$

$$f_{ij}, y_{ij} \ge 0 \quad \forall (i,j) \in \mathcal{A} \quad (3.1h)$$

$$x_{ij} \in \{0, 1\} \quad \forall \{i, j\} \in \mathcal{E} \quad (3.1i)$$

The maximization of the total cost of the MST by augmenting the weight of the arcs is represented by (3.1a). Constraints (3.1b)-(3.1d) define flow balance for
each node. If $y_{ij} = 0$, constraint (3.1e) forces the flow on the corresponding arc to be zero. Constraint (3.1f) imposes that the MST is composed by exactly $n-1$ arcs. Therefore, solutions given by (3.1b)-(3.1f) represent a spanning tree. The interdiction budget constraint is expressed by (3.1g) which is originally stated in Bazgan et al. (2012) as a cardinality constraint. In this manuscript, it is replaced by a knapsack constraint to generalize the formulation. Positive and integrality requirements are expressed in (3.1h) and (3.1i). [MSTI<sub>Ba</sub>] is a max-min problem with a quadratic objective function.

We refer to the inner problem or inner part of a max-min formulation as the remainder of the model when the values of the variables with respect to the maximization problem are fixed. The inner problem of [MSTI<sub>Ba</sub>] when fixing variables $x_{ij}$ is defined by (3.1a)-(3.1f) and (3.1h).

To establish a single-level model, the inner part of [MSTI<sub>Ba</sub>] is substituted with its dual formulation. The dual variables are shown next to their respective constraints in model (3.1). The dual formulation is the following:

$$[\text{MSTI}_{\text{DBa}}] \quad \max_{x, \sigma, \alpha, \mu} \sum_{\substack{l \in \mathcal{V} \\ l \neq 1}} (\alpha_l^l - \alpha_1^l) + (n-1)\mu \quad (3.2a)$$

s.t.

$$\sigma_{ij}^l \ge \alpha_j^l - \alpha_i^l \quad \forall (i, j) \in \mathcal{A}, \forall l \in \mathcal{V} \setminus \{1\} \quad (3.2b)$$

$$\sum_{l \neq 1} \sigma_{ij}^l + \mu \le c_{ij} + d_{ij}x_{ij} \quad \forall \{i, j\} \in \mathcal{E} \quad (3.2c)$$

$$\sum_{l \neq 1} \sigma_{ji}^l + \mu \le c_{ij} + d_{ij}x_{ij} \quad \forall \{i, j\} \in \mathcal{E} \quad (3.2d)$$

$$\sum_{\{i,j\} \in \mathcal{E}} b_{ij}x_{ij} \le B \quad (3.2e)$$

$$x_{ij} \in \{0, 1\} \quad \forall \{i, j\} \in \mathcal{E} \quad (3.2f)$$

$$\sigma_{ij}^l \ge 0 \quad \forall (i, j) \in \mathcal{A}, \forall l \in \mathcal{V} \setminus \{1\} \quad (3.2g)$$

$$\alpha_i^l \ge 0 \quad \forall i \in \mathcal{V}, \forall l \in \mathcal{V} \setminus \{1\} \quad (3.2h)$$

$$\mu = \text{unrestricted} \quad (3.2i)$$

The quadratic terms in [MSTI<sub>Ba</sub>] objective function (3.1a) are no longer present in formulation (3.2). Thus, we obtain a mixed-integer linear formula-
tion.

3.2 MSTI Formulation Based on Martin (1991)
MST Formulation

In Martin (1991), the author proposes a formulation for the MST that meets
the condition of Total Dual Integrality. This condition proves the integrality of
the polyhedron defined by the constraints of the model. An integral polyhedron
is a polyhedron whose vertices are all integer (Cook et al. (1997)). Thus the
model provides an integer solution even when the integrality requirement on the
variables respect to the edge selection are removed. To present the model, first,
let us define $\mathcal{A}_m = \{(m, j) \in \mathcal{A}, \mid j \in \mathcal{V}\}$ for all $m \in \mathcal{V}$ as the set of all arcs with
node $m$ as origin. Let $y_e$ be a variable that is equal to 1 if edge $e$ is part of the
MST, and 0 otherwise. Each edge $e$ is disaggregated into $k$-arcs, i.e. $(k, i, j)$ and
$(k, j, i)$ for all $k \in \mathcal{V}$ and for all $e = \{i, j\} \in \mathcal{E}$. Let $z_{kij}$ be 1 if arc $(i, j)$ is chosen
as part of the directed MST, and 0 otherwise. Let $\mathbf{y}$-tree and $\mathbf{z}_k$-tree denote the
trees defined by $y_e$ and $z_{kij}$ variables, respectively. The MST formulation reads
as follows:

$$
\begin{equation}
\begin{array}{@{}l@{}}
\text{[MST]} \quad \min_{\mathbf{y},\mathbf{z}} \sum_{e \in \mathcal{E}} c_e y_e \\
\text{s.t.} \\
\quad \sum_{e \in \mathcal{E}} y_e = n-1
\end{array}
\tag{3.3a}
\end{equation}
$$

$$
\begin{align}
& \sum_{e \in \mathcal{E}} y_e = n-1 \tag{3.3b} \\
& z_{kij} + z_{kji} = y_e \tag{3.3c}
\end{align}
$$

$$
z_{kij} + z_{kji} = y_e \qquad \forall k \in \mathcal{V}, e = \{i, j\} \in \mathcal{E} \tag{3.3c}
$$

$$
\sum_{(m,j) \in A_m} z_{kmj} \le 1 \qquad \forall k, m \in \mathcal{V}, k \ne m \qquad (3.3\text{d})
$$

$$
\sum_{(k,j) \in A_k} z_{kkj} \le 0 \qquad \forall k \in \mathcal{V} \tag{3.3e}
$$

$$
y_e \ge 0 \qquad \forall e \in \mathcal{E} \tag{3.3f}
$$

$$
z_{kij} \ge 0 \qquad \forall k, i, j \in \mathcal{V}, i \ne j \tag{3.3g}
$$

Objective function (3.3a) maximizes the weight of the **y**-tree. Exactly *n* − 1 edges are selected to define a MST thanks to (3.3b). The variables *z*<sub>*kij*</sub> represent
$k$ directed trees induced by variables $y_e$, whose arcs define paths from any node towards node $k$. Constraints (3.3c)-(3.3e) define cycle elimination constraints for the $z_k$-trees. In turn, they eliminate the cycles of the $y$-tree. If there were an undirected cycle in the $y$-tree that contains a given node $k$, each $z_k$-tree will have, by (3.3c), an analogous cycle that contains node $k$ as well. A directed cycle containing $k$, i.e. a cycle that starts and ends in node $k$, is impossible by (3.3d) since it does not allow the selection of an arc directed out of $k$ in a $z_k$-tree. Non-directed cycles are those that for a node $i \in V$, $i \neq k$, there exists two arcs with origin in $i$. This is also forbidden by (3.3e) since only one directed out arc is allowed for each node different of $k$. Thus, formulation (3.3) defines a MST of $\mathcal{G}$. The max-min formulation that defines the interdiction of the MST, indicated with [MSTI] is the following:

$$ \text{[MSTI]} \quad \max_{\mathbf{x}} \min_{\mathbf{y},\mathbf{z}} \sum_{e \in \mathcal{E}} (c_e + d_e x_e) y_e \qquad (3.4a) $$

s.t.

$$ \sum_{e \in \mathcal{E}} y_e = n - 1 \qquad : \{\beta\} \qquad (3.4b) $$

$$ z_{kij} + z_{kji} = y_e \qquad : \{\sigma_{ke}\} \quad \forall k \in \mathcal{V}, e = \{i, j\} \in \mathcal{E} \qquad (3.4c) $$

$$ \sum_{(m,j) \in A_m} z_{kmj} \leq 1 \qquad : \{\tau_{km}\} \quad \forall k, m \in \mathcal{V}, k \neq m \qquad (3.4d) $$

$$ \sum_{(k,j) \in A_k} z_{kkj} \leq 0 \qquad : \{\theta_k\} \quad \forall k \in \mathcal{V} \qquad (3.4e) $$

$$ \sum_{e \in \mathcal{E}} b_e x_e \leq B \qquad (3.4f) $$

$$ y_e \geq 0 \qquad \forall e \in \mathcal{E} \qquad (3.4g) $$

$$ x_e \in \{0, 1\} \qquad \forall e \in \mathcal{E} \qquad (3.4h) $$

$$ z_{kij} \geq 0 \qquad \forall k, i, j \in \mathcal{V}, i \neq j \qquad (3.4i) $$

The objective function (3.4a) maximizes the weight of the edges chosen to be part of the MST. Constraints (3.4c)-(3.4e) are as in [MST]. The interdiction budget constraint is imposed by (3.4f). Constraints (3.4g)-(3.4i) define the variables.

Note that formulation [MSTI] is also a max-min quadratic model. Two different approaches are followed to propose a single-level formulation. The first
one is the development of optimality constraints for the computation of the MST.
This allows us to remove the minimization problem and thus to obtain a single-
level problem. Subsequently, a classic linearization technique on the term $x_e y_e$ is
used. This is presented in Section 3.3. The second approach is the one followed
in Section 3.1, the inner part of the formulation is a linear program which can
be replaced by its dual. This technique is applied to an equivalent formulation
of [MSTI] that leads to an even more compact formulation. This is presented in
Section 3.4.

3.3 Reformulation using Optimality Constraints

This section starts by stating a well-known optimal condition for the MST (Schri-
jver (2003)) which is later used to develop optimality constraints for formulation
[MST].

**Theorem 3.1.** A tree $T$ of $\mathcal{G}$ is a MST if and only if $c_f \ge c_e, \forall e \in T, f \in \mathcal{E} \setminus T$ such that $T \setminus \{e\} \cup \{f\}$ defines a spanning tree.

Let $T^*$ be the MST of $\mathcal{G}$ and let $e = \{i, j\}, f = \{u, v\} \in \mathcal{E}$ be two edges
that satisfy the conditions of Theorem 3.1. Due to constraints (3.3c), we have
$z_{uij} + z_{uji} = 1$ and $z_{vij} + z_{vji} = 1$. Let us suppose that $z_{vij} = 1$. This means that
in the $\mathbf{z}_v$-tree corresponding to $T^*$ there exist a unique directed path from $i$ to
$v$ that uses arc $(i, j)$. Therefore, $z_{uij} = 0$ since there cannot be a path from $i$ to
$u$ that uses arc $(i, j)$ because $\{u, v\} \notin T^*$. Analogously, $z_{uji} = 0$ if we assume
$z_{vji} = 1$. Thus, $z_{vij}$ and $z_{uij}$ (or $z_{vji}$ and $z_{uji}$) cannot be simultaneously 1. It
follows that $z_{uij} + z_{vji} = 2$ (or $z_{uji} + z_{vij} = 2$). Theorem 3.1 can be equivalently
stated as follows.

**Theorem 3.2.** ($\mathbf{y}^*, \mathbf{z}^*$) is an optimal solution of [MST] if and only if $z_{uij}^* + z_{vji}^* = 2$ or $z_{uji}^* + z_{vij}^* = 2$ for all $e = \{i, j\}, f = \{u, v\}$ such that $c_f \ge c_e$.

In order to integrate the optimality constraints in the formulations for the
MSTI problem, Theorem 3.2 can be equivalently stated as:

**Theorem 3.3.** ($\mathbf{y}^*, \mathbf{z}^*$) is an optimal solution of [MST] if and only if $z_{uij}^* + z_{vji}^* \le 1$ and $z_{uji}^* + z_{vij}^* \le 1$ for all $e = \{i, j\}, f = \{u, v\}$ such that $c_f < c_e$.
Conditions of Theorem 3.3 can be strengthened to obtain the following theorem.

**Theorem 3.4.** ($\mathbf{y}^*, \mathbf{z}^*$) is an optimal solution of [MST] if and only if $z_{uji}^* + z_{vji}^* \le y_e^*$ and $z_{uji}^* + z_{vji}^* \le y_e^*$ for all $e = \{i, j\}, f = \{u, v\}$ such that $c_f < c_e$.

*Proof. Case 1.* When the edge $e$ is selected the corresponding variable $y_e^* = 1$ and the conditions are as in Theorem 3.3.

**Case 2.** When the edge $e$ is not selected the corresponding variable $y_e^* = 0$ and due to constraints (3.4c) $z_{kij}^* = z_{kji}^* = 0$, for all $k \in \mathcal{V}$. $\square$

Note that, depending on the interdiction plan, the relation between the cost of the edges may change. As an example, it may indeed happen that $c_e < c_f$, but $c_f < c_e + d_e$. As a consequence, the optimality conditions based on Theorem 3.4 are further developed. To generate an appropriate condition for the different outcomes regarding the weights of the edges, several sets on the space $\mathcal{E} \times \mathcal{E}$ are introduced and listed below:

$$ \mathcal{E}_1 = \{(e, f) \mid c_f + d_f < c_e \ \forall e, f \in \mathcal{E}\} $$

$$ \mathcal{E}_2 = \{(e, f) \mid c_f < c_e, c_f + d_f < c_e + d_e, c_e \le c_f + d_f \ \forall e, f \in \mathcal{E}\} $$

$$ \mathcal{E}_3 = \{(e, f) \mid c_f < c_e, c_e + d_e \le c_f + d_f \ \forall e, f \in \mathcal{E}\} $$

$$ \mathcal{E}_4 = \{(e, f) \mid c_e \le c_f, c_f + d_f < c_e + d_e \ \forall e, f \in \mathcal{E}\} $$

$$ \mathcal{E}_5 = \{(e, f) \mid c_e \le c_f, c_e + d_e \le c_f + d_f, c_f < c_e + d_e \ \forall e, f \in \mathcal{E}\} $$

The sets $\mathcal{E}_i \subset \mathcal{E} \times \mathcal{E}$ represent all the different relations between edges given their weight and their augmented weight. For each set we can now derive optimality constraints.

**Set $\mathcal{E}_1$:** Note that on $\mathcal{E}_1$, regardless the interdiction plan, the weight of $e = \{i, j\}$ is always grater than the weight of $f = \{u, v\}$. Therefore, we can directly apply the conditions of Theorem 3.4 and define $z_{uji} + z_{vij} \le y_e$ as optimality constraint for any pair $(e, f)$ of $\mathcal{E}_1$ with $e = \{i, j\}$ and $f = \{u, v\}$.

**Set $\mathcal{E}_3$:** In this case the optimality constraints are modified as $z_{uji} + z_{vij} \le y_e + x_f$. This imposes the optimality condition only when edge $f$ is not interdicted. Indeed, when $f$ is interdicted, the weight of edge $e$ is lower than the weight of edge $f$ and the corresponding constraint is deactivated by adding variable $x_f$.
### 3. FORMULATIONS FOR THE MSTI PROBLEM

**Set $\mathcal{E}_4$**: The conditions of Theorem 3.4 are met when edge $e$ is interdicted. Thus, $z_{uji} + z_{vij} \le y_e - x_e + 1$ is defined for any element of this set. Note that the latter expression is relaxed if edge $e$ is not interdicted.

**Set $\mathcal{E}_5$**: The optimality conditions for this set are considered only in the specific case when edge $e$ is interdicted and edge $f$ is not. Once more, the optimality constraints are modified to $z_{uji} + z_{vij} \le y_e - x_e + x_f + 1$. In fact, the right hand side of this expression becomes $y_e + 1$ in any other case.

**Set $\mathcal{E}_2$**: Since the weights of the edges of any element of $\mathcal{E}_2$ can meet three different cases, the constraints defined for $\mathcal{E}_3$ and $\mathcal{E}_4$ are used. This way, one of those two conditions imposes Theorem 3.4 while the other becomes relaxed.

For each pair of edges $(e, f)$, $e, f \in \mathcal{E}$, it is considered that $e = \{i, j\}$ and $f = \{u, v\}$ unless stated otherwise. Introducing the optimality constraints allows to remove the minimization over $\mathbf{y}$ and $\mathbf{z}$ in formulation [MSTI] and to obtain the following single-level non-linear formulation for the MSTI problem.

$$ [\text{MSTI_Q}] \quad \max_{\mathbf{x},\mathbf{y},\mathbf{z}} \sum_{e \in \mathcal{E}} (c_e + d_e x_e) y_e \qquad (3.5a) $$

s.t.

$$ \sum_{e \in \mathcal{E}} y_e = n - 1 \qquad (3.5b) $$

$$ z_{kij} + z_{kji} = y_e \qquad \forall k \in \mathcal{V}, e = \{i, j\} \in \mathcal{E} \qquad (3.5c) $$

$$ \sum_{(m,j) \in A_m} z_{kmj} \le 1 \qquad \forall k, m \in \mathcal{V}, k \ne m \qquad (3.5d) $$

$$ \sum_{(k,j) \in A_k} z_{kkj} \le 0 \qquad \forall k \in \mathcal{V} \qquad (3.5e) $$

$$ z_{uji} + z_{vij} \le y_e \qquad \forall (e, f) \in \mathcal{E}_1 \qquad (3.5f) $$

$$ z_{uji} + z_{vij} \le y_e + x_f \qquad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_3 \qquad (3.5g) $$

$$ z_{uji} + z_{vij} \le y_e - x_e + 1 \qquad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_4 \qquad (3.5h) $$

$$ z_{uji} + z_{vij} \le y_e - x_e + x_f + 1 \qquad \forall (e, f) \in \mathcal{E}_5 \qquad (3.5i) $$

$$ \sum_{e \in \mathcal{E}} b_e x_e \le B \qquad (3.5j) $$

$$ x_e \in \{0, 1\} \qquad \forall e \in \mathcal{E} \qquad (3.5k) $$

$$ y_e \ge 0 \qquad \forall e \in \mathcal{E} \qquad (3.5l) $$
$$z_{kij} \geq 0 \qquad \forall k, i, j \in \mathcal{V}, i \neq j \qquad (3.5m)$$

Constraints (3.5f)-(3.5i) are the optimality conditions discussed above. They ensure that the spanning tree determined by (3.5c)-(3.5e) is of minimum cost, thus a MST. The objective function (3.5a) is non-linear due to the product of the variables $y_e$ and $x_e$. Therefore, a classic linearization technique and boundary inequalities are used and presented next.

First, we redefine $y_e$ as a binary variable. Note that $y_e$ variables are linear in [MST] due to Total Dual Integral properties. Let $t_e = x_e y_e$ for all $e \in \mathcal{E}$, then $t_e$ is a binary variable that takes the value of 1 only if both $x_e$ and $y_e$ are equal to 1 and 0, otherwise. The linearization of formulation [MSTI_Q] reads as follows:

$$[\text{MSTI}_{\text{Opt}}] \quad \max_{t,x,y,z} \sum_{e \in \mathcal{E}} (c_e y_e + d_e t_e) \qquad (3.6a)$$

s.t.

$$\sum_{e \in \mathcal{E}} y_e = n - 1 \qquad (3.6b)$$

$$z_{kij} + z_{kji} = y_e \qquad \forall k \in \mathcal{V}, e = \{i, j\} \in \mathcal{E} \qquad (3.6c)$$

$$\sum_{(m,j) \in \mathcal{A}_m} z_{kmj} \leq 1 \qquad \forall k, m \in \mathcal{V}, k \neq m \qquad (3.6d)$$

$$\sum_{(k,j) \in \mathcal{A}_k} z_{kkj} \leq 0 \qquad \forall k \in \mathcal{V} \qquad (3.6e)$$

$$z_{uji} + z_{vij} \leq y_e \qquad \forall (e, f) \in \mathcal{E}_1 \qquad (3.6f)$$

$$z_{uji} + z_{vij} \leq y_e + x_f \qquad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_3 \qquad (3.6g)$$

$$z_{uji} + z_{vij} \leq y_e - x_e + 1 \qquad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_4 \qquad (3.6h)$$

$$z_{uji} + z_{vij} \leq y_e - x_e + x_f + 1 \qquad \forall (e, f) \in \mathcal{E}_5 \qquad (3.6i)$$

$$t_e \leq x_e \qquad \forall e \in \mathcal{E} \qquad (3.6j)$$

$$t_e \leq y_e \qquad \forall e \in \mathcal{E} \qquad (3.6k)$$

$$\sum_{e \in \mathcal{E}} b_e x_e \leq B \qquad (3.6l)$$

$$t_e, x_e, y_e \in \{0, 1\} \qquad \forall e \in \mathcal{E} \qquad (3.6m)$$

$$z_{kij} \geq 0 \qquad \forall k, i, j \in \mathcal{V}, i \neq j \qquad (3.6n)$$
### 3. FORMULATIONS FOR THE MSTI PROBLEM

When variable $x_e$ or $y_e$ is equal to zero then $t_e$ is equally zero due to the additional constraints (3.6j) and (3.6k). The latter allows to write the product $d_e t_e$ as in the objective function (3.6a). Finally, we obtain [MSTI<sub>Opt</sub>] which is a single-level mixed-integer linear problem.

## 3.4 Dual Formulations

A second procedure to determine single-level linear formulations for the MSTI problem consists in replacing the inner part of [MSTI] by its dual formulation. The dual variables for the inner problem constraints are given in model (3.4). The [MSTI<sub>Dual</sub>] formulation is presented below.

$$ [\text{MSTI}_{\text{Dual}}] \quad \max_{x, \beta, \sigma, \tau, \theta} \beta(n-1) - \sum_{k \in \mathcal{V}} \sum_{m \in \mathcal{V}, m \neq k} \tau_{km} \quad (3.7a) $$

s.t.

$$ \beta + \sum_{k \in \mathcal{V}} \sigma_{ke} \leq c_e + d_e x_e \quad \forall e \in \mathcal{E} \quad (3.7b) $$

$$ \sigma_{ke} + \tau_{km} \geq 0 \quad \forall k, m \in \mathcal{V}, e = \{m, j\} \in \mathcal{E} \quad (3.7c) $$

$$ \sigma_{ke} + \theta_k \geq 0 \quad \forall k \in \mathcal{V}, e = \{k, j\} \in \mathcal{E} \quad (3.7d) $$

$$ \sum_{e \in \mathcal{E}} b_e x_e \leq B \quad (3.7e) $$

$$ \tau_{km}, \theta_k \geq 0 \quad \forall k, m \in \mathcal{V}, m \neq k \quad (3.7f) $$

$$ x_e \in \{0, 1\} \quad \forall e \in \mathcal{E} \quad (3.7g) $$

$$ \beta, \sigma_{ke} = \text{unrestricted} \quad \forall k \in \mathcal{V}, \forall e \in \mathcal{E} \quad (3.7h) $$

It can be observed that constraints (3.4e) force variables $z_{kkj}$ to be zero. This yields to have more variables and constraints for the dual formulation [MSTI<sub>Dual</sub>]. The [MSTI] model can be reformulated so that the constraints (3.4e) are no longer necessary, thus making the dual of the inner problem more compact. As a result, it is possible to have a formulation with one less family of constraints and one less family of variables. Let us introduce $\mathcal{E}^k = \{\{k, i\} \in \mathcal{E} \mid i \in \mathcal{V} \setminus \{k\}\}$ as the set of all edges with $k$ as one of the endpoints. The simplified version of [MSTI] is shown next:
$$ [\text{MSTI}_S] \quad \max_{\mathbf{x} \in \mathcal{X}} \min_{\mathbf{y}, \mathbf{z}} \sum_{e \in \mathcal{E}} (c_e + d_e x_e) y_e \qquad (3.8a) $$

s.t.

$$ \sum_{e \in \mathcal{E}} y_e = n - 1 \qquad (3.8b) $$

$$ z_{kij} + z_{kji} = y_e \qquad \forall k \in \mathcal{V}, e = \{i, j\} \in \mathcal{E} \setminus \mathcal{E}^k \qquad (3.8c) $$

$$ \sum_{(m,j) \in A_m \setminus \{m,k\}} z_{kmj} + y_e \le 1 \qquad \forall k, m \in \mathcal{V}, k \ne m, e = \{m,k\} \qquad (3.8d) $$

$$ y_e \ge 0 \qquad \forall e \in \mathcal{E} \qquad (3.8e) $$

$$ z_{kij} \ge 0 \qquad \forall k, i, j \in \mathcal{V}, i \ne j \qquad (3.8f) $$

where $\mathcal{X} = \{\mathbf{x} \in \{0, 1\}^{|\mathcal{E}|} | \sum_{e \in \mathcal{E}} b_e x_e \le B\}$. In (3.4), given an edge $e = \{k, j\}$, $y_e = z_{kjk}$ due to (3.4c) and (3.4e). The latter constraint is not defined in [MSTI$_S$] by not considering edges that are incident to $k$ in (3.8c). In addition, the variable $z_{kjk}$ that appeared in (3.4d) is substituted by $y_e$, $e = \{k, j\}$, in (3.8d). The procedure performed to obtain [MSTI$_{Dual}$] is now applied to [MSTI$_S$]. A simplified and compact version of [MSTI$_{Dual}$] reads as follows:

$$ [\text{MSTI}_{\text{SDual}}] \quad \max_{\mathbf{x}, \beta, \sigma, \tau} \beta(n-1) - \sum_{k \in \mathcal{V}} \sum_{\substack{m \in \mathcal{V} \\ m \ne k}} \tau_{km} \qquad (3.9a) $$

s.t.

$$ \beta + \sum_{k \in \mathcal{V} \setminus \{m,h\}} \sigma_{ke} - \tau_{hm} - \tau_{mh} \le c_e + d_e x_e \qquad \forall e = \{m,h\} \in \mathcal{E} \qquad (3.9b) $$

$$ \sigma_{ke} + \tau_{km} \ge 0 \qquad \forall k, m \in \mathcal{V}, e = \{m, j\} \in \mathcal{E} \setminus \mathcal{E}^k \qquad (3.9c) $$

$$ \sum_{e \in \mathcal{E}} b_e x_e \le B \qquad (3.9d) $$

$$ \tau_{km} \ge 0 \qquad \forall k, m \in \mathcal{V}, m \ne k \qquad (3.9e) $$

$$ x_e \in \{0, 1\} \qquad \forall e \in \mathcal{E} \qquad (3.9f) $$

$$ \beta, \sigma_{ke} = \text{unrestricted} \qquad \forall k \in \mathcal{V}, \forall e \in \mathcal{E} \qquad (3.9g) $$

Constraints (3.4c) and (3.4d) are modified to avoid using indexes $kkj$. Conse-
## 3. FORMULATIONS FOR THE MSTI PROBLEM

quently, in constraints (3.4e) variables $z_{kkj}$ are not needed anymore. We can see the results of these changes in [MSTI<sub>SDual</sub>]. Constraints (3.9b), the constraints associated with the primal variables $y_e$, consider two variables $\tau_{hm}$ since variables $y_e$ are now considered in (3.8d). Furthermore, two variables $\sigma_{ke}$ where $k$ is one of the endpoints of edge $e$ are not considered because their corresponding constraints in (3.8c) are not defined. [MSTI<sub>SDual</sub>] is a more compact formulation of the MSTI problem since it has one less set of variables and one less family of constraints with respect to [MSTI<sub>Dual</sub>].

## 3.5 Total Interdiction Formulation

This section focuses on the total interdiction case, namely when $d_e = +\infty$ for all $e \in \mathcal{E}$. Intuitively, since total interdiction means removal of the edge, it is natural to claim that an edge may be interdicted or selected, but cannot be both simultaneously. Mathematically this is modeled by the constraints $x_e + y_e \le 1$, for each $e \in \mathcal{E}$. Therefore, two new sets $\mathcal{E}_6 = \{(e, f) \mid c_f < c_e \ \forall e, f \in \mathcal{E}\}$ and $\mathcal{E}_7 = \{(e, f) \mid c_e \le c_f \ \forall e, f \in \mathcal{E}\}$ are defined since the comparison between interdicted edges is no longer considered. The new optimality conditions for these sets look as follows. Let $e = \{i, j\}$ and $f = \{u, v\}$:

**Set $\mathcal{E}_6$:** The optimality condition is necessary only when edge $f$ is not interdicted. Therefore, we define $z_{uji} + z_{vij} \le y_e + x_f$. In any other case, the inequality is relaxed.

**Set $\mathcal{E}_7$:** An optimality condition is imposed for this set only when edge $e$ is interdicted. However, $y_e = 0$ when $x_e = 1$ due to $x_e+y_e \le 1$. Thus, $z_{uji}+z_{vij} \le 0$. If edge $e$ is not interdicted, then the optimality condition should be relaxed. Therefore, there is no need to define an optimality condition for this set.

The formulation for the total interdiction case then reads as:

$$ [\text{MSTI}_{\text{Tot}}] \quad \max_{x,y,z} \sum_{e \in \mathcal{E}} c_e y_e \qquad (3.10a) $$

s.t.

$$ y_e \le 1 - x_e \qquad \forall e \in \mathcal{E} \qquad (3.10b) $$

$$ \sum_{e \in \mathcal{E}} y_e = n - 1 \qquad (3.10c) $$
$$z_{kij} + z_{kji} = y_e \qquad \forall k \in \mathcal{V}, e = \{i, j\} \in \mathcal{E} \qquad (3.10d)$$

$$\sum_{(i,j) \in A_m} z_{kmj} \le 1 \qquad \forall k, m \in \mathcal{V}, k \ne m \qquad (3.10e)$$

$$\sum_{(i,j) \in A_k} z_{kkj} \le 0 \qquad \forall k \in \mathcal{V} \qquad (3.10f)$$

$$z_{uji} + z_{vij} \le y_e + x_f \qquad \forall (e, f) \in \mathcal{E}_6 \qquad (3.10g)$$

$$\sum_{e \in \mathcal{E}} b_e x_e \le B \qquad (3.10h)$$

$$x_e \in \{0, 1\} \qquad \forall e \in \mathcal{E} \qquad (3.10i)$$

$$y_e \ge 0 \qquad \forall e \in \mathcal{E} \qquad (3.10j)$$

$$z_{kij} \ge 0 \qquad \forall k, i, j \in \mathcal{V}, i \ne j \qquad (3.10k)$$

The objective function (3.10a) does not need to maximize over variables $x_e$ since constraints (3.10b) avoid the use of edges that are interdicted. Constraints (3.10g) are the optimality conditions introduced above. The remaining constraints are as in [MSTI<sub>Opt</sub>].

Formulation [MSTI<sub>Tot</sub>] is not equivalent to [MSTI<sub>DBa</sub>], [MSTI<sub>Opt</sub>], [MSTI<sub>Dual</sub>] nor [MSTI<sub>SDual</sub>] for all possible settings of parameters *B* and *d*<sub>e</sub>. To illustrate this point, consider the graph given in Figure 3.1a. Let *B* = 4 and let us assume a cardinality constraint, that is, *b*<sub>e</sub> = 1 for all *e* ∈ *E*. A pair (*c*<sub>e</sub>, *d*<sub>e</sub>) where *d*<sub>e</sub> = Σ<sub>f∈E</sub> *c*<sub>f</sub> is reported on each edge *e* ∈ *E*. Note that *d*<sub>e</sub> is a large enough value for each *e* ∈ *E* to model edge removal. The optimal solution given by either formulation [MSTI<sub>Opt</sub>], [MSTI<sub>DBa</sub>], [MSTI<sub>Dual</sub>] or [MSTI<sub>SDual</sub>] is shown in Figure 3.1b. Dotted edges (either black or blue) represent the interdicted edges while the blue edges represent the MST after interdiction. Figure 3.1c shows the optimal solution of model [MSTI<sub>Tot</sub>]. The solution illustrated in Figure 3.1b disconnects node 2 from the rest of the graph since the value of *B* is greater than the connectivity number equal to 3. Moreover, the MST provided by this same solution makes use of the interdicted edge {2, 3}. Thus, we can conclude that the instance is not well-defined since the budget allows the interdictor to disconnect the graph. On the other hand, the [MSTI<sub>Tot</sub>] solution provides a MST where no interdicted edges are considered. This is since constraints (3.10b) forbid the selection of an interdicted edge, not present in other models, whereas due to constraints (3.10c)-(3.10g) the solution must be a spanning tree. This explains
<figure><img src="image_3.png" /><figcaption>Figure 3.1: Comparison of formulation solutions</figcaption></figure>

the fact that the solution in Figure 3.1c interdicts only three edges when it is
possible to interdict four. Therefore, under these parameter settings [MSTI$_{Tot}$] is
not equivalent to [MSTI$_{DBa}$], [MSTI$_{Opt}$], [MSTI$_{Dual}$] nor [MSTI$_{SDual}$].

The assumption of a knapsack constraint also gives place for the formulations
to not be equivalent. In this case, the connectivity number with respect to the
augmentation costs is calculated by solving max{∑<sub>e∈E</sub> x<sub>e</sub> : ∑<sub>e∈E</sub> b<sub>e</sub>x<sub>e</sub> ≤ B}.
Then, setting a budget greater than or equal to the connectivity number will
cause the behavior described above.

Next, it is demonstrated that the formulations [MSTI<sub>Opt</sub>] and [MSTI<sub>Tot</sub>], and
subsequently the rest of the formulations, are equivalent under the assumption of
total interdiction and a budget *B* less than the connectivity number of *G*.

**Proposition 3.5.** Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be a graph where $\mathcal{V}$ is the node set and $\mathcal{E}$ is the edge set. Let us associate a weight $c_e$, an interdiction augmentation $d_e$ and an interdiction cost $b_e$ with all edges in $\mathcal{E}$. Let $B$ be less than the connectivity number of $\mathcal{G}$ with respect to the augmentation costs and $d_e$ at least $\max_{e \in \mathcal{E}} c_e + 1 - c_e$ for all $e \in \mathcal{E}$. i.e. $d_e$ is large enough to define total interdiction. Then, $[MSTI_{Opt}]$ and $[MSTI_{Tot}]$ provide the same optimal solution.
Proof. Let $(\bar{\mathbf{x}}, \bar{\mathbf{y}}, \bar{\mathbf{z}})$ be the optimal solution of [MSTI$_{Tot}$] under the parameter setting stated in the hypothesis. Note that $\mathcal{E}_1 = \emptyset$, $\mathcal{E}_6 = \mathcal{E}_2 \cup \mathcal{E}_3$ and $\mathcal{E}_7 = \mathcal{E}_4 \cup \mathcal{E}_5$. Constraint (3.10g) is met for all $(e, f) \in \mathcal{E}_6$, then constraint (3.6g) is verified for all $(e, f) \in \mathcal{E}_2$ and in $\mathcal{E}_3$. For any $(e, f) \in \mathcal{E}_6 \cap \mathcal{E}_2$, if $\bar{x}_e = 0$ and $\bar{x}_f = 0$ then $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e$ from (3.10g); it follows that $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e - \bar{x}_e + 1$. If $\bar{x}_e = 0$ and $\bar{x}_f = 1$ then $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e + 1$; it follows that $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e - \bar{x}_e + 1$. If $\bar{x}_e = 0$ and $\bar{x}_f = 0$ or 1 then $\bar{z}_{uji} + \bar{z}_{vij} \le 0$ due to (3.10b); it follows that $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e - \bar{x}_e + 1$. Therefore, (3.6h) is verified for all $(e, f) \in \mathcal{E}_2$.

Note that from (3.10d), $\bar{z}_{uji} \le \bar{y}_e$ and $\bar{z}_{vij} \le \bar{y}_e$. It follows that $\bar{z}_{uji} + \bar{z}_{vij} - \bar{y}_e \le \bar{y}_e$ and from $x_e + y_e \le 1$ it follows that $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e - \bar{x}_e + 1$. Then constraint (3.6h) is verified for all $(e, f) \in \mathcal{E}_4$. For any $(e, f) \in \mathcal{E}_7 \cap \mathcal{E}_5$, we can write $\bar{z}_{uji} + \bar{z}_{vij} \le 2$ when $\bar{x}_e = 0$ since there is no need of an optimality condition in this case. It follows that $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e - \bar{x}_e + \bar{x}_f + 1$. When $\bar{x}_e = 1$, $\bar{z}_{uji} + \bar{z}_{vij} \le 0$ due to (3.10b), it follows that $\bar{z}_{uji} + \bar{z}_{vij} \le \bar{y}_e - \bar{x}_e + \bar{x}_f + 1$. Thus, (3.6i) is verified for all $(e, f) \in \mathcal{E}_5$. Therefore, the optimal solution of [MSTI$_{Tot}$] is feasible in [MSTI$_{Opt}$].

Let $(\hat{\mathbf{x}}, \hat{\mathbf{y}}, \hat{\mathbf{z}})$ be the optimal solution of [MSTI$_{Opt}$] under the parameter setting stated in the hypothesis. Constraint (3.6g) is met for all $(e, f)$ in $\mathcal{E}_2$ and in $\mathcal{E}_3$, then constraint (3.10g) is verified for all $(e, f) \in \mathcal{E}_6$. We proceed to prove that (3.10b) is verified by $(\hat{\mathbf{x}}, \hat{\mathbf{y}}, \hat{\mathbf{z}})$ by absurd. Suppose there is at least one edge $e' \in \mathcal{E}$ such that $\hat{x}_{e'} + \hat{y}_{e'} = 2$. Let $T$ be the edge set associated to the MST defined by $\hat{\mathbf{y}}$. If edge $e'$ is removed from $T$ then two connected components $T_1$ and $T_2$ are obtained. $T_1$ and $T_2$ are sub-trees of $T$. $B$ is small enough to not allow a feasible interdiction plan that defines a cut of $\mathcal{G}$. Therefore, there must exist at least one non-interdicted edge $e'' \neq e'$ such that it connects $T_1$ and $T_2$ and such that $x_{e''} + y_{e''} \le 1$. The interdicted weight of $e'$ is $c_{e'} + d_{e'}$. Since $d_{e'}$ is at least $\max_{e \in \mathcal{E}} c_e + 1 - c_{e'}$, $c_{e''} < c_{e'} + d_{e'}$. Therefore, the weight of the tree defined by the edge set $T_1 \cup T_2 \cup \{e''\}$ is lower than the one of $T$ which is a contradiction because the MST with respect to $\hat{\mathbf{x}}$ is $T$, i.e. the tree defined by $\hat{\mathbf{y}}$. Therefore, the optimal solution of [MSTI$_{Opt}$] is feasible in [MSTI$_{Tot}$]. Then, [MSTI$_{Opt}$] and [MSTI$_{Tot}$] provide the same optimal solution. $\square$
3.6 Parameter Analyses and Illustrative Problem

We consider different setups for experimentation in Section 3.9. These refer to the use of total and partial interdiction as well as considering a cardinality or a knapsack constraint. Let $\rho$ be the connectivity number of $\mathcal{G}$ with respect to interdiction costs $b_e$. Table 3.1 shows the possible settings of an MSTI problem instance.

<table><caption>Table 3.1: Instance cases</caption><thead><tr><th rowspan="2">Constraint</th><th colspan="2">Partial</th><th colspan="2">Total</th></tr><tr><th>d<sub>e</sub> &lt; &infin;, &forall;e &isin; &mathcal{E}<sub>e</sub><br>B &lt; &rho;<br>&rho; &ge; B</th><th>d<sub>e</sub> = &infin;, &forall;e &isin; &mathcal{E}<sub>e</sub><br>B &lt; &rho;<br>&rho; &ge; B</th></tr></thead><tbody><tr><td>Cardinality</td><td>&#x2713;</td><td>&#x2015;</td><td>&#x2713;</td><td>&#x2610;</td></tr><tr><td>Knapsack</td><td>&#x2713;</td><td>&#x2015;</td><td>&#x2713;</td><td>&#x2610;</td></tr></tbody></table>

Cases marked with a check-mark (✓) are defined as non-trivial instances. On the other hand, cases marked with a cross (✗) are discarded since they represent the scenarios where it is possible for the interdictor to disconnect $\mathcal{G}$. For the cases marked with black dots (●), it has to be verified that the edges associated with interdiction augmentations equal to infinity do not define a cut in $\mathcal{G}$. The value of $\rho$ is defined as the sum of the interdiction costs of the edges that define the minimum cut of $\mathcal{G}$, i.e. the set of edges when removed disconnects the network. However, a "real" cut might not exist for partial interdiction. In the case of partial interdiction, the augmentation of an edge may or may not be large enough to consider the interdiction as edge removal. Therefore, it is verified that if a budget larger than $\rho$ is defined then the edges that do have a large enough augmentation do not define a cut in the graph.

An illustrative example is presented to show the main differences of the instance settings. We first consider partial interdiction and a cardinality interdiction constraint. Let $\mathcal{G}$ be a complete graph with $|\mathcal{V}| = 4$, $|\mathcal{E}| = 6$, $\rho = 3$ and weights and interdiction augmentations as shown in Figure 3.2a. Semi-dotted lines represent partially interdicted edges, dotted lines represent removed edges and blue lines represent the MST with respect to interdiction. The optimal solution for $B = 2$ is presented in Figure 3.2b. No interdicted edges were selected in the MST because the increase in the edge weight is sufficiently large to be considered as eliminated during the computation of the MST. This is not always
the case. Consider a slightly different network where $c_{13} = 3$ then solve for $B = 2$. The optimal solution results as illustrated in Figure 3.2c. In this example, the weight of one of the interdicted edges, that is the edge {1,3} with a weight of $c_{13} + d_{13} = 8$, is still small enough to be chosen as part of the MST instead of the non-interdicted edges {1,2} and {3,4}. The question of whether interdicted edges are selected for the MST depends on the weights and augmentations of the network. Moreover, the larger the budget $B$, the more likely the network operator will pick interdicted edges.

<figure><img src="image_4.png" /><figcaption>Figure 3.2: Illustrative example of $G = (4, 6)$</figcaption></figure>

Using interdicted edges as part of the MST is not an issue when considering partial interdiction. However, this is not the case for total interdiction. First, if the interdictor has at her disposal a large budget that exceeds the value of $\rho$, she can immediately disconnect the graph which is a trivial case and is not considered throughout this manuscript. On the opposite case, we revise a small example when $B < \rho$ and the value of $d_e$ define a large enough value to model edge removal. Consider the problem defined by Figure 3.2a but with $d_e$ defining large values as in Section 3.5. The solution for $B = 2$ of this instance is presented in Figure 3.2d. As expected for total interdiction, interdicted edges are not part
of the MST. The interdictor prohibits all edges incident to node 4 except the one
with the highest weight, thus the follower has no choice but to use edge {3, 4}
and thereby inducing a large increase in the weight of the tree. This was not
the case in Figure 3.2b. These two examples show the drastic difference in the
solutions of the MSTI problem defined on the same graph when partial and total
interdiction are considered.

Since the cardinality constraint is a relaxation of the knapsack constraint,
an instance that is "valid" for the cardinality constraint is thus "valid" for the
knapsack constraint.

3.7 Valid Inequalities

This section presents valid inequalities to strengthen the linear relaxation of for-
mulation [MSTI<sub>Opt</sub>]. Two sets of inequalities are developed. The first makes use
of the linearization technique used to linearize the objective function (3.5a) of
[MSTI<sub>Opt</sub>]. This is done in order to find tighter optimal conditions. The second
set of inequalities modifies optimality constraints (3.6f)-(3.6i) to remove variables
y<sub>e</sub>, then we use the definition of t<sub>e</sub> to further simplify the constraints.

3.7.0.1 First Set of Valid Inequalities

General conditions are stated next. Let the sum $z_{uji} + z_{vij}$ be equal to $w^{uv}$. To
ease notation we simply use $w$ instead of $w^{uv}$. First, note that if $y_e = 0$, $e = \{i, j\}$,
then due to (3.6c) $w$ is zero. Second, if $y_e = 1$, then $w$ may be 1 or 2. We recall
that $z_{uji} = 1$ means that in the optimal $\mathbf{z}_u$-tree there exists a path that uses the
arc $(j, i)$ and with anti-root in $u$. Equivalently $z_{vij}$ means that in the optimal
$\mathbf{z}_v$-tree a path that uses arc $(i, j)$ and is ant-rooted in $v$ exists. This is possible
only when $y_f = 0$, otherwise edge $\{u, v\}$ would be selected and a cycle would be
formed. Consequently when $y_f = 1$, then $w$ cannot be 2.

We consider the following expression $w = y_e + (1 - y_f)(\Delta)$ where $\Delta$ represents a term which is set according to sets $\mathcal{E}_i$, $i = 2, 3, 4, 5$, introduced in Section 3.3 in order to cut off non-optimal integer solutions. Therefore, if $y_e = 1$ and for each set $\mathcal{E}_i$, the goal is to determine $\Delta$ terms as a expression of the interdiction variables $x_e$ and $x_f$ in order to make $w = 2$ for the cases when Theorem 3.4 is not
imposed. This is, an expression of the interdictions of e and f when optimality constraints (3.6f)-(3.6i) are relaxed.

**Case** $\mathcal{E}_2$. The expression $w = y_e + (1 - y_f)(1 - x_e)x_f$ is defined since $w = 2$ when $x_e = 0$ and $x_f = 1$. We develop the right-hand side and $w = y_e + x_f - x_e x_f - y_f x_f + y_f x_e x_f$. Note that $-x_e x_f + y_f x_e x_f = x_e x_f (y_f - 1) \le 0$. Thus, $w \le y_e + x_f - y_f x_f$. We replace $y_f x_f$ by $t_f$ and $w \le y_e + x_f - t_f$ is obtained.

**Case** $\mathcal{E}_3$. Expression $w$ is equal to 2 only when edge $f$ is interdicted. Therefore, $\Delta = x_f$ and $w = y_e + (1 - y_f)x_f$. A simple development of $w$ and the use of expression $t_f = y_f x_f$ yields to $w = y_e + x_f - t_f$.

**Case** $\mathcal{E}_4$. In this case, we define $w = y_e + (1 - y_f)(1 - x_e)$. We have that $w = 2$ when edge $e$ is not interdicted. Then $w$ can be expressed as $y_e - x_e + 1 - y_f(1 - x_e)$. If we consider $x_e = 0$, $w \le y_e - y_f + 1$ is obtained. The latter can be done since the interdiction of $f$ does not affect the expression.

**Case** $\mathcal{E}_5$. We define $w = y_e + (1 - y_f)[(1 - x_e) + x_e x_f]$; all possible interdiction cases of $e$ and $f$ except $x_e = 1$ and $x_f = 0$ make $w = 2$. After computation, it is obtained $w = y_e - x_e + x_e x_f - y_f + x_e y_f - y_f x_e x_f + 1$. We observe that $x_e x_f \le x_e + x_f$ and $x_e (y_f - t_f) \le 0$. Therefore, the resulting expression is $w \le y_e - y_f + x_f + 1$.

The valid inequalities are summarized below:

$$z_{uji} + z_{vij} \le y_e + x_f - t_f \quad \forall (e, f) \in \mathcal{E}_2, \mathcal{E}_3 \quad (3.11a)$$

$$z_{uji} + z_{vij} \le y_e - y_f + 1 \quad \forall (e, f) \in \mathcal{E}_4 \quad (3.11b)$$

$$z_{uji} + z_{vij} \le y_e - y_f + x_f + 1 \quad \forall (e, f) \in \mathcal{E}_5 \quad (3.11c)$$

The family of constraints (3.11a) can be added to [MSTI<sub>Opt</sub>]. However, (3.11a) replaces (3.6g) due to the next Lemma.

**Lemma 3.6.** Let $e = \{i, j\}$ and $f = \{u, v\}$ two edges either in $\mathcal{E}_2$ or $\mathcal{E}_3$. Then, constraints (3.6g) are dominated by (3.11a).

*Proof.* Let $e$ and $f$ be in either $\mathcal{E}_2$ or $\mathcal{E}_3$. By (3.6g) we have $z_{uji} + z_{vij} \le y_e + x_f$. Since $y_f$ and $x_f$ are binary, variables $t_f \ge 0$. Then $y_e + x_f - t_f \le y_e + x_f$ and constraints (3.11a) dominates (3.6g). □
# 3. FORMULATIONS FOR THE MSTI PROBLEM

## 3.7.0.2 Second Set of Valid Inequalities

The second set of inequalities is obtained by adding up $z_{uij}$ in both sides of constraints (3.6f). We can rearrange and group the terms in order to obtain

$$ (z_{uij} + z_{uji}) + z_{vij} - z_{uij} \le y_e \quad \forall (e, f) \in \mathcal{E}_1 $$

Then, by using constraint (3.3c) we obtain the following expression

$$ y_e + z_{vij} - z_{uij} \le y_e \quad \forall (e, f) \in \mathcal{E}_1 $$

Finally, we simplify and obtain $z_{vij} - z_{uij} \le 0$. The same process is performed on constraints (3.6g)-(3.6i). The resulting constraints are shown next:

$$ z_{vij} - z_{uij} \le 0 \quad \forall (e, f) \in \mathcal{E}_1 \quad (3.14a) $$

$$ z_{vij} - z_{uij} \le x_f \quad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_3 \quad (3.14b) $$

$$ z_{vij} - z_{uij} \le 1 - x_e \quad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_4 \quad (3.14c) $$

$$ z_{vij} - z_{uij} \le 1 - x_e + x_f \quad \forall (e, f) \in \mathcal{E}_5 \quad (3.14d) $$

Note that we can multiply the right hand side of constraints (3.14a)-(3.14d) by $y_e$ and the inequalities that we obtain are still valid. Indeed, when $y_e = 0$ variables $z_{vij}$ and $z_{uij}$ are zero due to constraint (3.6c). When $y_e = 1$ the equivalence of the expressions is trivial.

For this reason, it is possible to multiply the right hand side of constraints (3.14c) and (3.14d) by $y_e$ in order to obtain

$$ z_{vij} - z_{uij} \le (1 - x_e)y_e \quad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_4 \quad (3.15a) $$

$$ z_{vij} - z_{uij} \le (1 - x_e + x_f)y_e \quad \forall (e, f) \in \mathcal{E}_5 \quad (3.15b) $$

Since $t_e = x_e y_e$ and $x_f \ge y_e x_f$, we obtain the next constraints:
$$z_{vij} - z_{uij} \leq y_e - t_e \quad \forall (e, f) \in \mathcal{E}_2, \forall (e, f) \in \mathcal{E}_4 \quad (3.16a)$$

$$z_{vij} - z_{uij} \leq y_e + x_f - t_e \quad \forall (e, f) \in \mathcal{E}_5 \quad (3.16b)$$

## 3.8 Extension of the $\bar{B}$-edge Connected Certificate

The reduction of $\mathcal{G}$ to $\mathcal{G}_{\bar{B}}$ in Section 2.1 is only proved for the case of total interdiction, i.e. interdicted edges are to be removed. In this section, the $\bar{B}$-edge connected certificate is extended to consider partial interdiction. Let $\mathcal{G}(\mathcal{S})$ be an augmented graph of $\mathcal{G}$ where the weight of the edges in $\mathcal{S}$ is $c_e+d_e$ and let $\bar{B} > 1$, $\bar{B} \in \mathbb{Z}^+$.

**Lemma 3.7.** For any edge set $\mathcal{S}$, $\mathcal{S} \subseteq \mathcal{E}$, $|\mathcal{S}| < \bar{B}$ and $\sum_{e \in \mathcal{S}} b_e \leq B$, the edges of minimum spanning tree of $\mathcal{G}(\mathcal{S})$ belong to $\mathcal{G}_{\bar{B}}$.

*Proof.* Let $\mathcal{S} = \mathcal{S}_r \cup \mathcal{S}_a$. $\mathcal{S}_r$ is an edge set whose edges have an interdiction augmentation of infinity, i.e. these edges are considered as removed when interdicted. $\mathcal{S}_a$ is an edge set whose elements are to be augmented by a finite amount. Clearly, $\mathcal{S} \subseteq \mathcal{E}$; assume that $|\mathcal{S}| < \bar{B}$ and $\sum_{e \in \mathcal{S}} b_e \leq B$.

If $\mathcal{S}_a = \emptyset$ then all edges of $\mathcal{S}$ are considered as removed when interdicted and the proof is reduced to that of Lemma 2.1.

Assume $\mathcal{S}_a \neq \emptyset$. The proof is developed by contradiction. Suppose there is an edge $e^* = (u, v) \in \mathcal{E} \setminus \cup_{i=0}^{\bar{B}} T_i$ in the MST $T^*$ of $\mathcal{G}(\mathcal{S})$. If edge $e^*$ is removed from $T^*$, then the connected components $\hat{T}_1$ and $\hat{T}_2$ are obtained. Assume that $\hat{T}_1$ and $\hat{T}_2$ contain node $u$ and node $v$, respectively. In each $T_i$, $i = 0, ..., \bar{B}$, there exists a unique path between $u$ and $v$. The weight of $e^*$ is larger than the weight of any edge of any $u-v$ path of $T_i$, $i = 0, ..., \bar{B}$, otherwise $e^*$ would have been chosen for one of the trees. The budget $B$ is not large enough to let $\mathcal{S}_r$ define a cut of $\mathcal{G}$. In addition, $|\mathcal{S}| < \bar{B}$. Therefore, there must exists a non-interdicted edge in one of the $u-v$ paths that connects $\hat{T}_1$ and $\hat{T}_2$ that has a weight lower than the weight of $e^*$. Therefore, a tree of $\mathcal{G}(\mathcal{S})$ with a smaller weight than $T^*$ is found. Hence, a contradiction. $\square$
## 3.9 Computational Experiments

### 3.9.1 Instance Specifications

Instances of different sizes are generated to represent all cases shown in Table 3.1. The instance generation is partly based on that in Bazgan et al. (2012). Networks considered are undirected complete graphs of $|V|$ nodes. The values of $c_e$, $e \in \mathcal{E}$, are uniformly generated in [1, 100]. An arbitrary total order is imposed for edges of the same weight without loss of generality. When total interdiction is considered, $d_e = \max_{f \in \mathcal{E}} c_f - c_e + 1$ for all $e \in \mathcal{E}$. In the partial interdiction case, $d_e$ is randomly generated between 1 and $\max_{f \in \mathcal{E}} c_f - c_e + 1$. When the interdiction budget constraint is formulated as a cardinality constraint, $b_e = 1$ for all $e \in \mathcal{E}$. When it is formulated as a knapsack constraint, $b_e$ is randomly generated between 1 and 100.

In Section 3.8, it is shown that the size of the network can be reduced by using the $\bar{B}$-edge connected certificate of $\mathcal{G}$. This preprocessing is implemented in our experimentation. The preprocessing of the network depends on knowing in advance the maximum number of edges to interdict. In the cardinality case, $\bar{B}$ is equal to the budget $B$. Clearly, it is possible to know the maximum number of edges that the interdictor can interdict when considering a knapsack constraint by setting $\bar{B} = \max\{\sum_{e \in \mathcal{E}} x_e : \sum_{e \in \mathcal{E}} b_e x_e \le B\}$. However, preliminary experimentation proved that $\bar{B}$ turns out to be large enough such that the network reduction ends up providing the original network. Therefore, the preprocessing is only meaningful when considering a cardinality budget constraint.

The formulations are implemented in a 64-bit computer with an Intel Xeon(R) CPU E5-2630 v4 (2.20GHz) processor and 64 GB of RAM and solved using CPLEX 12.9. A time limit of 3600 seconds is imposed for each experiment.

### 3.9.2 Tuning Phase for Valid Inequalities

Preliminary tuning experiments are carried out to verify the impact of the valid inequalities developed in Section 3.7. Let $[V_0]$ be the [MSTI$_{Opt}$] to which Lemma 3.6 is applied, i.e. constraints (3.6g) are replaced by (3.11a). $[V_1]$ represent model $[V_0]$ with constraints (3.11b), $[V_2]$ with constraints (3.11c) and $[V_3]$ with both of them. The [MSTI$_{Opt}$] and the latter four formulations are used to solve the MSTI problem on complete graphs of different sizes and budgets. Total interdiction and
<table><caption>Table 3.2: Preliminary results of the first set of valid inequalities</caption><thead><tr><th>|V|</th><th>B</th><th>[MSTI<sub>Opt</sub>]</th><th>[V<sub>0</sub>]</th><th>[V<sub>1</sub>]</th><th>[V<sub>2</sub>]</th><th>[V<sub>3</sub>]</th></tr></thead><tbody><tr><td>10</td><td>5</td><td>710.15</td><td>492.26</td><td>492.26</td><td>492.26</td><td>492.26</td></tr><tr><td>10</td><td>5</td><td>681.16</td><td>459.47</td><td>459.47</td><td>459.47</td><td>459.47</td></tr><tr><td>15</td><td>3</td><td>218.84</td><td>218.84</td><td>218.84</td><td>217.96</td><td>217.96</td></tr><tr><td>20</td><td>3</td><td>232.81</td><td>232.81</td><td>232.81</td><td>232.81</td><td>232.81</td></tr></tbody></table>

cardinality constraint are assumed. The computational results are presented in Table 3.2.

The first two columns represent the number of nodes and the budget considered for each instance. Each row represents a different complete graph. Table 3.2 reports the LP relaxation of each of the five models. The values shown in column [MSTI<sub>Opt</sub>] are upper bounds on the LP relaxations of formulations [V<sub>i</sub>], i = 0, 1, 2, 3, since the latter models are [MSTI<sub>Opt</sub>] with additional constraints. [V<sub>0</sub>] and [V<sub>1</sub>] provide tighter values for the first two instances and exactly the same values for the LP relaxation as [MSTI<sub>Opt</sub>]. We see that both [V<sub>2</sub>] and [V<sub>3</sub>] slightly improves the LP relaxation of the third instance. The latter implies that constraint (3.11b) is inactive since the definition of these valid inequalities in [V<sub>1</sub>] and [V<sub>3</sub>] do not improve the bounds. On the other hand, even if it was for less than a unit, (3.11c) improved the LP value on the instance of 15 nodes. Therefore, only [V<sub>2</sub>], considering constraints (3.11a) and (3.11c), is considered in the final experimentation. This formulation is renamed as [MSTI-V<sub>2</sub>].

Analogously, experimentation of all possible combinations of the second set of valid inequalities is done. Table 3.3 presents the names representing the different implementations of each of the constraints.

<table><caption>Table 3.3: Names of formulations with valid inequalities.</caption><thead><tr><th>Name</th><th>Constraints</th><th>Name</th><th>Constraints</th><th>Name</th><th>Constraints</th></tr></thead><tbody><tr><td>[V<sub>4</sub>]</td><td>(3.14a)</td><td>[V<sub>9</sub>]</td><td>(3.14a), (3.16a)</td><td>[V<sub>14</sub>]</td><td>(3.14a), (3.14b), (3.16a)</td></tr><tr><td>[V<sub>5</sub>]</td><td>(3.14b)</td><td>[V<sub>10</sub>]</td><td>(3.14a), (3.16b)</td><td>[V<sub>15</sub>]</td><td>(3.14a), (3.14b), (3.16b)</td></tr><tr><td>[V<sub>6</sub>]</td><td>(3.16a)</td><td>[V<sub>11</sub>]</td><td>(3.14b), (3.16a)</td><td>[V<sub>16</sub>]</td><td>(3.14a), (3.16a), (3.16b)</td></tr><tr><td>[V<sub>7</sub>]</td><td>(3.16b)</td><td>[V<sub>12</sub>]</td><td>(3.14b), (3.16b)</td><td>[V<sub>17</sub>]</td><td>(3.14b), (3.16a), (3.16b)</td></tr><tr><td>[V<sub>8</sub>]</td><td>(3.14a), (3.14b)</td><td>[V<sub>13</sub>]</td><td>(3.16a), (3.16b)</td><td>[V<sub>18</sub>]</td><td>(3.14a), (3.14b), (3.16a), (3.16b)</td></tr></tbody></table>

Table 3.4 shows the preliminary results of the second set of valid inequalities assuming total interdiction and cardinality constraint. Our first observation is that constraints (3.14a) and (3.16a) are inactive during optimization and do not
## 3. FORMULATIONS FOR THE MSTI PROBLEM

improve the LP relaxation of [MSTI<sub>Opt</sub>]. This is confirmed in the results of columns [V<sub>4</sub>], [V<sub>6</sub>] and [V<sub>9</sub>] thus we can discard all formulations including any of those constraints. For the first two instances, [V<sub>7</sub>] and [V<sub>12</sub>] provide the tightest values. The common family of valid inequalities in the last two models is (3.16b). For the instances of sizes 15 and 20, the best LP relaxation values are obtained by [V<sub>5</sub>] and [V<sub>12</sub>]. In this case, the common constraints is (3.14b). Therefore, [V<sub>12</sub>] is the tighter formulation. For the final experimentation, only the best performing formulation, i.e. [V<sub>12</sub>] considering (3.14b) and (3.16b), is analyzed and compared. [V<sub>12</sub>] is renamed as [MSTI-V<sub>12</sub>].

<table><caption>Table 3.4: Preliminary results of the second set of valid inequalities</caption><thead><tr><th>|V|</th><th>B</th><th>[MSTI<sub>Opt</sub>]</th><th>[V<sub>4</sub>]</th><th>[V<sub>5</sub>]</th><th>[V<sub>6</sub>]</th><th>[V<sub>7</sub>]</th><th>[V<sub>8</sub>]</th><th>[V<sub>9</sub>]</th><th>[V<sub>10</sub>]</th><th>[V<sub>11</sub>]</th><th>[V<sub>12</sub>]</th><th>[V<sub>13</sub>]</th><th>[V<sub>14</sub>]</th><th>[V<sub>15</sub>]</th><th>[V<sub>16</sub>]</th><th>[V<sub>17</sub>]</th><th>[V<sub>18</sub>]</th></tr></thead><tbody><tr><td>10</td><td>5</td><td>710.15</td><td>710.15</td><td>709.98</td><td>710.15</td><td>688.93</td><td>709.98</td><td>710.15</td><td>688.93</td><td>709.98</td><td>688.93</td><td>688.93</td><td>709.98</td><td>688.94</td><td>688.93</td><td>688.94</td><td>688.94</td></tr><tr><td>10</td><td>5</td><td>681.16</td><td>681.16</td><td>681.44</td><td>414.89</td><td>660.24</td><td>681.44</td><td>681.16</td><td>660.24</td><td>681.44</td><td>660.24</td><td>660.24</td><td>681.44</td><td>660.24</td><td>660.24</td><td>660.24</td><td>660.24</td></tr><tr><td>15</td><td>3</td><td>218.84</td><td>218.84</td><td>202.93</td><td>218.84</td><td>216.96</td><td>202.93</td><td>218.84</td><td>216.96</td><td>202.93</td><td>202.93</td><td>216.96</td><td>202.93</td><td>202.93</td><td>216.96</td><td>202.93</td><td>202.93</td></tr><tr><td>20</td><td>3</td><td>232.81</td><td>232.81</td><td>228.69</td><td>232.81</td><td>228.69</td><td>232.81</td><td>228.69</td><td>232.81</td><td>228.69</td><td>228.62</td><td>232.81</td><td>228.69</td><td>228.62</td><td>232.81</td><td>228.62</td><td>228.62</td></tr></tbody></table>

### 3.9.3 Final Experimentation

Computational results on the performance of the different mathematical formulations presented in this manuscript are reported in this section. The formulations assessed in this chapter are: the formulation retrieved from the literature [MSTI<sub>DBa</sub>]; our original model [MSTI<sub>Opt</sub>] based on the MST formulation of Martin (1991); two versions of [MSTI<sub>Opt</sub>], [MSTI-V<sub>2</sub>] and [MSTI-V<sub>12</sub>], strengthened by two sets of valid inequalities; the dual version [MSTI<sub>Dual</sub>] of [MSTI<sub>Opt</sub>] and a more compact version [MSTI<sub>SDual</sub>] of [MSTI<sub>Dual</sub>] by removing one family of constraints of the MST inner problem. Networks of size |V| = 10, 15, 20, 25, 30 and 50 are considered. For a cardinality constraint, B = 3, 5 and 7. In the case of a knapsack constraint, the budget is defined as a proportion of the largest edge weight of the graph. Thus, $B = \eta \cdot \max_{e \in \mathcal{E}} c_e$ where $\eta = 0.2, 0.4, 0.6, 0.8, 1$ and 1.2.

For each instance in the following tables, the average computational time, the average number of Branch-and-Bound nodes that are explored, the average relative gap at root node, the average relative gap between the best known solution and the upper bound at the end of optimization of four different networks is reported. The last column of each set of data represents the number of solved instances out of the four test networks. A dash (-) is reported when the instance
could not be solved or no integer solution could be found to compute a opti-
mality gap under the time limit. Assuming a cardinality constraint, Tables 3.5
and 3.6 detail the computational results when total and partial interdiction are
considered, respectively.

When considering total interdiction, instances of 10 nodes are efficiently solved
by both [MSTI<sub>DBa</sub>] and [MSTI<sub>SDual</sub>]. However, [MSTI<sub>DBa</sub>] solves the instances
where *B* = 5 at root node. On the other hand, [MSTI<sub>SDual</sub>] is, in average, the
best formulation in terms of computation time, size of the Branch-and-Bound
tree and relative gap at root node when *B* = 7. Likewise, instances of 15 nodes
are solved in a fairly short time by [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>]. [MSTI<sub>SDual</sub>]
obtains the shorter computation times in this case with the exception of instances
of *B* = 7 where it is outperformed by [MSTI<sub>Dual</sub>] only by an average 0.3 of
seconds. Even though [MSTI<sub>Tot</sub>] has the tighter relative gaps at root node and
the less number of nodes explored in the Branch-and-Bound tree, it obtains much
larger computation times. A similar situation occurs for [MSTI<sub>Opt</sub>]. Moreover,
[MSTI<sub>Opt</sub>] and [MSTI<sub>Tot</sub>] are unable to solve instances with the largest budget
in graphs of size 20. However, [MSTI<sub>Tot</sub>] still obtains better relative gaps at the
root node when the budget is set to 5 and 7. [MSTI-V<sub>2</sub>] and [MSTI-V<sub>12</sub>] are no
better than [MSTI<sub>Opt</sub>], in several instances [MSTI-V<sub>2</sub>] obtains a tighter relative
gap at the root node but the computational time is practically doubled. In the
case of [MSTI-V<sub>12</sub>], greater relative gaps and computational times are obtained
and even small size instances are unable to be solved. [MSTI<sub>SDual</sub>] still provides
the fastest computational times yet the tightest gaps belong to [MSTI<sub>Tot</sub>] and
[MSTI<sub>Opt</sub>]. The limits of the formulations start on instances of 25 nodes where
only one instance of budget *B* = 7 is solved by [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>].
A pattern similar to the other instance sizes is observed when *B* = 3 and 5.
Instances of 30 nodes with a budget of 3 are solved by all models with [MSTI<sub>Dual</sub>]
and [MSTI<sub>SDual</sub>] as the most efficient. Only [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] are able
to solve three out of four instances when *B* = 5. The limitations of our models
are reached at instances of 50 nodes and a budget of 7.

Models [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] provide the best results when considering
partial interdiction as shown in Table 3.6. All graphs of size 10 are solved in
less than a second by all formulations. [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] out-stand by
solving all them at root node. Then, a similar pattern is observed as in the exper-
iments where total interdiction is imposed, i.e. [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] excel
in computational time even though smaller relative gaps and fewer number of ex-
plored nodes are occasionally reported by the other formulations. Nevertheless,
all formulations are unable to solve instances of 50 nodes.

The results obtained by considering a knapsack interdiction constraint are shown in Tables 3.7 and 3.8. The budget for each graph is reported as $\eta$, the fraction of the largest edge weight for simplification. We analyze first the statistics when total interdiction and a knapsack constraint are assumed. Unlike results of those of cardinality constraint, all test instances are solved by at least formulation [MSTI<sub>Tot</sub>]. For instances of 10, 15 and 20 nodes and $\eta \le 1$, the results are practically identical for any of the models except for [MSTI-V<sub>12</sub>]. They differentiate in the computational time, although the largest difference in time between the models is no more than five seconds. For these same sizes, the computational time slightly increases when $\eta = 1.2$. Once more, similar results are obtained in instances of 25 and 30 nodes. However, instances where $\eta \ge 0.6$ are not solved at root node. For [MSTI<sub>Opt</sub>], [MSTI-V<sub>2</sub>] and [MSTI<sub>Tot</sub>] the gap at root node is of less than 1.17 where $\eta \le 0.8$. [MSTI<sub>Tot</sub>] gives in average the tightest gaps but it is sometimes outperformed by [MSTI-V<sub>12</sub>]. [MSTI-V<sub>12</sub>] behaves differently than its counterparts, most of the instances are not solved at root node nevertheless [MSTI-V<sub>12</sub>] occasionally reports better average computational times than [MSTI<sub>Opt</sub>]; moreover [MSTI-V<sub>12</sub>] solved all of the test instances. For the largest instance sizes, the statistics decay significantly for [MSTI<sub>DBa</sub>], [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>]. In the case of [MSTI<sub>DBa</sub>], no instance is solved when $\eta$ is greater than or equal to 0.6 and greater than or equal to 0.8 for [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>].

In Table 3.8, [MSTI<sub>SDual</sub>] is the only model capable of solving all of the in-
stances at root node for networks of 10, 15 and 20 nodes when considering partial
interdiction. When the size of the network increases to 50, [MSTI<sub>DBa</sub>], [MSTI<sub>Dual</sub>]
and [MSTI<sub>SDual</sub>] deteriorate. [MSTI<sub>DBa</sub>] is unable to solve to optimality in the al-
located time any of the largest instances. [MSTI<sub>SDual</sub>] solves most of the instances
with η ≤ 0.8 but at a high computational time. [MSTI<sub>Opt</sub>] and [MSTI-V<sub>2</sub>] pro-
vide very similar results but [MSTI<sub>Opt</sub>] out-stands in computational time. Even
though [MSTI<sub>Opt</sub>] have tightest relative gaps at root node than [MSTI-V<sub>12</sub>], the
latter reports shorter resolution times in instances of 25 nodes or more, however
the difference is not larger than several seconds. Furthermore, [MSTI-V₁₂] is able
to solve a few of the largest instances.
3. FORMULATIONS FOR THE MSTI PROBLEM

<table><caption>Table 3.5: Computational results considering total interdiction and cardinality constraint.</caption><thead><tr><th colspan="10">Conflg.</th><th colspan="10">Total Interdiction</th></tr><tr><th colspan="2">[V]</th><th colspan="2">B</th><th colspan="2">Time (s)</th><th colspan="2">Nodes</th><th colspan="2">Time (s)</th><th colspan="2">[MSTI]Op</th><th colspan="2">Gap<sub>r</sub>(%) Gap (%) Opt/Tot</th><th colspan="2">Time (s)</th><th colspan="2">Nodes</th><th colspan="2">Time (s)</th><th colspan="2">[MSTI]V<sub>1/2</sub></th><th colspan="2">Gap<sub>r</sub>(%) Gap (%) Opt/Tot</th><th colspan="2">Time (s)</th><th colspan="2">Nodes</th><th colspan="2">[MSTI]D<sub>pa</sub></th><th colspan="2">Gap<sub>r</sub>(%) Gap (%) Opt/Tot</th></tr><tr><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>10</td><td>3</td><td>0.8</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>1.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.3</td><td>68.0</td><td>77.42</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>10.6</td><td>2517.0</td><td>161.5</td><td>0.00</td><td>4/4</td><td>15.4</td><td>1827.0</td><td>124.13</td><td>0.00</td><td>4/4</td><td>20.8</td><td>2336.5</td><td>318.92</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>31.3</td><td>9722.0</td><td>190.6</td><td>0.00</td><td>4/4</td><td>57.4</td><td>11475.5</td><td>141.10</td><td>0.00</td><td>4/4</td><td>57.7</td><td>9103.8</td><td>325.27</td><td>0.00</td><td>4/4</td><td>1.0</td><td>1983.0</td><td>25.01</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>15</td><td>3</td><td>5.5</td><td>57.3</td><td>13.7</td><td>0.00</td><td>4/4</td><td>9.9</td><td>45.5</td><td>12.26</td><td>0.00</td><td>4/4</td><td>8.1</td><td>167.8</td><td>51.69</td><td>0.00</td><td>4/4</td><td>0.9</td><td>106.8</td><td>9.64</td><td>0.00</td><td>4/4</td><td>0.9</td><td>106.8</td><td>9.64</td><td>0.00</td><td>4/4</td><td>0.9</td><td>106.8</td><td>9.64</td><td>0.00</td><td>4/4</td><td>0.9</td><td>106.8</td><td>9.64</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>94.6</td><td>2113.3</td><td>58.5</td><td>0.00</td><td>4/4</td><td>164.1</td><td>1521.0</td><td>54.55</td><td>0.00</td><td>4/4</td><td>131.2</td><td>2033.8</td><td>166.17</td><td>0.00</td><td>4/4</td><td>14.9</td><td>9315.8</td><td>68.28</td><td>0.00</td><td>4/4</td><td>14.9</td><td>9315.8</td><td>68.28</td><td>0.00</td><td>4/4</td><td>14.9</td><td>9315.8</td><td>68.28</td><td>0.00</td><td>4/4</td><td>14.9</td><td>9315.8</td><td>68.28</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>1903.6</td><td>11188.3</td><td>193.7</td><td>0.00</td><td>4/4</td><td>3404.7</td><td>12177.8</td><td>176.32</td><td>7.32</td><td>2/4</td><td>3600.0</td><td>8805.5</td><td>397.42</td><td>91.32</td><td>0/4</td><td>102.5</td><td>53304.8</td><td>99.68</td><td>0.00</td><td>4/4</td><td>102.5</td><td>53304.8</td><td>99.68</td><td>0.00</td><td>4/4</td><td>102.5</td><td>53304.8</td><td>99.68</td><td>0.00</td><td>4/4</td><td>102.5</td><td>53304.8</td><td>99.68</td><td>0.00</td><td>4/4</td></tr><tr><td>20</td><td>3</td><td>24.7</td><td>97.0</td><td>12.7</td><td>0.00</td><td>4/4</td><td>49.8</td><td>111.8</td><td>14.46</td><td>0.00</td><td>4/4</td><td>46.6</td><td>484.8</td><td>51.12</td><td>0.00</td><td>4/4</td><td>4.3</td><td>655.5</td><td>26.69</td><td>0.00</td><td>4/4</td><td>4.3</td><td>655.5</td><td>26.69</td><td>0.00</td><td>4/4</td><td>4.3</td><td>655.5</td><td>26.69</td><td>0.00</td><td>4/4</td><td>4.3</td><td>655.5</td><td>26.69</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>1379.2</td><td>4701.3</td><td>50.1</td><td>0.00</td><td>4/4</td><td>2468.6</td><td>4256.0</td><td>62.66</td><td>2.21</td><td>3/4</td><td>3600.0</td><td>5189.3</td><td>137.99</td><td>28.90</td><td>0/4</td><td>153.4</td><td>2579.8</td><td>71.17</td><td>0.00</td><td>4/4</td><td>153.4</td><td>2579.8</td><td>71.17</td><td>0.00</td><td>4/4</td><td>153.4</td><td>2579.8</td><td>71.17</td><td>0.00</td><td>4/4</td><td>153.4</td><td>2579.8</td><td>71.17</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>3600.0</td><td>1576.0</td><td>116.9</td><td>63.58</td><td>0/4</td><td>3600.0</td><td>294.5</td><td>98.37</td><td>77.92</td><td>0/4</td><td>3600.0</td><td>707.0</td><td>234.99</td><td>179.26</td><td>0/4</td><td>1468.3</td><td>186060.3</td><td>95.94</td><td>0.00</td><td>4/4</td><td>1468.3</td><td>186060.3</td><td>95.94</td><td>0.00</td><td>4/4</td><td>1468.3</td><td>186060.3</td><td>95.94</td><td>0.00</td><td>4/4</td><td>1468.3</td><td>186060.3</td><td>95.94</td><td>0.00</td><td>4/4</td></tr><tr><td>25</td><td>3</td><td>108.7</td><td>187.8</td><td>12.1</td><td>0.00</td><td>4/4</td><td>222.4</td><td>164.0</td><td>11.84</td><td>0.00</td><td>4/4</td><td>331.5</td><td>908.3</td><td>45.54</td><td>0.00</td><td>4/4</td><td>19.2</td><td>1445.5</td><td>26.51</td><td>0.00</td><td>4/4</td><td>19.2</td><td>1445.5</td><td>26.51</td><td>0.00</td><td>4/4</td><td>19.2</td><td>1445.5</td><td>26.51</td><td>0.00</td><td>4/4</td><td>19.2</td><td>1445.5</td><td>26.51</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>3032.0</td><td>1826.8</td><td>59.0</td><td>17.16</td><td>2/4</td><td>3506.0</td><td>529.5</td><td>43.80</td><td>26.19</td><td>1/4</td><td>3600.0</td><td>489.5</td><td>106.08</td><td>71.41</td><td>0/4</td><td>575.9</td><td>36222.8</td><td>60.36</td><td>0.00</td><td>4/4</td><td>575.9</td><td>36222.8</td><td>60.36</td><td>0.00</td><td>4/4</td><td>575.9</td><td>36222.8</td><td>60.36</td><td>0.00</td><td>4/4</td><td>575.9</td><td>36222.8</td><td>60.36</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>3600.0</td><td>37.3</td><td>113.3</td><td>104.09</td><td>0/4</td><td>3600.0</td><td>0.0</td><td>128.41</td><td>128.41</td><td>0/4</td><td>3600.0</td><td>72.5</td><td>185.92</td><td>170.42</td><td>0/4</td><td>3600.0</td><td>97829.0</td><td>84.33</td><td>20.20</td><td>0/4</td><td>3600.0</td><td>97829.0</td><td>84.33</td><td>20.20</td><td>0/4</td><td>3600.0</td><td>97829.0</td><td>84.33</td><td>20.20</td><td>0/4</td><td>3600.0</td><td>97829.0</td><td>84.33</td><td>20.20</td><td>0/4</td></tr><tr><td>30</td><td>3</td><td>896.4</td><td>911.3</td><td>18.50</td><td>0.00</td><td>4/4</td><td>2019.9</td><td>1016.5</td><td>24.20</td><td>0.00</td><td>4/4</td><td>3115.5</td><td>1871.5</td><td>54.12</td><td>8.37</td><td>2/4</td><td>48.0</td><td>2701.8</td><td>26.19</td><td>0.00</td><td>4/4</td><td>48.0</td><td>2701.8</td><td>26.19</td><td>0.00</td><td>4/4</td><td>48.0</td><td>2701.8</td><td>26.19</td><td>0.00</td><td>4/4</td><td>48.0</td><td>2701.8</td><td>26.19</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>3600.0</td><td>78.3</td><td>56.08</td><td>49.56</td><td>0/4</td><td>3600.0</td><td>0.0</td><td>79.00</td><td>79.00</td><td>0/4</td><td>3600.0</td><td>86.3</td><td>144.29</td><td>110.24</td><td>0/4</td><td>2502.1</td><td>54591.5</td><td>63.78</td><td>10.37</td><td>2/4</td><td>2502.1</td><td>54591.5</td><td>63.78</td><td>10.37</td><td>2/4</td><td>2502.1</td><td>54591.5</td><td>63.78</td><td>10.37</td><td>2/4</td><td>2502.1</td><td>54591.5</td><td>63.78</td><td>10.37</td><td>2/4</td></tr><tr><td>7</td><td>3600.0</td><td>0.0</td><td>177.42</td><td>177.42</td><td>0/4</td><td>3600.0</td><td>0.0</td><td>171.56</td><td>171.56</td><td>0/4</td><td>3600.0</td><td>7.0</td><td>275.38</td><td>272.31</td><td>0/4</td><td>3600.0</td><td>33495.0</td><td>92.29</td><td>43.44</td><td>0/4</td><td>3600.0</td><td>33495.0</td><td>92.29</td><td>43.44</td><td>0/4</td><td>3600.0</td><td>33495.0</td><td>92.29</td><td>43.44</td><td>0/4</td><td>3600.0</td><td>33495.0</td><td>92.29</td><td>43.44</td><td>0/4</td></tr><tr><td>50</td><td>3</td><td>3600.0</td><td>0.0</td><td>26.62</td><td>26.62</td><td>0/4</td><td>3600.0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>10</td><td>3</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>279.0</td><td>11.57</td><td>0.00</td><td>4/4</td><td>2.7</td><td>55.8</td><td>18.03</td><td>0.00</td><td>4/4</td><td>2.7</td><td>55.8</td><td>18.03</td><td>0.00</td><td>4/4</td><td>2.7</td><td>55.8</td><td>18.03</td><td>0.00</td><td>4/4</td><td>2.7</td><td>55.8</td><td>18.03</td><td>0.00</td><td>4/4</td><td>2.7</td><td>55.8</td><td>18.03</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>1.0</td><td>1981.3</td><td>27.91</td><td>0.00</td><td>4/4</td><td>0.7</td><td>1716.3</td><td>17.41</td><td>0.00</td><td>4/4</td><td>3.2</td><td>37.5</td><td>14.34</td><td>0.00</td><td>4/4</td><td>3.2</td><td>37.5</td><td>14.34</td><td>0.00</td><td>4/4</td><td>3.2</td><td>37.5</td><td>14.34</td><td>0.00</td><td>4/4</td><td>3.2</td><td>37.5</td><td>14.34</td><td>0.00</td><td>4/4</td><td>3.2</td><td>37.5</td><td>14.34</td><td>0.00</td><td>4/4</td></tr><tr><td>15</td><td>3</td><td>0.7</td><td>113.0</td><td>1.70</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.3</td><td>61.5</td><td>10.80</td><td>0.00</td><td>4/4</td><td>3.3</td><td>61.5</td><td>10.80</td><td>0.00</td><td>4/4</td><td>3.3</td><td>61.5</td><td>10.80</td><td>0.00</td><td>4/4</td><td>3.3</td><td>61.5</td><td>10.80</td><td>0.00</td><td>4/4</td><td>3.3</td><td>61.5</td><td>10.80</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>7.6</td><td>9031.0</td><td>57.46</td><td>0.00</td><td>4/4</td><td>6.9</td><td>8834.8</td><td>53.38</td><td>0.00</td><td>4/4</td><td>45.6</td><td>2371.5</td><td>47.74</td><td>0.00</td><td>4/4</td><td>45.6</td><td>2371.5</td><td>47.74</td><td>0.00</td><td>4/4</td><td>45.6</td><td>2371.5</td><td>47.74</td><td>0.00</td><td>4/4</td><td>45.6</td><td>2371.5</td><td>47.74</td><td>0.00</td><td>4/4</td><td>45.6</td><td>2371.5</td><td>47.74</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>56.8</td><td>54769.0</td><td>90.65</td><td>0.00</td><td>4/4</td><td>57.1</td><td>56743.8</td><td>95.52</td><td>0.00</td><td>4/4</td><td>4/4</td><td>603.0</td><td>9792.5</td><td>90.18</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td></tr><tr><td>20</td><td>3</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td><td>13.6</td><td>72.3</td><td>10.98</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>71.9</td><td>23876.8</td><td>65.44</td><td>0.00</td><td>4/4</td><td>41.2</td><td>21990.3</td><td>62.42</td><td>0.00</td><td>4/4</td><td>45.7</td><td>3794.8</td><td>50.37</td><td>0.00</td><td>4/4</td><td>45.7</td><td>3794.8</td><td>50.37</td><td>0.00</td><td>4/4</td><td>45.7</td><td>3794.8</td><td>50.37</td><td>0.00</td><td>4/4</td><td>45.7</td><td>3794.8</td><td>50.37</td><td>0.00</td><td>4/4</td><td>45.7</td><td>3794.8</td><td>50.37</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>599.1</td><td>190184.5</td><td>90.99</td><td>0.00</td><td>4/4</td><td>579.0</td><td>18570.3</td><td>95.92</td><td>0.00</td><td>4/4</td><td>3600.0</td><td>6434.8</td><td>81.32</td><td>29.06</td><td>0/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td></tr><tr><td>25</td><td>3</td><td>10.0</td><td>1318.0</td><td>28.13</td><td>0.00</td><td>4/4</td><td>10.3</td><td>1490.8</td><td>29.07</td><td>0.00</td><td>4/4</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td><td>55.7</td><td>212.3</td><td>10.32</td><td>0.00</td><td>4/4</td></tr><tr><td>30</td><td>3</td><td>42.8</td><td>2668.5</td><td>29.69</td><td>0.00</td><td>4/4</td><td>43.8</td><td>2571.0</td><td>28.93</td><td>0.00</td><td>4/4</td><td>406.9</td><td>876.8</td><td>14.70</td><td>0.00</td><td>4/4</td><td>406.9</td><td>876.8</td><td>14.70</td><td>0.00</td><td>4/4</td><td>406.9</td><td>876.8</td><td>14.70</td><td>0.00</td><td>4/4</td><td>406.9</td><td>876.8</td><td>14.70</td><td>0.00</td><td>4/4</td><td>406.9</td><td>876.8</td><td>14.70</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>2191.5</td><td>86170.3</td><td>64.67</td><td>2.70</td><td>3/4</td><td>2308.2</td><td>90281.5</td><td>63.83</td><td>2.69</td><td>3/4</td><td>3600.0</td><td>89825</td><td>80.03</td><td>41.65</td><td>0/4</td><td>3600.0</td><td>89825</td><td>80.03</td><td>41.65</td><td>0/4</td><td>3600.0</td><td>89825</td><td>80.03</td><td>41.65</td><td>0/4</td><td>3600.0</td><td>89825</td><td>80.03</td><td>41.65</td><td>0/4</td><td>3600.0</td><td>89825</td><td>80.03</td><td>41.65</td><td>0/4</td></tr><tr><td>7</td><td>3600.0</td><td>58510.5</td><td>96.57</td><td>40.23</td><td>0/4</td><td>3600.0</td><td>57981.0</td><td>96.44</td><td>40.18</td><td>0/4</td><td>3600.0</td><td>29.3</td><td>138.52</td><td>131.72</td><td>0/4</td><td>3600.0</td><td>29.3</td><td>138.52</td><td>131.72</td><td>0/4</td><td>3600.0</td><td>29.3</td><td>138.52</td><td>131.72</td><td>0/4</td><td>3600.0</td><td>29.3</td><td>138.52</td><td>131.72</td><td>0/4</td><td>3600.0</td><td>29.3</td><td>138.52</td><td>131.72</td><td>0/4</td></tr><tr><td>50</td><td>3</td><td>1951.5</td><td>8408.0</td><td>20.49</td><td>2.70</td><td>3/4</td><td>1995.6</td><td>9803.8</td><td>19.35</td><td>2.66</td><td>3/4</td><td>3600.0</td><td>44.3</td><td>22.30</td><td>21.43</td><td>0/4</td><td>3600.0</td><td>44.3</td><td>22.30</td><td>21.43</td><td>0/4</td><td>3600.0</td><td>44.3</td><td>22.30</td><td>21.43</td><td>0/4</td><td>3600.0</td><td>44.3</td><td>22.30</td><td>21.43</td><td>0/4</td><td>3600.0</td><td>44.3</td><td>22.30</td><td>21.43</td><td>0/4</td></tr></tbody></table>
<table><caption>Table 3.6: Computational results considering partial interdiction and cardinality constraint.</caption><thead><tr><th rowspan="2">Config.</th><th rowspan="2">[P]</th><th rowspan="2">B</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap, (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt./Tot</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th colspan="2">Partial Interdiction</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap, (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt./Tot</th></tr><tr><th>[MSTI<sub>Opt</sub>]</th><th>[MSTI<sub>V2</sub>]</th><th>Gap, (%)</th><th>Opt./Tot</th></tr></thead><tbody><tr><td rowspan="3">10</td><td>3</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>44.0</td><td>30.56</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>0.3</td><td>9.0</td><td>1.71</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>179.0</td><td>57.35</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>254.0</td><td>54.44</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">15</td><td>3</td><td>3.1</td><td>79.5</td><td>9.60</td><td>0.00</td><td>4/4</td><td>4.1</td><td>64.3</td><td>7.81</td><td>0.00</td><td>4/4</td><td>3.6</td><td>169.8</td><td>39.06</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>7.1</td><td>257.5</td><td>18.44</td><td>0.00</td><td>4/4</td><td>8.2</td><td>228.5</td><td>16.55</td><td>0.00</td><td>4/4</td><td>12.7</td><td>1167.0</td><td>79.70</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>11.2</td><td>984.0</td><td>24.44</td><td>0.00</td><td>4/4</td><td>11.7</td><td>402.8</td><td>19.61</td><td>0.00</td><td>4/4</td><td>35.0</td><td>4718.3</td><td>99.37</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">20</td><td>3</td><td>6.5</td><td>35.8</td><td>6.97</td><td>0.00</td><td>4/4</td><td>8.6</td><td>31.3</td><td>4.50</td><td>0.00</td><td>4/4</td><td>10.9</td><td>282.0</td><td>28.02</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>27.1</td><td>400.0</td><td>14.87</td><td>0.00</td><td>4/4</td><td>35.6</td><td>281.8</td><td>12.81</td><td>0.00</td><td>4/4</td><td>126.1</td><td>4407.3</td><td>63.23</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>58.5</td><td>1416.5</td><td>25.83</td><td>0.00</td><td>4/4</td><td>71.6</td><td>909.8</td><td>25.56</td><td>0.00</td><td>4/4</td><td>423.8</td><td>8267.3</td><td>106.88</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">25</td><td>3</td><td>66.0</td><td>232.3</td><td>9.07</td><td>0.00</td><td>4/4</td><td>85.9</td><td>129.5</td><td>7.49</td><td>0.00</td><td>4/4</td><td>113.2</td><td>665.5</td><td>43.88</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>1139.2</td><td>2262.0</td><td>21.05</td><td>1.95</td><td>3/4</td><td>1151.5</td><td>1087.3</td><td>20.62</td><td>1.79</td><td>3/4</td><td>2638.8</td><td>4751.3</td><td>98.70</td><td>9.33</td><td>3/4</td></tr><tr><td>7</td><td>1871.8</td><td>4762.0</td><td>41.34</td><td>6.26</td><td>3/4</td><td>2072.7</td><td>3158.3</td><td>38.20</td><td>5.06</td><td>3/4</td><td>3600.0</td><td>4154.5</td><td>123.54</td><td>36.46</td><td>0/4</td></tr><tr><td rowspan="3">30</td><td>3</td><td>428.1</td><td>470.5</td><td>13.40</td><td>0.00</td><td>4/4</td><td>516.3</td><td>344.8</td><td>11.69</td><td>0.00</td><td>4/4</td><td>1583.1</td><td>2245.0</td><td>40.92</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>3374.8</td><td>1344.5</td><td>49.30</td><td>14.90</td><td>1/4</td><td>3427.6</td><td>826.3</td><td>36.80</td><td>16.90</td><td>1/4</td><td>3600.0</td><td>390.0</td><td>104.66</td><td>56.87</td><td>0/4</td></tr><tr><td>7</td><td>3600.0</td><td>537.8</td><td>61.12</td><td>36.87</td><td>0/4</td><td>3600.0</td><td>352.3</td><td>61.27</td><td>38.92</td><td>0/4</td><td>3600.0</td><td>279.5</td><td>141.56</td><td>83.76</td><td>0/4</td></tr><tr><td rowspan="3">50</td><td>3</td><td>3600.0</td><td>0.0</td><td>21.95</td><td>21.95</td><td>0/4</td><td>3600.0</td><td>-</td><td>-</td><td>-</td><td>0/4</td><td>3600.0</td><td>16.0</td><td>28.07</td><td>26.61</td><td>0/4</td></tr><tr><td rowspan="3">10</td><td>3</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">15</td><td>3</td><td>0.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>25.8</td><td>3.43</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>3.9</td><td>2102.3</td><td>34.96</td><td>0.00</td><td>4/4</td><td>1.9</td><td>1378.8</td><td>11.45</td><td>0.00</td><td>4/4</td><td>2.1</td><td>1666.0</td><td>13.06</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>17.2</td><td>7612.8</td><td>45.03</td><td>0.00</td><td>4/4</td><td>9.4</td><td>6909.8</td><td>19.43</td><td>0.00</td><td>4/4</td><td>7.4</td><td>6390.5</td><td>16.34</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">20</td><td>3</td><td>4.0</td><td>578.8</td><td>23.21</td><td>0.00</td><td>4/4</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.6</td><td>191.3</td><td>4.02</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>31.0</td><td>6137.3</td><td>38.88</td><td>0.00</td><td>4/4</td><td>11.7</td><td>4324.0</td><td>38.28</td><td>0.00</td><td>4/4</td><td>13.1</td><td>4093.5</td><td>35.74</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>119.3</td><td>16313.3</td><td>40.83</td><td>0.00</td><td>4/4</td><td>70.1</td><td>16715.0</td><td>42.94</td><td>0.00</td><td>4/4</td><td>62.2</td><td>15839.8</td><td>39.72</td><td>0.00</td><td>0/4</td></tr><tr><td rowspan="3">25</td><td>3</td><td>19.6</td><td>1746.0</td><td>33.57</td><td>0.00</td><td>4/4</td><td>13.8</td><td>1617.3</td><td>37.44</td><td>0.00</td><td>4/4</td><td>16.5</td><td>1692.5</td><td>35.42</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>429.4</td><td>27600.3</td><td>45.40</td><td>0.00</td><td>4/4</td><td>248.9</td><td>24697.3</td><td>44.76</td><td>0.00</td><td>4/4</td><td>244.8</td><td>24175.8</td><td>44.97</td><td>0.00</td><td>3/4</td></tr><tr><td>7</td><td>2298.0</td><td>75185.8</td><td>48.33</td><td>3.09</td><td>3/4</td><td>1749.0</td><td>105014.3</td><td>53.17</td><td>1.03</td><td>1/4</td><td>1657.6</td><td>110006.8</td><td>52.54</td><td>0.00</td><td>0/4</td></tr><tr><td rowspan="3">30</td><td>3</td><td>58.5</td><td>3440.8</td><td>46.65</td><td>0.00</td><td>4/4</td><td>47.5</td><td>3754.8</td><td>47.44</td><td>0.00</td><td>4/4</td><td>44.6</td><td>3509.0</td><td>47.96</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>2221.5</td><td>63990.8</td><td>62.09</td><td>0.00</td><td>4/4</td><td>1487.1</td><td>59806.0</td><td>62.49</td><td>0.00</td><td>3/4</td><td>1610.2</td><td>62609.5</td><td>61.52</td><td>0.00</td><td>0/4</td></tr><tr><td>7</td><td>3600.0</td><td>37857.5</td><td>70.68</td><td>24.58</td><td>0/4</td><td>3600.0</td><td>49736.3</td><td>68.69</td><td>23.40</td><td>0/4</td><td>3600.0</td><td>57695.3</td><td>67.27</td><td>20.74</td><td>0/4</td></tr><tr><td rowspan="3">50</td><td>3</td><td>3600.0</td><td>8246.0</td><td>55.31</td><td>32.24</td><td>0/4</td><td>3600.0</td><td>10144.3</td><td>55.78</td><td>27.02</td><td>3/4</td><td>3600.0</td><td>10779.0</td><td>56.17</td><td>25.86</td><td>0/4</td></tr></tbody></table>
<table><caption>Table 3.7: Computational results considering total interdiction and knapsack constraint.</caption><thead><tr><th rowspan="2">Config.</th><th rowspan="2">B</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap<sub>+</sub> (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt/Tot</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap<sub>+</sub> (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt/Tot</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap<sub>+</sub> (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt/Tot</th></tr><tr><th>[MSTI Opt]</th><th>[MSTI V2]</th><th>[MSTI V12]</th><th>[MSTI Dba]</th></tr></thead><tbody><tr><td>10</td><td>0.2</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.3</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>2.5</td><td>3.91</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>6.5</td><td>6.56</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>15</td><td>0.2</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>2.8</td><td>1.42</td><td>0.00</td><td>4/4</td><td>0.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>7.8</td><td>2.95</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.0</td><td>20.0</td><td>7.01</td><td>0.00</td><td>4/4</td><td>1.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.6</td><td>6.8</td><td>2.30</td><td>0.00</td><td>4/4</td><td>1.9</td><td>4.5</td><td>1.73</td><td>0.00</td><td>4/4</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>9.3</td><td>69.5</td><td>29.02</td><td>0.00</td><td>4/4</td><td>10.1</td><td>77.5</td><td>37.34</td><td>0.00</td><td>4/4</td><td>4.8</td><td>17.0</td><td>4.77</td><td>0.00</td><td>4/4</td><td>1.9</td><td>31.5</td><td>15.13</td><td>0.00</td><td>4/4</td></tr><tr><td>20</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.0</td><td>0.5</td><td>0.14</td><td>0.00</td><td>4/4</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.3</td><td>17.5</td><td>4.73</td><td>0.00</td><td>4/4</td><td>2.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.7</td><td>12.5</td><td>4.32</td><td>0.00</td><td>4/4</td><td>5.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>2.9</td><td>0.3</td><td>0.00</td><td>0.00</td><td>4/4</td><td>5.9</td><td>2.5</td><td>0.60</td><td>0.00</td><td>4/4</td><td>3.5</td><td>28.3</td><td>7.46</td><td>0.00</td><td>4/4</td><td>7.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>11.6</td><td>48.5</td><td>4.74</td><td>0.00</td><td>4/4</td><td>13.2</td><td>25.0</td><td>4.75</td><td>0.00</td><td>4/4</td><td>7.8</td><td>5.5</td><td>2.22</td><td>0.00</td><td>4/4</td><td>16.1</td><td>136.3</td><td>31.42</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>76.9</td><td>209.3</td><td>21.27</td><td>0.00</td><td>4/4</td><td>69.6</td><td>114.3</td><td>17.53</td><td>0.00</td><td>4/4</td><td>31.1</td><td>29.5</td><td>12.47</td><td>0.00</td><td>4/4</td><td>14.5</td><td>150.5</td><td>27.66</td><td>0.00</td><td>4/4</td></tr><tr><td>25</td><td>0.2</td><td>2.1</td><td>0.0</td><td>0.00</td><td>4/4</td><td>3.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.2</td><td>2.5</td><td>1.26</td><td>0.00</td><td>4/4</td><td>2.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>2.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>4.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.6</td><td>11.3</td><td>2.37</td><td>0.00</td><td>4/4</td><td>5.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>2.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>5.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.2</td><td>10.3</td><td>3.14</td><td>0.00</td><td>4/4</td><td>21.8</td><td>12.3</td><td>9.93</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>6.4</td><td>6.8</td><td>1.17</td><td>0.00</td><td>4/4</td><td>11.6</td><td>3.3</td><td>0.47</td><td>0.00</td><td>4/4</td><td>5.9</td><td>18.5</td><td>3.77</td><td>0.00</td><td>4/4</td><td>48.6</td><td>89.0</td><td>24.89</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>47.4</td><td>53.8</td><td>3.56</td><td>0.00</td><td>4/4</td><td>50.0</td><td>61.5</td><td>3.94</td><td>0.00</td><td>4/4</td><td>22.1</td><td>26.5</td><td>2.56</td><td>0.00</td><td>4/4</td><td>55.1</td><td>132.8</td><td>20.74</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>318.5</td><td>314.3</td><td>79.22</td><td>0.00</td><td>4/4</td><td>323.3</td><td>195.8</td><td>40.69</td><td>0.00</td><td>4/4</td><td>104.3</td><td>80.0</td><td>5.88</td><td>0.00</td><td>4/4</td><td>89.4</td><td>521.0</td><td>54.71</td><td>0.00</td><td>4/4</td></tr><tr><td>30</td><td>4.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>6.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>4.5</td><td>3.5</td><td>1.96</td><td>0.00</td><td>4/4</td><td>6.0</td><td>1.3</td><td>0.79</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>5.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>7.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>5.5</td><td>28.8</td><td>3.60</td><td>0.00</td><td>4/4</td><td>23.4</td><td>46.0</td><td>17.77</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>7.9</td><td>7.3</td><td>0.69</td><td>0.00</td><td>4/4</td><td>12.4</td><td>3.5</td><td>0.75</td><td>0.00</td><td>4/4</td><td>7.6</td><td>29.5</td><td>5.74</td><td>0.00</td><td>4/4</td><td>100.1</td><td>115.5</td><td>37.11</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>21.6</td><td>6.0</td><td>0.63</td><td>0.00</td><td>4/4</td><td>61.1</td><td>37.8</td><td>5.96</td><td>0.00</td><td>4/4</td><td>19.1</td><td>66.3</td><td>15.62</td><td>0.00</td><td>4/4</td><td>185.2</td><td>283.5</td><td>77.97</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>599.9</td><td>332.5</td><td>15.15</td><td>0.00</td><td>4/4</td><td>649.4</td><td>377.5</td><td>12.89</td><td>0.00</td><td>4/4</td><td>121.4</td><td>77.0</td><td>7.06</td><td>0.00</td><td>4/4</td><td>247.4</td><td>598.3</td><td>80.25</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>3146.5</td><td>379.3</td><td>183.86</td><td>71.58</td><td>4/4</td><td>3004.7</td><td>267.3</td><td>175.73</td><td>77.61</td><td>1/4</td><td>606.1</td><td>114.0</td><td>20.03</td><td>0.00</td><td>4/4</td><td>401.8</td><td>1247.8</td><td>91.62</td><td>0.00</td><td>4/4</td></tr><tr><td>50</td><td>34.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>35.5</td><td>3.5</td><td>0.68</td><td>0.00</td><td>4/4</td><td>33.5</td><td>2.0</td><td>0.46</td><td>0.00</td><td>4/4</td><td>180.0</td><td>16.5</td><td>7.09</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>47.0</td><td>15.8</td><td>0.45</td><td>0.00</td><td>4/4</td><td>48.7</td><td>186.5</td><td>4.00</td><td>0.00</td><td>4/4</td><td>47.4</td><td>162.8</td><td>3.22</td><td>0.00</td><td>4/4</td><td>2027.1</td><td>98.5</td><td>36.98</td><td>12.07</td><td>3/4</td></tr><tr><td>0.6</td><td>160.5</td><td>206.0</td><td>3.21</td><td>0.00</td><td>4/4</td><td>184.9</td><td>733.8</td><td>7.92</td><td>0.00</td><td>4/4</td><td>199.4</td><td>602.5</td><td>5.86</td><td>0.00</td><td>4/4</td><td>3600.0</td><td>13.0</td><td>61.13</td><td>59.70</td><td>0/4</td></tr><tr><td>0.8</td><td>2508.4</td><td>277.5</td><td>3.37</td><td>0.85</td><td>2/4</td><td>3026.9</td><td>835.3</td><td>18.95</td><td>3.27</td><td>1/4</td><td>1340.3</td><td>988.0</td><td>15.41</td><td>0.00</td><td>4/4</td><td>3600.0</td><td>52.5</td><td>78.34</td><td>75.31</td><td>0/4</td></tr><tr><td>10</td><td>0.2</td><td>0.1</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr></tbody></table>
<table><caption>Table 3.7: Computational results considering total interdiction and knapsack constraint. (continued)</caption><thead><tr><th rowspan="2">Config.</th><th rowspan="2">B</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap<sub>r</sub>(%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt/Tot</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th colspan="2">Total Interdiction</th></tr><tr><th>MSTIPDual</th><th>MSTISDual</th><th>MSTITot</th></tr></thead><tbody><tr><td rowspan="10">15</td><td>0.2</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>1.3</td><td>32.3</td><td>4.38</td><td>0.00</td><td>4/4</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>20</td><td>0.2</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>1.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>2.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>2.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.7</td><td>40.0</td><td>2.41</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>6.3</td><td>311.5</td><td>23.84</td><td>0.00</td><td>4/4</td><td>4.3</td><td>54.5</td><td>11.16</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="10">25</td><td>0.2</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>2.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>7.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>9.1</td><td>11.3</td><td>2.13</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>11.9</td><td>45.8</td><td>16.29</td><td>0.00</td><td>4/4</td><td>15.0</td><td>109.0</td><td>31.05</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>23.2</td><td>136.8</td><td>20.07</td><td>0.00</td><td>4/4</td><td>17.4</td><td>104.3</td><td>9.97</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>30.3</td><td>490.3</td><td>40.58</td><td>0.00</td><td>4/4</td><td>26.6</td><td>417.3</td><td>33.06</td><td>0.00</td><td>4/4</td></tr><tr><td>30</td><td>0.2</td><td>3.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>4.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>8.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>8.7</td><td>0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>18.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>22.4</td><td>0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>63.7</td><td>208.8</td><td>21.40</td><td>0.00</td><td>4/4</td><td>62.5</td><td>165.5</td><td>24.04</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>152.2</td><td>616.3</td><td>62.83</td><td>0.00</td><td>4/4</td><td>134.8</td><td>617.8</td><td>53.44</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>209.3</td><td>1238.5</td><td>75.18</td><td>0.00</td><td>4/4</td><td>237.3</td><td>1168.0</td><td>69.92</td><td>0.00</td><td>4/4</td></tr><tr><td>50</td><td>0.2</td><td>202.5</td><td>8.3</td><td>4.09</td><td>0.00</td><td>4/4</td><td>214.9</td><td>11.8</td><td>0.93</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1191.3</td><td>219.8</td><td>30.13</td><td>0.00</td><td>4/4</td><td>946.6</td><td>183.5</td><td>33.77</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>2921.1</td><td>408.0</td><td>66.93</td><td>16.48</td><td>2/4</td><td>2855.5</td><td>477.3</td><td>64.29</td><td>9.51</td><td>3/4</td></tr><tr><td>0.8</td><td>3600.0</td><td>459.0</td><td>80.34</td><td>53.35</td><td>0/4</td><td>3600.0</td><td>664.5</td><td>85.61</td><td>38.96</td><td>0/4</td></tr></tbody></table>
<table><caption>Table 3.8: Computational results considering partial interdiction and knapsack constraint.</caption><thead><tr><th rowspan="2">Config.</th><th rowspan="2">[V]</th><th rowspan="2">B</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap<sub>Top</sub> (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt/Tot</th><th colspan="6">Partial Interdiction</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th rowspan="2">Gap<sub>Top</sub> (%)</th><th rowspan="2">Gap (%)</th><th rowspan="2">Opt/Tot</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap<sub>Top</sub> (%)</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap<sub>Top</sub> (%)</th><th>Gap (%)</th></tr></thead><tbody><tr><td rowspan="6">10</td><td>0.2</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>5.3</td><td>5.04</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>1.8</td><td>1.78</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">15</td><td>0.2</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.4</td><td>2.5</td><td>1.14</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>8.5</td><td>2.93</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>27.3</td><td>8.15</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>1.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">20</td><td>0.2</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.9</td><td>0.8</td><td>0.42</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.2</td><td>16.5</td><td>3.83</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>1.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.4</td><td>10.8</td><td>2.64</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>1.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.6</td><td>2.3</td><td>0.70</td><td>0.00</td><td>4/4</td><td>2.2</td><td>46.8</td><td>6.41</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>2.9</td><td>2.8</td><td>0.76</td><td>0.00</td><td>4/4</td><td>3.1</td><td>11.5</td><td>2.13</td><td>0.00</td><td>4/4</td><td>3.2</td><td>4.8</td><td>0.93</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>4.5</td><td>20.8</td><td>3.29</td><td>0.00</td><td>4/4</td><td>5.2</td><td>9.0</td><td>1.16</td><td>0.00</td><td>4/4</td><td>4.7</td><td>20.8</td><td>3.44</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">25</td><td>0.2</td><td>2.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.5</td><td>3.8</td><td>0.75</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>2.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.1</td><td>6.3</td><td>2.07</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>3.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.4</td><td>11.8</td><td>3.95</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>4.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>6.6</td><td>1.3</td><td>0.30</td><td>0.00</td><td>4/4</td><td>4.0</td><td>53.0</td><td>10.35</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>16.1</td><td>28.0</td><td>2.46</td><td>0.00</td><td>4/4</td><td>15.4</td><td>21.8</td><td>2.10</td><td>0.00</td><td>4/4</td><td>8.8</td><td>2.8</td><td>0.50</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>45.9</td><td>159.3</td><td>7.57</td><td>0.00</td><td>4/4</td><td>39.0</td><td>56.5</td><td>5.02</td><td>0.00</td><td>4/4</td><td>23.9</td><td>68.8</td><td>4.39</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">30</td><td>0.2</td><td>3.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>5.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.0</td><td>4.5</td><td>2.52</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>5.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>6.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.8</td><td>34.3</td><td>3.76</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>6.9</td><td>1.3</td><td>0.27</td><td>0.00</td><td>4/4</td><td>7.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>5.3</td><td>34.0</td><td>4.72</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>14.9</td><td>7.3</td><td>1.41</td><td>0.00</td><td>4/4</td><td>19.0</td><td>15.0</td><td>1.77</td><td>0.00</td><td>4/4</td><td>10.4</td><td>71.3</td><td>6.53</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>88.9</td><td>122.5</td><td>5.93</td><td>0.00</td><td>4/4</td><td>79.6</td><td>104.3</td><td>5.73</td><td>0.00</td><td>4/4</td><td>31.0</td><td>50.3</td><td>4.85</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>282.6</td><td>393.5</td><td>10.60</td><td>0.00</td><td>4/4</td><td>255.8</td><td>277.5</td><td>8.81</td><td>0.00</td><td>4/4</td><td>77.8</td><td>88.8</td><td>6.91</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">50</td><td>0.2</td><td>29.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>30.4</td><td>4.3</td><td>0.68</td><td>0.00</td><td>4/4</td><td>21.0</td><td>11.3</td><td>1.20</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>39.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>40.6</td><td>189.8</td><td>3.18</td><td>0.00</td><td>4/4</td><td>27.7</td><td>153.0</td><td>3.78</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>91.2</td><td>123.8</td><td>3.40</td><td>0.00</td><td>4/4</td><td>103.3</td><td>716.0</td><td>5.75</td><td>0.00</td><td>4/4</td><td>97.0</td><td>879.5</td><td>11.34</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>620.6</td><td>422.5</td><td>7.89</td><td>0.00</td><td>4/4</td><td>941.7</td><td>1845.0</td><td>16.53</td><td>0.00</td><td>4/4</td><td>626.8</td><td>1715.0</td><td>18.88</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>3600.0</td><td>0.0</td><td>12.43</td><td>0.00</td><td>4/4</td><td>3600.0</td><td>0.0</td><td>17.78</td><td>0.00</td><td>4/4</td><td>2304.5</td><td>235.3</td><td>2.60</td><td>1.51</td><td>2/4</td></tr><tr><td rowspan="6">10</td><td>0.2</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.2</td><td>2.8</td><td>0.45</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr></tbody></table>
<table><caption>Table 3.8: Computational results considering partial interdiction and knapsack constraint. (continued)</caption><thead><tr><th rowspan="2">|V|</th><th rowspan="2">B</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th colspan="2">MSTIDBA</th><th rowspan="2">Opt/Tot</th><th rowspan="2">Time (s)</th><th colspan="2">MSTIDBA</th><th rowspan="2">Opt/Tot</th><th rowspan="2">Time (s)</th><th rowspan="2">Nodes</th><th colspan="2">MSTIDBA</th><th rowspan="2">Opt/Tot</th></tr><tr><th>Gap, (%)</th><th>Gap (%)</th><th>Nodes</th><th>Gap, (%)</th><th>Gap (%)</th><th>Nodes</th><th>Gap, (%)</th></tr></thead><tbody><tr><td rowspan="6">15</td><td>0.2</td><td>0.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.5</td><td>1.3</td><td>2.31</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.6</td><td>2.5</td><td>1.35</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.5</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>1.3</td><td>36.0</td><td>4.45</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">20</td><td>0.2</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>1.8</td><td>0.45</td><td>0.00</td><td>4/4</td><td>0.6</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>2.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>0.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>3.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>6.7</td><td>47.3</td><td>8.48</td><td>0.00</td><td>4/4</td><td>1.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>9.4</td><td>205.5</td><td>11.33</td><td>0.00</td><td>4/4</td><td>1.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.9</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">25</td><td>0.2</td><td>2.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>1.8</td><td>3.0</td><td>3.60</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>3.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.2</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>15.9</td><td>11.3</td><td>2.30</td><td>0.00</td><td>4/4</td><td>3.3</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>3.0</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>26.1</td><td>43.0</td><td>9.44</td><td>0.00</td><td>4/4</td><td>8.2</td><td>39.5</td><td>4.69</td><td>0.00</td><td>4/4</td><td>6.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>33.7</td><td>162.5</td><td>18.48</td><td>0.00</td><td>4/4</td><td>11.1</td><td>86.0</td><td>6.19</td><td>0.00</td><td>4/4</td><td>10.7</td><td>119.8</td><td>11.88</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>72.5</td><td>330.5</td><td>24.69</td><td>0.00</td><td>4/4</td><td>15.8</td><td>264.8</td><td>12.32</td><td>0.00</td><td>4/4</td><td>19.0</td><td>301.8</td><td>10.71</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">30</td><td>0.2</td><td>5.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.8</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>2.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>29.4</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>7.1</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>7.1</td><td>0.00</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>85.9</td><td>132.5</td><td>23.37</td><td>0.00</td><td>4/4</td><td>10.7</td><td>0.0</td><td>0.00</td><td>0.00</td><td>4/4</td><td>9.3</td><td>0.00</td><td>0.00</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>136.9</td><td>283.0</td><td>35.39</td><td>0.00</td><td>4/4</td><td>23.5</td><td>98.5</td><td>7.42</td><td>0.00</td><td>4/4</td><td>34.1</td><td>68.0</td><td>2.26</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>183.8</td><td>534.8</td><td>47.19</td><td>0.00</td><td>4/4</td><td>87.1</td><td>373.5</td><td>13.71</td><td>0.00</td><td>4/4</td><td>82.9</td><td>426.0</td><td>22.07</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>239.9</td><td>991.3</td><td>51.81</td><td>0.00</td><td>4/4</td><td>127.4</td><td>898.3</td><td>26.46</td><td>0.00</td><td>4/4</td><td>153.8</td><td>996.8</td><td>27.79</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">50</td><td>0.2</td><td>219.0</td><td>15.8</td><td>6.25</td><td>0.00</td><td>4/4</td><td>219.7</td><td>13.8</td><td>4.10</td><td>0.00</td><td>4/4</td><td>212.2</td><td>7.3</td><td>0.54</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>3153.1</td><td>34.3</td><td>20.21</td><td>12.25</td><td>2/4</td><td>924.1</td><td>116.0</td><td>14.79</td><td>0.00</td><td>4/4</td><td>1139.8</td><td>110.3</td><td>17.03</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>3600.0</td><td>29.3</td><td>33.06</td><td>32.82</td><td>0/4</td><td>2777.1</td><td>501.3</td><td>34.97</td><td>1.85</td><td>3/4</td><td>2711.0</td><td>427.5</td><td>36.86</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>3600.0</td><td>113.5</td><td>44.52</td><td>42.32</td><td>0/4</td><td>3600.0</td><td>845.0</td><td>51.81</td><td>21.61</td><td>0/4</td><td>3337.5</td><td>709.0</td><td>48.64</td><td>11.99</td><td>2/4</td></tr><tr><td>1.0</td><td>3600.0</td><td>21.3</td><td>55.41</td><td>54.97</td><td>0/4</td><td>3600.0</td><td>571.5</td><td>231.90</td><td>36.50</td><td>0/4</td><td>3600.0</td><td>540.0</td><td>229.66</td><td>37.26</td><td>0/4</td></tr></tbody></table>
3.10 Conclusions

In this chapter we presented seven formulations in order to solve the MSTI
problem. The first six formulations, i.e. [MSTI<sub>Opt</sub>], [MSTI<sub>DBa</sub>], [MSTI<sub>Dual</sub>],
[MSTI<sub>SDual</sub>], [MSTI-V<sub>2</sub>] and [MSTI-V<sub>12</sub>], can handle total and partial interdic-
tion as well as both types of budget constraints, cardinality and knapsack. The
seventh formulation, [MSTI<sub>Tot</sub>], is a special model that only considers total in-
terdiction. [MSTI<sub>DBa</sub>] is a model retrieved from the literature. [MSTI<sub>Opt</sub>] is a
formulation based on a linear model of the MST of Martin (1991). Two families
of valid inequalities were developed to strengthen [MSTI<sub>Opt</sub>] and consequently
[MSTI-V<sub>2</sub>] and [MSTI-V<sub>12</sub>] are defined. [MSTI<sub>Dual</sub>] is obtained by computing the
dual of the follower's problem. Similarly, [MSTI<sub>SDual</sub>] is as well obtained by com-
puting the dual of the inner minimization problem but from a compact version
of [MSTI<sub>Opt</sub>]. [MSTI<sub>Tot</sub>] is a special version of [MSTI<sub>Opt</sub>] that only considers to-
tal interdiction and it is only equivalent to the other formulations under specific
parameter settings.

Test instances with networks of different sizes were generated and used to
evaluate the efficiency of the presented formulations. The experiments reported
in Section 3.9 provide varied results. There is no formulation that consistently
outperforms the other in all cases. The next conclusions follow:

*   **Cardinality constraint - Total interdiction.** [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>]
    proved to be the most efficient formulations by optimally solving most of
    the test instances in the shortest computational times. [MSTI<sub>DBa</sub>] ranks
    second; although in several instances it obtained better relative gaps and
    a smaller number of explored Branch-and-Bound nodes, the computation
    times are significantly large. In addition, [MSTI<sub>DBa</sub>] failed to solve some
    instances less than [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] when the budget increased.
    [MSTI<sub>Opt</sub>], [MSTI-V<sub>2</sub>], [MSTI-V<sub>12</sub>] and [MSTI<sub>Tot</sub>] become fairly inefficient
    starting on networks of 25 nodes. Furthermore, instances are unsolvable on
    graphs of size 50 or more with a budget greater than or equal to 5.

* **Cardinality constraint - Partial interdiction.** Similar conclusions as in the previous bullet point. [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] report the best results. However, [MSTI<sub>SDual</sub>] obtained slightly better resolution times and
it solved one more instance than [MSTI<sub>Dual</sub>]. [MSTI<sub>DBa</sub>] occasionally con-
tinues to report slightly better relative gaps and smaller number of explored
nodes but with a higher computational time. None of the formulations is
capable of solving instances of 50 nodes, thus marking their limits in this
case.

*   **Knapsack constraint - Total interdiction.** [MSTI<sub>Tot</sub>] is the most efficient formulation. Each instance is solved and most of them were solved at root node. [MSTI-V<sub>12</sub>] takes the second over [MSTI<sub>Opt</sub>] since the former obtain similar or better resolution times than the latter and it solved all instances. The roles of [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>] were reversed since in this case they did not report the best results. However, instances of 10 to 30 nodes are optimally solved in less than 240 seconds by these two formulations. Their results decay on the networks of largest size with largest budgets. [MSTI<sub>DBa</sub>] becomes the most inefficient model in this case.

*   **Knapsack constraint - Partial interdiction.** [MSTI<sub>Opt</sub>] and [MSTI-V<sub>12</sub>] becomes the most efficient models by solving every instance in similar times. [MSTI-V<sub>12</sub>] is able to solve slightly larger instances than [MSTI<sub>Opt</sub>]. [MSTI<sub>SDual</sub>] ranks second and [MSTI<sub>Dual</sub>] third. [MSTI<sub>DBa</sub>] once again becomes the most inefficient model since it obtains the worst computational times and gaps.

Several formulations for the MSTI problem based on different MST models
are proposed. These formulations are conceived to handle the various assump-
tions with respect to the types of interdiction and types of budget constraints.
Computational experiments showed that at least one of our proposed formula-
tions is efficient in networks of small and medium size for all four different cases.
Experiments imply that larger networks are impossible to solve by means of the
presented formulations. Therefore, different approaches other than pure mathe-
matical models are proposed in the next chapters.
3. FORMULATIONS FOR THE MSTI PROBLEM
# Chapter 4

## A Branch-and-Price Algorithm for the MSTI Problem

The numerical experiments reported in the previous chapter indicate the need to design specific resolution methods. The computational time required by our formulations of the MSTI problem grows considerably as the size of the network increases.

One reason is the number of variables present in the models, for instance only variables $x_e$ grow at a rate of ($|V|^2 - |V|$/2 for complete graphs. Branch-and-Price (B&P) algorithm is a well-known method that can address models with a large number of variables. In this chapter, we develop a B&P algorithm based on the [MSTI<sub>SDual</sub>] formulation, (3.9), in order to work with a much smaller number of variables and hopefully diminish the resolution time. The algorithm starts by reformulating [MSTI<sub>SDual</sub>] via a Dantzig-Wolfe decomposition. Then the Master Problem (MP) is defined by relaxing the integrality of the latter reformulation. The MP has as many variables as the original model. Therefore, a more compact formulation that only considers a fraction of the variables (columns), named the Restricted Master Problem (RMP), is defined. This model is in turn solved by a column generation procedure embedded in a Branch-and-Bound scheme in order to recover integrality. In Section 4.1, we detail the decomposition of [MSTI<sub>SDual</sub>] and the definition of the RMP. The pricing problem and the B&P algorithm for the MSTI problem are presented in Section 4.2. The chapter ends with computational experiments in Section 4.3, assuming all types of interdictions and budget constraints, and followed by conclusions in Section 4.4.
## 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

### 4.1 Dantzig-Wolfe Decomposition

In this section, the Dantzig-Wolfe decomposition is presented on formulation (3.9). Even though $[MSTI_{SDual}]$ did not outperform all other models, it was chosen to be used in the B&P algorithm since it is the most compact formulation. Let $\mathcal{X}$ be the set of interdiction strategies defined as $\{\mathbf{x} \in \{0, 1\}^{|\mathcal{E}|} | \sum_{e \in \mathcal{E}} b_e x_e \le B\}$. $[MSTI_{SDual}]$ can be expressed in its *compact* form as:

$$ [MSTI_{SDual}] \max_{\mathbf{x},\beta,\sigma,\tau} \beta(n-1) - \sum_{k \in \mathcal{V}} \sum_{m \in \mathcal{V}, m \neq k} \tau_{km} \quad (4.1a) $$

s.t.

$$ \beta + \sum_{k \in \mathcal{V} \setminus \{m,h\}} \sigma_{ke} - \tau_{hm} - \tau_{mh} \le c_e + d_e x_e \quad \forall e = \{m,h\} \in \mathcal{E} \quad (4.1b) $$

$$ \sigma_{ke} + \tau_{km} \ge 0 \qquad \forall k, m \in \mathcal{V}, e = \{m, j\} \in \mathcal{E} \setminus \mathcal{E}^k \quad (4.1c) $$

$$ \tau_{km} \ge 0 \qquad \forall k, m \in \mathcal{V}, m \neq k \quad (4.1d) $$

$$ \beta, \sigma_{ke} = \textit{unrestricted} \qquad \forall k \in \mathcal{V}, \forall e \in \mathcal{E} \quad (4.1e) $$

$$ x \in \mathcal{X} \qquad (4.1f) $$

Let $\text{conv}(\mathcal{X})$ represent the convex hull of $\mathcal{X}$. Due to the Weyl-Minkowski theorem (Schrijver (1998)), a point of $\mathcal{X}$ can be written as a convex combination of the extreme points in $\text{conv}(\mathcal{X})$. Each point of $\text{conv}(\mathcal{X})$ corresponds to an interdiction plan. The number of extreme points is finite since there is only a finite number of interdiction strategies. Therefore, any interdiction plan can be expressed as a convex combination of interdiction plans. Let $\mathcal{P}$ be the set of extreme points. The constraints that define the convex combination of interdiction strategies are the following:

$$ \mathbf{x} = \sum_{p \in \mathcal{P}} \lambda_p \mathbf{x}_p \quad (4.2a) $$

$$ \sum_{p \in \mathcal{P}} \lambda_p = 1 \quad (4.2b) $$

$$ \lambda_p \ge 0 \qquad \forall p \in \mathcal{P} \quad (4.2c) $$
The non-negative weights of each interdiction plan $\mathbf{x}_p$ in the convexity constraint (4.2a) are represented by $\lambda_p$. The meaning of each $\lambda_p$ is the proportion of strategy $\mathbf{x}_p$ to obtain $\mathbf{x}$. The component-wise version of (4.2a) is $x_e = \sum_{p \in \mathcal{P}} x_{pe} \lambda_p$ for all $p \in \mathcal{P}$ where $x_{pe}$ is equal to 1 if the edge $e$ is interdicted in the interdiction strategy $p$, and 0 otherwise. Then, the next extended formulation is obtained by using expression (4.2a) to substitute $x_e$ in model (4.1) and by adding constraints (4.2b)-(4.2c).

$$ [\text{Ext-MSTI}_{\text{SDual}}] \max_{\mathbf{x},\beta,\sigma,\tau,\lambda} \beta(n-1) - \sum_{k \in \mathcal{V}} \sum_{\substack{m \in \mathcal{V} \\ m \neq k}} \tau_{km} \quad (4.3a) $$

s.t.

$$ \beta + \sum_{k \in \mathcal{V} \setminus \{m,h\}} \sigma_{ke} - \tau_{hm} - \tau_{mh} \le c_e + \sum_{p \in \mathcal{P}} (d_e x_{pe}) \lambda_p \quad : \{\pi_{mh}^1\} \quad \forall e = \{m,h\} \in \mathcal{E} \quad (4.3b) $$

$$ \sigma_{ke} + \tau_{km} \ge 0 \qquad \forall k, m \in \mathcal{V}, e = \{m, j\} \in \mathcal{E} \setminus \mathcal{E}^k \quad (4.3c) $$

$$ \sum_{p \in \mathcal{P}} \lambda_p = 1 \qquad : \{\pi^0\} \quad (4.3d) $$

$$ x_e = \sum_{p \in \mathcal{P}} x_{pe} \lambda_p \qquad \forall e \in \mathcal{E} \quad (4.3e) $$

$$ \lambda_p, \tau_{km} \ge 0, \qquad \forall p \in \mathcal{P}, \forall k, m \in \mathcal{V}, m \neq k \quad (4.3f) $$

$$ \beta, \sigma_{ke} = \text{unrestricted} \qquad \forall k \in \mathcal{V}, \forall e \in \mathcal{E} \quad (4.3g) $$

$$ x_e \in \{0,1\} \qquad \forall e \in \mathcal{E} \quad (4.3h) $$

$[\text{Ext-MSTI}_{\text{SDual}}]$ contains a quadratic number of variables. Thus solving (4.3) with all the variables is computationally burdensome. Therefore, only a subset of variables is considered and the others are generated via a column generation procedure. We begin by considering the linear relaxation of (4.3) by removing (4.3h). The integrality of variables $x_e$ and (4.3d) impose to have only one variable $\lambda_p$ to be one. Since (4.3h) is removed, several variables $\lambda_p$ may take positive values simultaneously. Additionally, parameters $x_{pe} \in \{0,1\}$ and $0 \le \lambda_p \le 1$, for all $p \in \mathcal{P}$, due to (4.3d) and (4.3f). Thus, $0 \le \sum_{p \in \mathcal{P}} x_{pe} \lambda_p \le 1$. Constraint (4.3e) is dropped since it is implicit in the formulation when the integrality of $x_e$ is relaxed. The resulting formulation defined by (4.3a)-(4.3d), (4.3f) and (4.3g) is denoted as the master problem MP$[\mathcal{P}]$.
# 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

Let $\hat{\mathcal{P}} \subseteq \mathcal{P}$ be a sub-set of interdiction strategies. We call Restricted Master Problem defined over $\hat{\mathcal{P}}$, indicated by $[\text{RMP}(\hat{\mathcal{P}})]$, the problem defined by (4.3a)-(4.3d), (4.3f) and (4.3g). A column generation procedure is an iterative algorithm where the RMP and the pricing problem (or sub-problem) are solved sequentially and iteratively. The pricing problem identifies columns, which are in fact the extreme points of $\text{conv}(\mathcal{X})$, with a positive reduced cost. These columns are added to $[\text{RMP}(\hat{\mathcal{P}})]$ and then the problem is re-optimized. The pricing problem is presented in the following section.

We develop a Branch-and-Bound algorithm, where the column generation procedure is performed at each node of the search tree, to obtain an integer solution that can then be converted to a solution of an instance of the MSTI problem. This framework is known as a B&P algorithm since variables are prized in the course of the algorithm. The overall framework is presented in detail in the next section.

## 4.2 B&P Algorithm

In this section, we detail the B&P algorithm developed to solve the MSTI problem. The main idea is to design a classical Branch-and-Bound algorithm that solves at each node of the search tree the $[\text{RMP}(\hat{\mathcal{P}})]$ by a column generation procedure. In the following sections, we describe the details of the different components of our algorithms.

### 4.2.1 Branching

The branching strategy chosen for the B&P algorithm is the traditional strategy. It consists in selecting the edge whose value is the closest to 0.5. Then, a binary branching is imposed on this edge. Since the $[\text{RMP}(\hat{\mathcal{P}})]$ no longer has variables $x_e$ to branch on, the branching is translated to use variables $\lambda_p$. Let $\hat{\mathcal{E}}_1, \hat{\mathcal{E}}_0 \subset \mathcal{E}$ be the sets of edges where a branching strategy is to be imposed at a given node, i.e. $x_e = 1$ for all $e \in \hat{\mathcal{E}}_1$ and $x_e = 0$ for all $e \in \hat{\mathcal{E}}_0$. The following constraints are thus defined:
$$ \sum_{p \in \hat{\mathcal{P}}} x_{pe} \lambda_p \begin{cases} \ge 1, & \text{if } x_e = 1 \quad \forall e \in \hat{\mathcal{E}}_1 \\ \le 0, & \text{if } x_e = 0 \quad \forall e \in \hat{\mathcal{E}}_0 \end{cases} : \{\pi_e^2\} \quad (4.4) $$

If an edge $e \in \hat{\mathcal{E}}_1$ is to be part of the final solution, only interdiction plans containing $e$ must be selected. Therefore, the sum of variables $\lambda_p$ that represent these interdiction strategies are set to be greater or equal to one. For the edges in $\hat{\mathcal{E}}_0$, they are set to zero.

The classical Branch-and-Bound stopping conditions for branching are considered in our algorithm. Those are: the solution at the node is integer, the solution at the node is infeasible or the upper bound of the node is lower than the lower bound. In addition, one more condition is defined to fathom nodes in an early stage. If $b_e > B - \sum_{e \in \hat{\mathcal{E}}_1} b_e$, for all $e \in \mathcal{E} \setminus \hat{\mathcal{E}}_1 \cup \hat{\mathcal{E}}_0$, then the node is fathomed. That is, the interdiction costs of the edges not yet considered for branching are greater than the remaining budget.

### 4.2.2 Pricing Problem

The pricing problem is defined by using the dual variables with respect to constraints involving $\lambda_p$, i.e. the convexity constraint, (4.3b) and the branching constraints (4.4). The dual variables corresponding to these constraints are given in (4.3) and (4.4). The pricing problem used to identify columns with a positive reduced cost turns out to be a knapsack problem with a modified objective function. The sub-problem is defined as follows:

$$ \bar{c}(\hat{\mathbf{x}}) = \max \sum_{e=\{m,h\} \in \mathcal{E}} d_e \pi_{mh}^1 \hat{x}_e - \sum_{e \in \hat{\mathcal{E}}_1} \pi_e^2 \hat{x}_e - \pi^0 \quad (4.5a) $$

$$ \sum_{e \in \mathcal{E}} b_e \hat{x}_e \le B \quad (4.5b) $$

$$ \hat{x}_e = 1 \quad \forall e \in \hat{\mathcal{E}}_1 \quad (4.5c) $$

$$ \sum_{e \in \hat{\mathcal{E}}_0} \hat{x}_e = 0 \quad (4.5d) $$

$$ \hat{x}_e \in \{0, 1\} \quad \forall e \in \mathcal{E} \quad (4.5e) $$
## 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

The optimal solution of (4.5) is an interdiction plan that meets the budget constraint (4.5b) and the branching strategies of the node given by (4.5c) and (4.5d). A column $\hat{\mathbf{x}}$ is added to $\hat{\mathcal{P}}$ when $\bar{c}(\hat{\mathbf{x}}) > 0$. Afterwards, $[\mathrm{RMP}(\hat{\mathcal{P}})]$ is re-optimized considering the new column respect to $\hat{\mathbf{x}}$. This process is repeated until the optimal solution of the pricing problem does not generate an interdiction strategy with a positive reduced cost, that is $\bar{c}(\hat{\mathbf{x}}) \le 0$. Thus, all relevant columns were found and the iterative procedure ends.

### 4.2.2.1 Strengthening of the Pricing Problem

The reduction of the network by means of the $\bar{B}$-edge connected certificate of $\mathcal{G}$, as shown in Section 3.8, gives rise to a family of constraints that can be used to strengthen the pricing problem (4.5). The graph $\mathcal{G}_{\bar{B}} = \cup_{i=0}^{i} T_i$ where $T_0$ is the MST of $\mathcal{G}$ and $T_i$ the MST of $\mathcal{G}_i = \mathcal{G} \setminus \cup_{j=0}^{i-1} T_j$ represents the $\bar{B}$-edge connected certificate of $\mathcal{G}$. The equivalence of solving the MSTI problem in $\mathcal{G}$ and $\mathcal{G}_{\bar{B}}$ was proved in Chapter 3. In addition, the reduction of $\mathcal{G}$ is valid for both interdiction constraints where $\bar{B} = B$ in the cardinality case and $\bar{B} = \max\{\sum_{e \in \mathcal{E}} x_e : \sum_{e \in \mathcal{E}} b_e x_e \le B\}$ for the knapsack case. The following lemma is given.

**Lemma 4.1.** Let $\mathcal{S}$ be an edge set whose elements are partially interdicted. Let $\mathcal{S}_a = \mathcal{S} \setminus \cup_{j=0}^{i-1} T_j$. If $e \in T_i$, then the replacement edge of $e$, i.e. an edge $e'$ such that $T_i \setminus \{e\} \cup \{e'\}$ forms a tree and the increment in its weight is minimal, belongs to $T_{i+1} \cup \mathcal{S}_a \cup \{e\}$.

*Proof.* Assuming total interdiction, the work of Bazgan et al. (2012) proves that the replacement edge of $e$ belongs to $T_{i+1}$.

If partial interdiction is assumed, edge $e$ is still part of the graph. It might be that $c_e < c_{e'}$ where $e'$ is the edge with the smallest weight of $T_{i+1}$ that connects the two connected components induced by removing $e$ from $T_i$. Analogously, such edge $e'$ can belong to $\mathcal{S}_a$. Thus, the replacement edge of $e$ is found in the set $T_{i+1} \cup \mathcal{S}_a \cup \{e\}$. $\square$

In Bazgan et al. (2012), a sequential procedure embedded in a construction of a search tree and based in Lemma 4.1 is proposed for the MSTI problem considering total interdiction and cardinality constraint. The sequential procedure consists in $\bar{B}$ iterations. At each iteration, one edge of $T_0$ is interdicted and replaced by