one edge of $T_1$, the edge removed from $T_1$ that was added to $T_0$ is now replaced for one edge of $T_2$, and so on. At the end of $\bar{B}$ iterations, $\bar{B}$ edges are interdicted. The authors proved that the optimal solution of the MSTI problem has the same structure given by the latter algorithm, i.e. the solution can be constructed by $\bar{B}$ iterative interdictions and replacements.

The particular structure of the procedure above gives rise to next family of valid inequalities of the MSTI problem.

$$ \sum_{e \in T_i} x_e \leq \bar{B} - i \qquad \forall i = 0, 1, \dots, \bar{B} \qquad (4.6) $$

Constraints (4.6) give an upper bound on the number of edges that can be interdicted for each $T_i$, $0 \le i \le \bar{B}$. Note that at each step of the sequential algorithm, an edge of $T_i$ is replaced by one in $T_{i+1}$. That is, edges of the "lower" trees are climbing up to $T_0$. A total of $\bar{B}$ edges in $T_0$ can be interdicted. For $T_1$, we can interdict at most $\bar{B} - 1$ since at least one edge in $T_0$ must be interdicted otherwise, the follower will chose $T_0$ as his optimal response to the leader's interdiction strategy. Analogously, in any optimal interdiction strategy at most $\bar{B} - 2$ edges in $T_2$ can be interdicted since at least one edge in $T_0$ and one in $T_1$ need to be interdicted by the leader. Thus, the pricing problem, denoted by [Pr], is defined by (4.5) and the family of constraints (4.6).

### 4.2.2.2 Heuristic for the Pricing Problem

The first idea to solve the pricing problem, i.e. (4.5) and (4.6) was through a commercial solver. However, preliminary experimentation showed that this approach was time consuming. Therefore, a simple heuristic is developed. The problem defined by (4.5a), (4.5b), (4.5e) and (4.6) is what is known in the literature as the 0-1 multidimensional knapsack problem. Therefore, we base our heuristic on the one proposed in Akçay et al. (2007).

Let $Q \in \mathbb{R}^{|\mathcal{E}|}$ be the vector of coefficients of $x_e$ by developing the summations in objective function (4.5a). Let $\bar{B}_{\bar{B}-i} = \bar{B} - i$ for $i = 0, 1, \dots, \bar{B}$. Parameters $\bar{B}_{\bar{B}-i}$ are called tree budgets and represent the right-hand sides of constraints (4.6). Let $\bar{c}(\hat{\mathbf{x}})$ be the objective value of [Pr] for the interdiction plan $\hat{\mathbf{x}}$. The heuristic consists in constructing an interdiction plan by adding the edge with
## 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

the largest $Q_e$ to the solution one at a time. Each time an edge $e$ is added to the interdiction strategy, the budget is reduced by the interdiction cost of the edge, i.e. $B - b_e$, and its corresponding tree budget is reduced by one. In addition, $\bar{c}(\hat{\mathbf{x}})$ is increased by $Q_e$.

The heuristic is divided into four main phases. First, the edges in $\mathcal{E}_1$ imposed by the branching strategy are added to the solution; their respective $Q_e$ values are added to $\bar{c}(\hat{\mathbf{x}})$ as well as the budget and the tree budgets are correspondingly modified. The second phase forbids the interdiction of edges in $\mathcal{E}_0$. Thirdly, the edges that cannot be interdicted due to the violation of any constraints are pruned. The last phase selects one of the remaining edges with the largest $Q_e$ coefficient, the edge is added to the interdiction plan and the reduced cost and the budgets are modified. The algorithm iterates between phases three and four until no more edges can be selected.

The pseudo-code of the heuristic for [Pr] is presented in Algorithm 1. Step 1 initialize $\bar{c}(\hat{\mathbf{x}})$ to constant $\pi^0$, the interdiction plan $\hat{\mathbf{x}}$ to the empty strategy and vector $\mathbf{Q}$ to the zero vector. Step 2 computes coefficient $d_e\pi_{mh}^1$ for each edge and saves it in $Q_e$. Steps 3 to 10 correspond to phase one described above; when an edge is added to the solution is then removed from the edge set $\mathcal{E}$ in Step 9. Phase two is carried out in Step 11 to 13 and the edges of $\mathcal{E}_0$ are removed from $\mathcal{E}$. The loop between phases three and four start in Step 14 where the third phase related to edge pruning goes from Step 15 to 20 and the fourth phase from Step 24 to 29. The termination condition in Step 21 ends the loop where all edges have been eliminated from the edge set. Finally, the algorithms returns a feasible interdiction plan $\hat{\mathbf{x}}$ with reduced cost $\bar{c}(\hat{\mathbf{x}})$.

The heuristic presented in Algorithm 1 might not always provide the optimal solution. To ensure the correctness of the B&P algorithm, [Pr] is solved by a commercial solver only when Algorithm 1 does not provide columns with positive reduced costs. If a column with a positive reduced cost is identified, it is added to $\hat{\mathcal{P}}$ and the MP is re-optimized. Otherwise, the node is considered to be completely solved and the B&P algorithm continues.

### 4.2.3 Lower Bound

The computation of the lower bound for the MSTI problem differs what is usually implemented in the literature. Each interdiction plan $\hat{\mathbf{x}}$ found by [Pr] defines
**Algorithm 1** Heuristic for the Pricing Problem

**Ensure:** An interdiction plan $\hat{\mathbf{x}}$ with reduced cost $\bar{c}(\hat{\mathbf{x}})$

1: $\bar{c}(\hat{\mathbf{x}}) \leftarrow \pi^0$, $\hat{\mathbf{x}} \leftarrow 0$, $\mathbf{Q} \leftarrow 0$

2: $Q_e \leftarrow d_e \pi_{mh}^1$ for all $e \in \mathcal{E}$

3: **for** $e \in \hat{\mathcal{E}}_1$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $Q_e \leftarrow Q_e - \pi_e^2$

5: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}_e \leftarrow 1$

6: &nbsp;&nbsp;&nbsp;&nbsp; $B \leftarrow B - b_e$

7: &nbsp;&nbsp;&nbsp;&nbsp; $B_{\bar{B}-i} \leftarrow B_{\bar{B}-i} - 1$ where $i \in \{0, 1, \dots, \bar{B}\}$ such that $e \in T_i$

8: &nbsp;&nbsp;&nbsp;&nbsp; $\bar{c}(\hat{\mathbf{x}}) \leftarrow \bar{c}(\hat{\mathbf{x}}) + Q_e$

9: &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{E} \leftarrow \mathcal{E} \setminus \{e\}$

10: **end for**

11: **for** $e \in \hat{\mathcal{E}}_0$ **do**

12: &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{E} \leftarrow \mathcal{E} \setminus \{e\}$

13: **end for**

14: **while** $\mathcal{E} \neq \emptyset$ **do**

15: &nbsp;&nbsp;&nbsp;&nbsp; **for** $e \in \mathcal{E}$ **do**

16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Let $i \in \{0, 1, \dots, \bar{B}\}$ such that $e \in T_i$

17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $B < b_e \lor B_{\bar{B}-i} = 0$ **then**

18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{E} \leftarrow \mathcal{E} \setminus \{e\}$

19: **end if**

20: **end for**

21: **if** $\mathcal{E} = \emptyset$ **then**

22: Go to 31

23: **end if**

24: Let $e^* \in \mathcal{E}$ be the edge with the largest $Q_e$

25: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}_{e^*} \leftarrow 1$

26: &nbsp;&nbsp;&nbsp;&nbsp; $B \leftarrow B - b_{e^*}$

27: &nbsp;&nbsp;&nbsp;&nbsp; $B_{\bar{B}-i} \leftarrow B_{\bar{B}-i} - 1$ where $i \in \{0, 1, \dots, \bar{B}\}$ such that $e^* \in T_i$

28: &nbsp;&nbsp;&nbsp;&nbsp; $\bar{c}(\hat{\mathbf{x}}) \leftarrow \bar{c}(\hat{\mathbf{x}}) + Q_{e^*}$

29: &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{E} \leftarrow \mathcal{E} \setminus \{e^*\}$

30: **end while**

31: Return $\hat{\mathbf{x}}$ and $\bar{c}(\hat{\mathbf{x}})$
## 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

a feasible interdiction plan for the MSTI problem since the only feasibility constraints of the interdictor's problem are the budget and integrality constrains. Therefore, the MST with respect to each $\hat{\mathbf{x}}$ can be computed on graph $G_{\hat{\mathbf{x}}}$ where the weight of each edge is $c_e+d_e\hat{x}_e$. Each MST computed in this manner provides a valid lower bound for the MSTI problem.

In a classical Branch-and-Bound algorithm, when an integer solution is found at any given node, the objective value of this solution is compared to the current best lower bound. If it has a greater value, the current lower bound is replaced by this solution. An integer solution of $[MP(\mathcal{T})]$ has only one variable $\lambda_{p*}$ positive and the remaining ones are zero. In other words, the interdiction plan represented by $p^*$ is selected among all others in $\hat{\mathcal{P}}$ as optimal plan. This means that the interdiction plan that gives the best lower bound was generated at some iteration before the algorithm selects this strategy as an optimal (global or local) integer solution. What we proposed is to compute the MST with respect to $\hat{\mathbf{x}}$, as stated above, for all columns generated by the pricing problem during the resolution of a given node. The latter leads to identify the best lower bound even when no integer solution has been found.

### 4.2.4 Overall presentation of the algorithm

Let $\mathcal{ST}$ and $n_i, i \in \mathbb{N}$, represent the set of nodes and a node of the search tree, respectively. For any set of edges $\mathcal{E}'$, let $w(\mathcal{E}') = \sum_{e \in \mathcal{E}'} c_e$. Given an interdiction plan $\hat{\mathbf{x}}$, the reaction of the follower to the interdiction, i.e. the MST of the augmented graph $G_{\hat{\mathbf{x}}}$ where the weight of each edge is $c_e + d_e\hat{x}_e$, is denoted by $T(\hat{\mathbf{x}})$. Algorithm 2 describes the B&P algorithm developed to solve the MSTI problem.

Algorithm 2 defines a column generation procedure embedded in a Branch-and-Bound algorithm with all components presented in previous sections. The B&P algorithm ends when all nodes have been explored or the time limit is reached, ensured in Step 3. Node selection in Step 4 can be done in different ways. In the computation experiments, we explore the search tree using the best first strategy. In the best first strategy, the most promising node is selected as the first to be explored, that is the node with the best upper bound. Step 5 fathoms nodes that have an upper bound smaller than the lower bound.
<caption>**Algorithm 2 Branch-and-Price Algorithm (Part 1)**</caption>

**Require:** An interdiction plan $\mathbf{x}^*$ with its corresponding MST $\mathbf{y}^*$
1: Define $n_0$ as the root node
2: $\mathcal{S}\mathcal{T} \leftarrow \{n_0\}$, $\hat{\mathcal{P}} \leftarrow \{0\}$, $\underline{u} \leftarrow -\infty$, $\bar{c}(\hat{\mathbf{x}}) \leftarrow \infty$, $k \leftarrow 0$ $j \leftarrow 0$
3: **while** $\mathcal{S}\mathcal{T} \neq \emptyset \lor \text{Time limit is not reached}$ **do**
4: &nbsp;&nbsp;&nbsp;Select $n_i \in \mathcal{S}\mathcal{T}$
5: &nbsp;&nbsp;&nbsp;**if** $\underline{u} < \bar{u}_i$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Re)Define branching constraints (4.4) of $n_i$
7: &nbsp;&nbsp;&nbsp;**while** $\bar{c}(\hat{\mathbf{x}}) > 0$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Solve $[\text{RMP}(\hat{\mathcal{P}})]$ with objective $v$
9: &nbsp;&nbsp;&nbsp;$\bar{u}_i \leftarrow v$
10: &nbsp;&nbsp;&nbsp;Retrieve $\pi^0$, $\pi_{mh}^1$ and $\pi_e^2$ and define $[\text{Pr}]$
11: &nbsp;&nbsp;&nbsp;Solve $[\text{Pr}]$ with Algorithm 1 and obtain solution $\hat{\mathbf{x}}$ with reduced cost $\bar{c}(\hat{\mathbf{x}})$
12: &nbsp;&nbsp;&nbsp;**if** $(\bar{c}(\hat{\mathbf{x}}) < 0) \lor (\lfloor \bar{u}_i \rfloor = \lfloor \bar{u}_i + \bar{c}(\hat{\mathbf{x}}) \rfloor) \lor (\bar{u}_i + \bar{c}(\hat{\mathbf{x}}) \le \underline{u})$ **then**
13: &nbsp;&nbsp;&nbsp;Solve $[\text{Pr}]$ with exact method and obtain solution $\hat{\mathbf{x}}$ with reduced cost $\bar{c}(\hat{\mathbf{x}})$
14: &nbsp;&nbsp;&nbsp;**if** $(\bar{c}(\hat{\mathbf{x}}) < 0) \lor (\lfloor \bar{u}_i \rfloor = \lfloor \bar{u}_i + \bar{c}(\hat{\mathbf{x}}) \rfloor) \lor (\bar{u}_i + \bar{c}(\hat{\mathbf{x}}) \le \underline{u})$ **then**
15: &nbsp;&nbsp;&nbsp;Go to 21
16: &nbsp;&nbsp;&nbsp;**end if**
17: &nbsp;&nbsp;&nbsp;**end if**
18: &nbsp;&nbsp;&nbsp;Add variable $\lambda_p$ corresponding to $\hat{\mathbf{x}}$ to $[\text{RMP}(\hat{\mathcal{P}})]$
19: &nbsp;&nbsp;&nbsp;$\hat{\mathcal{P}} \leftarrow \hat{\mathcal{P}} \cup \{\hat{\mathbf{x}}\}$
20: &nbsp;&nbsp;&nbsp;**end while**
21: &nbsp;&nbsp;&nbsp;**for** $\hat{\mathbf{x}}_{p_j} \in \hat{\mathcal{P}}$ **do**
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate $T(\hat{\mathbf{x}}_{p_j})$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $w(T(\hat{\mathbf{x}}_{p_j})) > \underline{u}$ **then**
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\underline{u} \leftarrow w(T(\hat{\mathbf{x}}_{p_j}))$
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**x**$^* \leftarrow \hat{x}_{p_j}$
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**y**$^* \leftarrow T(\hat{x}_{p_j})$
27: &nbsp;&nbsp;&nbsp;**end if**
28: &nbsp;&nbsp;&nbsp;$j \leftarrow j + 1$
29: &nbsp;&nbsp;&nbsp;**end for**
## 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

<caption>**Algorithm 2 Branch-and-Price Algorithm (Part 2)**</caption>

30: **if** ($\lambda \notin \{0, 1\}^{|\hat{\mathcal{P}}|}$) ∧ ($\underline{u} < \bar{u}_i$) ∧ ($\sum_{e \in \hat{\mathcal{E}}_1} b_e < B$) ∧ ($\exists e \in \mathcal{E} \setminus \hat{\mathcal{E}}_1 \cup \hat{\mathcal{E}}_0 : b_e \le B - \sum_{e \in \hat{\mathcal{E}}_1} b_e$) **then**
31: &nbsp;&nbsp;&nbsp;&nbsp;Select an edge $e'$ to branch
32: &nbsp;&nbsp;&nbsp;&nbsp;Define $n_{k+1}$ with $x_{e'} = 1$ and $n_{k+2}$ with $x_{e'} = 0$
33: &nbsp;&nbsp;&nbsp;&nbsp;ST ← ST ∪ {$n_{k+1}$} ∪ {$n_{k+2}$}
34: &nbsp;&nbsp;&nbsp;&nbsp;k ← k + 2
35: **end if**
36: ST ← ST \ {$n_i$}
37: **else**
38: ST ← ST \ {$n_i$}
39: **end if**
40: **end while**
41: **Return** $x^*$ and $y^*$

Steps 6 to 36 represent the resolution and branching on a node. First, the RMP is adapted to meet the branching conditions of the given node in Step 6. The column generation procedure starts in Step 7. Basically, $[\text{RMP}(\hat{\mathcal{P}})]$ is solved considering the restricted set of interdiction strategies $\hat{\mathcal{P}}$. The value of the dual variables with respect to the constraints involving $\lambda_p$ are retrieved and used to define the pricing problem in Step 11. The pricing problem is solved by the heuristic described in Algorithm 1. If a column with a positive reduced cost is found, it is added to $[\text{RMP}(\hat{\mathcal{P}})]$ and set $\hat{\mathcal{P}}$ is updated. Otherwise, a column with a positive reduced cost is tried to be obtained by a commercial solver, if it fails the column generation ends. The column generation procedure has other termination conditions apart from not finding solutions of the pricing problem with positive reduced costs. These termination conditions are listed below:

1. A negative reduced cost is obtained by the pricing problem.

2. The sum of the upper bound of the node and the positive reduced cost of the solution given by the [Pr] is lower than or equal to the global lower bound.

3. The reduced cost of the column is not large enough to allow the upper bound of the node to increase to the next unit. This is, the sum of the upper bound and the reduced cost is not larger than the floor of the upper bound.
bound. This is only applied if the coefficients and right-hand sides of (4.5b) and (4.6) are integer.

Algorithm 2 updates the lower bound by considering the elements of $\hat{\mathcal{P}}$. Only the new columns generated once a node is solved by column generation are considered to improve the value of the lower bound. The procedure that computes a MST for each element of $\hat{\mathcal{P}}$ is performed from step 21 to 28. The weight of the MST with the largest weight becomes the best lower bound.

The only case where the integrality of the solution is verified is in step 30 in order to decide whether there is a need of branching. Steps 30 to 36 are classical steps of branching node. If the solution of the node is not integer and it has a smaller value than the lower bound, no children are generated and the node is deleted by dominance. Otherwise, an edge is selected and two children are generated. The most traditional branching strategy is used for edge selection for the branching. The edge with the value closest to 0.5 is chosen. The first edge found by the algorithm during the search for such an edge is selected in case of a tie. Once every node of the search tree is explored, the best lower bound becomes the optimal solution of the problem and the algorithm ends by providing the solution.

## 4.3 Computational Experiments

To evaluate the efficiency of the B&P algorithm is tested in this section, four configurations of type of interdiction and budget constraints are considered. The testbed includes the instances generated in Section 3.9. The $\bar{B}$-edge connected certificate is considered for each of the networks. When a cardinality constraint is imposed, we set $\bar{B} = B$. In the case of a knapsack constraint, we have $\bar{B} = \max\{\sum_{e \in \mathcal{E}} x_e : \sum_{e \in \mathcal{E}} b_e x_e \le B\}$ as in the experimentation of Section 3.9. The reduction on the size of $\mathcal{G}$ and the efficiency of constraints (4.6) only have an impact when we consider a cardinality budget constraint. This is due to the large value for $\bar{B}$ obtained by solving the problem $\max\{\sum_{e \in \mathcal{E}} x_e : \sum_{e \in \mathcal{E}} b_e x_e \le B\}$.

The pricing problem, defined by (4.5) and (4.6), is solved by the heuristic described in Algorithm 1 to find a column with a positive reduced cost. The Kruskal algorithm is considered for the computation of the MSTs. Every procedure is implemented in C++. The time limit is one hour. The experimentation
## 4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI PROBLEM

<table><caption>Table 4.1: Computational results for Cardinality Budget Constraint</caption><thead><tr><th rowspan="3">Config.</th><th rowspan="3">|V|</th><th rowspan="3">B</th><th colspan="8">Cardinality Budget Constraint</th></tr><tr><th colspan="4">Total Interdiction</th><th colspan="4">Partial Interdiction</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="3">10</td><td>3</td><td></td><td>4.5</td><td>148.5</td><td>0.00</td><td>4/4</td><td>3.5</td><td>131.5</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>143.6</td><td>922.5</td><td>0.00</td><td>4/4</td><td>45.4</td><td>589.5</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td></td><td>1870.9</td><td>2487.5</td><td>0.85</td><td>3/4</td><td>129.0</td><td>659.5</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="2">15</td><td>3</td><td></td><td>36.3</td><td>581.5</td><td>0.00</td><td>4/4</td><td>81.6</td><td>1136.5</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>3600.0</td><td>4187.0</td><td>13.96</td><td>0/4</td><td>3110.5</td><td>4006.5</td><td>5.81</td><td>2/4</td></tr><tr><td rowspan="2">20</td><td>3</td><td></td><td>206.2</td><td>858.0</td><td>0.00</td><td>4/4</td><td>506.9</td><td>1581.5</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>3600.0</td><td>2605.5</td><td>22.83</td><td>0/4</td><td>3600.0</td><td>2991.5</td><td>16.41</td><td>0/4</td></tr><tr><td rowspan="2">25</td><td>3</td><td></td><td>1238.4</td><td>1954.5</td><td>0.00</td><td>4/4</td><td>2831.0</td><td>3830.5</td><td>2.32</td><td>3/4</td></tr><tr><td>5</td><td></td><td>3600.0</td><td>1697.0</td><td>26.64</td><td>0/4</td><td>3600.0</td><td>1562.5</td><td>32.12</td><td>0/4</td></tr><tr><td rowspan="2">30</td><td>3</td><td></td><td>2692.3</td><td>3530.5</td><td>0.00</td><td>4/4</td><td>3600.0</td><td>3749.5</td><td>12.23</td><td>0/4</td></tr><tr><td>5</td><td></td><td>3600.0</td><td>1322.0</td><td>37.35</td><td>0/4</td><td>3600.0</td><td>1258.0</td><td>49.80</td><td>0/4</td></tr></tbody></table>

is performed in a 64-bit desk computer with a 2.20GHz Intel(R) Xeon(R) CPU E5-2630 v4 processor and 64 GB of RAM memory.

Computational results for both types of interdiction when we impose a cardinality constraint for the budget are reported in Table 4.1. For each configuration, the average time, the average number of nodes of the Branch-and-Bound tree and the average gap of four test instances are given. The last column of each result set presents the number of optimally solved instances out of the four tested.

Most of the networks with a budget of $B = 3$ are solved. However, the resolution time becomes large as the size of the network increases, being larger than 200 seconds for graphs of 20 nodes or more. Except for networks with $|V| = 10$, the B&P algorithm is practically unable to solve graphs with an interdiction budget of 5 or more. For total interdiction, the average relative gaps between the best known solution and the upper bound retrieved at time limit of networks with 15 nodes more increase gradually from 13.96% to 37.50%. In the case of partial interdiction, from 5.81% to 49.80%. Moreover, for the latter interdiction, no network of 30 nodes in size was optimally solved.

Table 4.2 contains the computational experimentation with respect to the knapsack budget constraint. For simplification, the fraction $\eta$ of the largest edge weight is reported as the budget. Networks of 10 nodes are optimally solved in a reasonable time of less than 24 seconds. The B&P algorithm starts to struggle on graphs of 15 nodes, $\eta = 0.8$ and total interdiction. Two out of four instances are not solved. For partial interdiction, all 15 nodes graphs are solved. However,
<table><caption>Table 4.2: Computational results for Knapsack Budget Constraint</caption><thead><tr><th rowspan="3">Config.</th><th rowspan="3">|V| B</th><th colspan="8">Knapsack Budget Constraint</th></tr><tr><th colspan="4">Total Interdiction</th><th colspan="4">Partial Interdiction</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="4">10</td><td>0.2</td><td>0.1</td><td>5.5</td><td>0.00</td><td>4/4</td><td>0.1</td><td>3.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.4</td><td>15.5</td><td>0.00</td><td>4/4</td><td>0.2</td><td>5.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>3.0</td><td>94.0</td><td>0.00</td><td>4/4</td><td>1.5</td><td>44.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>24.0</td><td>594.5</td><td>0.00</td><td>4/4</td><td>4.4</td><td>99.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="4">15</td><td>0.2</td><td>0.5</td><td>4.0</td><td>0.00</td><td>4/4</td><td>0.6</td><td>5.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>10.4</td><td>85.5</td><td>0.00</td><td>4/4</td><td>4.5</td><td>48.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>236.3</td><td>1218.5</td><td>0.00</td><td>4/4</td><td>41.7</td><td>348.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>2107.0</td><td>3908.5</td><td>15.61</td><td>2/4</td><td>1092.2</td><td>2226.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="4">20</td><td>0.2</td><td>9.5</td><td>28.5</td><td>0.00</td><td>4/4</td><td>9.7</td><td>33.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>159.5</td><td>414.5</td><td>0.00</td><td>4/4</td><td>213.3</td><td>509.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>2781.0</td><td>3680.0</td><td>13.37</td><td>1/4</td><td>1555.6</td><td>2483.0</td><td>1.55</td><td>3/4</td></tr><tr><td>0.8</td><td>3600.0</td><td>3206.0</td><td>27.04</td><td>0/4</td><td>1690.4</td><td>2163.0</td><td>3.03</td><td>3/4</td></tr><tr><td rowspan="4">25</td><td>0.2</td><td>37.6</td><td>91.5</td><td>0.00</td><td>4/4</td><td>31.2</td><td>66.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1412.4</td><td>2893.0</td><td>0.32</td><td>3/4</td><td>1197.0</td><td>2213.0</td><td>2.56</td><td>3/4</td></tr><tr><td>0.6</td><td>3295.3</td><td>2672.5</td><td>35.17</td><td>1/4</td><td>1965.2</td><td>2022.0</td><td>10.73</td><td>2/4</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">30</td><td>0.2</td><td>104.1</td><td>142.5</td><td>0.00</td><td>4/4</td><td>225.4</td><td>296.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>2753.0</td><td>2291.5</td><td>11.61</td><td>2/4</td><td>3065.2</td><td>2628.0</td><td>7.58</td><td>2/4</td></tr><tr><td>0.6</td><td>3600.0</td><td>1110.0</td><td>51.78</td><td>0/4</td><td>3600.0</td><td>1844.5</td><td>21.88</td><td>0/4</td></tr></tbody></table>

there is a drastic increment in resolution time of more than 1000 seconds when $\eta = 0.8$. No instance was solved for a budget of 0.8 and 20 nodes for total interdiction. A clear tendency can be seen, where the bigger the budget the less test instances are solved. Unlike the results of cardinality constraint, more test instances are solved when considering partial interdiction in the knapsack case.

## 4.4 Conclusions

The B&P algorithm is very limited, specially in the cardinality case. When considering a cardinality constraint, $[MSTI_{SDual}]$ solves instances of up to 50 nodes in Chapter 3 whereas in the current section, the B&P algorithm reached the time limit even in small instances of 15 nodes and with a budget of 5. Two reasons might cause this behavior. First, the solver employed to solve the mathematical formulations handles more efficiently the branching of the variables. In our B&P algorithm, the most traditional branching strategy is used to select the variable on which we branch. According to research in Achterberg (2007), this strategy is generally not significantly better than choosing a variable at random. Second, imposing the branching rules and re-optimizing the $[RMP(\hat{\mathcal{P}})]$ is more time con-
4. A BRANCH-AND-PRICE ALGORITHM FOR THE MSTI
PROBLEM

assuming than solving the original model. Therefore, a B&P algorithm where a
decomposition on the variables defining an interdiction plan is not as efficient
than solving a MIP of the MSTI problem.
# Chapter 5

## Benders Decomposition for the
MSTI Problem

The numerical experiments of Chapters 3 and 4 indicate the need to move to a different approach to design a resolution method. The MSTI problem becomes more challenging to solve as the size of the instance increases. This is highlighted by the results of previous chapters where instances of 30 nodes or more cannot be solved and the relative gaps between the best known solutions and the upper bounds of even larger instances of our proposed formulations are greater than 50%.

The number of edges of a graph, and thus the number of variables associated with each edge, grows in a quadratic rate as the number of nodes increases. In Chapter 4, we proposed an B&P algorithm that is initialized with a restricted set of variables. As the algorithm solves an MSTI instance, more variables are generated. In this manner, it is hoped to work with a less amount of variables than the MIPs defined in Chapter 3. However, the computational experiments of Chapter 4 proved that the B&P algorithm is inefficient.

All formulations presented in Chapter 3 also grow quadratically in constraints since some of the families of constraints are defined over the set of edges. A Benders Decomposition (BD) algorithm is a technique that mitigates this issue; it divides a complicated problem into two problems with significantly less constraints than the original problem.

In this chapter, we propose a revised BD algorithm for the MSTI problem. Section 5.1 introduces the BD and gives the Master Problem (MP) and sub-
problem. A family of constraints of the MP is lifted in Section 5.2. A second family of constraints is defined in Section 5.3 to strengthen the MP. Section 5.4 presents two basic procedures to initialize the BD algorithm. Upper and lower bounds are discussed in Section 5.5. The revised BD decomposition is finally presented in 5.6. The separation procedure of optimality cuts as well as the particular implementation in a commercial solver of our algorithm is detailed. The chapter ends with computational experiments in Section 5.7 and conclusions in Section 5.8.

## 5.1 A Benders Decomposition

J.F. Benders in his seminal paper (Benders (1962)) proposed a decomposition technique that would later become known as Benders Decomposition. This decomposition technique aims to address hard problems that are broken down into two smaller, less complicated problems, namely the Master Problem (MP) and the sub-problem. In the original approach, the latter is necessarily a linear problem. An iterative procedure, consisting mainly of repeatedly solving both problems, is designed in order to converge to the optimal solution of the original problem. The MP is meant to work with a much smaller set of constraints than the original formulation would have, which is expected to decrease the burdensome resolution of the original problem. The reader is referred to Rahmaniani et al. (2017) for recent results on the BD algorithm.

The general formulation of the MSTI problem reads as follows:

$$ \max \min_{\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 (5.1) $$

The interdictor controls variables **x** and **x** = {**x** ∈ {0, 1}| |**x**| | Σe∈E b_e x_e ≤ B}. The network operator controls variables **y** and **y** represent the set of constraints that define the spanning trees of **G**. Therefore, the follower computes a MST on the graph **G** = (**V**, **E**) with augmented weights c_e + d_e x_e. Let **T** be the set of points of **y**. Our goal is to define a MP that only uses a subset of **T** to provide the optimal solution of the MSTI problem. Formulation (5.1) can be restated as follows:
$$ \max_{\hat{\mathbf{x}} \in \mathcal{X}} \left\{ \min_{\mathbf{y}} \left\{ \sum_{e \in \mathcal{E}} (c_e + d_e \hat{x}_e) y_e : \mathbf{y} \in \mathcal{Y} \right\} \right\} \quad (5.2) $$

The inner minimization problem of (5.2) is parameterized with $\hat{\mathbf{x}}$ thus the objective function becomes linear. If $\mathcal{G}$ is connected, the search of the MST is always feasible. The optimal solutions of the inner minimization problem corresponds to points of $\mathcal{T}$. Therefore, (5.2) is reformulated as

$$ \max_{\hat{\mathbf{x}} \in \mathcal{X}} \min_{T \in \mathcal{T}} \sum_{e \in T} (c_e + d_e \hat{x}_e) \quad (5.3) $$

where $T$ is a spanning tree, i.e. a point of $\mathcal{Y}$. To finally obtain the Benders MP, a new variable $z$ is defined in order to linearize the objective function of (5.3). The MP reads as follows:

$$ [MP(\mathcal{T})] \quad \max_{\mathbf{x},z} \quad (5.4a) $$

s.t.

$$ z \leq \sum_{e \in T} (c_e + d_e x_e) \quad \forall T \in \mathcal{T} \quad (5.4b) $$

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

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

$[MP(\mathcal{T})]$ maximizes variable $z$. Constraints (5.4b) bound $z$ by above with the weights of the spanning trees in $\mathcal{T}$. Therefore, the goal of (5.4) is to find an interdiction plan, which respects the budget constraint (5.4c), such that it increases the weights of the spanning trees of $\mathcal{T}$, thus allowing $z$ to increment its value. Model (5.4) requires the enumeration of all the spanning trees of $\mathcal{G}$. Therefore, we proceed to solve the MP by using a restricted number of spanning trees. Let $\hat{\mathcal{T}}$ be a subset of $\mathcal{T}$ and let us define $[MP(\hat{\mathcal{T}})]$ where the spanning trees considered in (5.4b) are only those of $\hat{\mathcal{T}}$.

For each solution $\hat{\mathbf{x}}$ of $[MP(\hat{\mathcal{T}})]$, a new tree $T$ can be found by solving the
sub-problem which is defined by the inner problem of (5.2). We denote as [MST-Sub($\hat{\mathbf{x}}$)] the minimization problem of (5.2).

## 5.2 Lifted Optimality Cuts

The family of constraints (5.4b) are known as optimality cuts or constraints since they do not play a role in the feasibility of the solutions and also cut off non-optimal solutions from the feasible space. In this section, we present a lifted version of these cuts. The concept of feasibility of a spanning tree with respect to an interdiction plan is introduced first.

**Definition 5.1.** A spanning tree $T$ of $G$ is feasible with respect to an interdiction strategy $\hat{\mathbf{x}} \in \mathcal{X}$ if interdicted edges are not considered in $T$ if total interdiction is assumed or the edges of $T$ have a weight of $c_e + d_e \hat{x}_e$ if partial interdiction is assumed.

Note that every spanning tree of $G$ is feasible with respect to at least one interdiction strategy. Such a strategy being the trivial interdiction plan in which no edge is interdicted. Let $\mathcal{G}_{\hat{\mathbf{x}}}$ be a graph where the weight of each edge is $c_e+d_e \hat{x}_e$.

**Proposition 5.2.** Let $\hat{\mathbf{x}} \in \mathcal{X}$ be an interdiction strategy and $T$ an edge set that defines a feasible spanning tree with respect to $\hat{\mathbf{x}}$. Let $L = \{f \in \mathcal{E} \mid \hat{x}_f = 1\}$. In addition, $L$ is arbitrarily ordered so that $L = \{f_1, f_2, \dots, f_{|L|}\}$. Let $\hat{\mathbf{x}}_i$ be a modified interdiction plan of $\hat{\mathbf{x}}$ where edges $x_{f_1}, x_{f_2}, \dots, x_{f_{i-1}}$ and $x_{f_i}$ are no longer interdicted. Let $q_0$ be the weight of $T$ and $q_i$ represents the weight of the MST of $\mathcal{G}_{\hat{\mathbf{x}}_i}$ for $i = 1, 2, \dots, |L|$. Then, the lifted optimality constraints (5.5a) are tighter constraints than optimality constraints (5.4b).

$$z \le \sum_{e \in T} (c_e + d_e x_e) + \sum_{f_i \in L} (q_i - q_{i-1})(1 - x_{f_i}) \quad (5.5a)$$

*Proof.* The second summation of the right-hand side of the lifted optimality cut is a valid upper bound of $z$ since it is the recalculation of the weight of $T$ if the interdiction of some of the edges in $\hat{\mathbf{x}}$ is removed. Since coefficient $q_i - q_{i-1}$ is negative by definition on the interdiction plan $\hat{\mathbf{x}}$, the next inequality follows.
$$z \le \sum_{e \in T} (c_e + d_e x_e) + \sum_{f_i \in L} (q_i - q_{i-1})(1 - x_{f_i}) \le \sum_{e \in T} (c_e + d_e x_e) \quad (5.6a)$$

Clearly, the lifted optimality cuts (5.5a) are tighter inequalities than (5.4b) and the proposition is proved. □

The interpretation of the second summation in (5.5a) is the following: if the interdiction of edge $f_i$ were to be released then a decrement of $q_i - q_{i-1}$ units in the current weight of $T$ will occur.

## 5.3 Set Covering Constraints

A second family of valid inequalities for the MSTI problem is defined by the set covering constraints that are presented in this section.

Let $\mathcal{SC}(v^*) := \{T \in \mathcal{T} | \sum_{e \in T} c_e < v^*\}$ be the set that contains the trees of $\mathcal{T}$ whose weight is less than $v^*$, the optimal value. The set covering constraints are stated as follows:

$$\sum_{e \in T} x_e \ge 1 \qquad \forall T \in \mathcal{SC}(v^*) \quad (5.7a)$$

Constraints (5.7a) ensure the interdiction of at least one edge of each tree that has a weight less than $v^*$. If there exists a tree $\bar{T}$ with weight $\bar{v}$ such that $\bar{v} < v^*$ and none of its edges are interdicted, then the network operator will select this tree as its optimal solution which contradicts the fact that $v^*$ is the optimal objective value. Clearly, $v^*$ is not known a priori, however constraints (5.7a) are valid for any value $v' \le v^*$. Therefore, the value of a known solution is used to define $\mathcal{SC}(v')$. If a solution with a better objective value $v''$ is found, the set $\mathcal{SC}(v')$ is updated to $\mathcal{SC}(v'')$ and more constraints can be defined. This same type of valid inequalities is proposed in Israeli & Wood (2002) for the SPI problem. In Wei et al. (2021), the authors give a mathematical formulation for the MSTI problem defined only by set covering inequalities.
## 5.4 Initialization of $\hat{\mathcal{T}}$ and the initial solution

In a BD algorithm, the MP is initialized with a restricted number of constraints. Then, as the algorithm iterates more constraints are added to the MP. In this section, we present how set $\hat{\mathcal{T}}$ is initialized in the developed BD algorithm.

Two trees are used to initialize $\hat{\mathcal{T}}$. The first one is the MST of $\mathcal{G}$ since this is a spanning tree that must be interdicted to worsen the weight of the MST computed by the follower.

The second spanning tree is obtained by a simple procedure developed to obtain a good feasible solution for the MSTI problem. The latter is built to define the initial solution of our algorithm in order to have a good initial lower bound for the problem and to define the set $\mathcal{SC}(v')$ where $v'$ is the value of this solution. Therefore, two basic procedures, depending on the type of budget constraint, are presented to generate the second spanning tree.

An enumeration algorithm is developed for the cardinality case. Given $B$ edges to be interdicted, all interdiction plans of $B$ edges that contain only edges of $T_0$ are computed, where $T_0$ is the MST of $\mathcal{G}$. They are considered one by one to interdict the network and compute the MST in the augmented graph. The best solution found is then added to $\hat{\mathcal{T}}$.

For the knapsack case, a more basic approach is taken. Since in the enumeration algorithm proposed for the cardinality case it is needed to know in advance the number of edges to interdict, the same approach cannot be followed here. Therefore, we provide the solution of the most vital edge as initial solution. The algorithm is straightforward. The $|V| - 1$ single-edge interdiction plans of $T_0$ are generated. The one that causes the greatest increase of the weight of the MST is the most vital edge and the associated tree is added to $\hat{\mathcal{T}}$.

## 5.5 Upper and Lower Bounds of $[MP(\hat{\mathcal{T}})]$

The classical BD algorithm consists of iteratively solving the MP and the subproblem. $[MP(\hat{\mathcal{T}})]$ is initialized with a limited number of trees in $\hat{\mathcal{T}}$, for instance the ones proposed in Section 5.4. The master problem is solved and an interdiction plan $\hat{\mathbf{x}}$ is found. $[MST-Sub(\hat{\mathbf{x}})]$ is parameterized with this interdiction plan. A new tree $T$ is then computed by solving the sub-problem. $T$ is subsequently
added to [MP($\hat{\mathcal{T}}$)], i.e. a new optimality cut (5.4b) is added to $\hat{\mathcal{T}}$. The MP is re-optimized and the process is repeated. In this section, we explain that the classical BD algorithm for the MSTI problem is valid and finite.

Since $\hat{\mathcal{T}} \subseteq \mathcal{T}$, $[MP(\hat{\mathcal{T}})]$ considers a smaller number of spanning trees than (5.4). Therefore, the former formulation is a relaxation of the latter. For this reason, solutions of $[MP(\hat{\mathcal{T}})]$ provide valid upper bounds for the MSTI problem. The solution given by $[MST-Sub(\hat{\mathbf{x}})]$ is a valid lower bound for the MSTI problem since it is the optimal response to the interdiction strategy $\hat{\mathbf{x}}$.

At each iteration of the BD algorithm, the best bounds are retrieved. The algorithm ends when both bounds are equal. Given a complete graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, the number of spanning trees in $\mathcal{G}$ is $|\mathcal{V}|^{|\mathcal{V}|-2}$ (Bedrosian (1964)). Since there is a finite number of spanning trees in $\mathcal{T}$, the procedure terminates in a finite number of iterations. It is expected that only a subset of $\mathcal{T}$ is generated by the iterative algorithm thus leading to solve a significantly smaller problem than $[MP(\mathcal{T})]$.

Based on the procedure above, a revised BD algorithm is presented in the following section where $[MP(\hat{\mathcal{T}})]$ is solved only once and lifted optimality cuts as well as set covering constraints are defined dynamically during optimization.

# 5.6 Revised Benders Decomposition Algorithm

In the previous sections, the main components of the revised BD algorithm proposed in this manuscript were introduced. In this section, it is explained how these components interact. The separation procedures for the optimality cuts and set covering constraints and the implementation of our algorithm are presented.

## 5.6.1 Enhanced Master Problem

The lifted optimality constraints (5.5a) and the set covering constraints (5.7a) and the tree constraints (4.6) were demonstrated to be valid for the $[MP(\hat{\mathcal{T}})]$. Therefore, an enhanced MP can be defined. Let $\mathcal{L}$ be a set of triplets $(T, L, \mathbf{q})$ where each of its components is defined as in Proposition 5.2. Let $\mathcal{SC}(v') := \{T \in \hat{\mathcal{T}} \mid \sum_{e \in T} c_e < v'\}$ be a collection that contains the edge sets that define spanning trees of $\mathcal{G}$ and whose weights have a value less than $v'$. In addition, $v'$ is set to be greater than or equal to the weight of $T_0$. The enhanced MP reads as follows:
## 5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

$$ [MP(\mathcal{L}, \mathcal{SC}(v'))] \max_{\mathbf{x},z} z, \qquad (5.8a) $$

s.t.

$$ z \le \sum_{e \in T} (c_e + d_e x_e) + \sum_{f_i \in L} (q_i - q_{i-1})(1 - x_{f_i}), \quad \forall (T, L, \mathbf{q}) \in \mathcal{L} \qquad (5.8b) $$

$$ \sum_{e \in T} x_e \ge 1 \qquad \forall T \in \mathcal{SC}(v') \qquad (5.8c) $$

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

$$ \sum_{e \in T_i} x_e \le \bar{B} - i \qquad \forall i = 0, 1, \dots, \bar{B} \qquad (5.8e) $$

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

In $[MP(\mathcal{L}, \mathcal{SC}(v'))]$, constraints (5.4b) are replaced by their lifted version (5.8b). Set covering constraints (5.8c) are added. Finally, the tree constraints (5.8e), defined in Section 4.2.2.1 for the pricing problem, are as well considered for the enhanced MP. The latter family of constraints are also valid for $[MP(\mathcal{L}, \mathcal{SC}(v'))]$ since they cut-off non-optimal interdiction strategies.

### 5.6.2 Separation Procedure for the Lifted Optimality Cuts

The lifted optimality cuts defined by Proposition 5.2 require a specific setting of set $L$ and vector $\mathbf{q}$ in order to be valid. In the following, a procedure that determines both parameters is presented. For any edge set $\mathcal{E}'$, let $w(\mathcal{E}') = \sum_{e \in \mathcal{E}'} c_e$ and $T_0$ the MST of $\mathcal{G}$. Let $T$ be the MST given by $[MST-Sub(\hat{\mathbf{x}})]$ for a given interdiction plan $\hat{\mathbf{x}}$. Let $q_0$ denote the weight of $T$. Let $\mathcal{J}_{\hat{\mathbf{x}}}$ be the set of edges that have a positive component in vector $\hat{\mathbf{x}}$. Assume that each time an element is added to $L$, it is arbitrarily ordered so that $L = \{f_1, f_2, \dots, f_{|L|}\}$ where $f_{|L|}$ is the last element added. Algorithm 3 presents a procedure which lifts constraints (5.4b).

Algorithm 3 has as input a pair $(\hat{\mathbf{x}}, T)$, that is an interdiction strategy with its respective spanning tree that is the optimal reaction of the follower. In Step 2, a graph $\mathcal{G}'$ with respect to $\hat{\mathbf{x}}$ is defined by removing all interdicted edges, i.e. all edges associated with a non zero $x_e$ value in $\hat{\mathbf{x}}$ are removed from $\mathcal{G}$. A loop on
**Algorithm 3** Separation Procedure for the Lifted Optimality Cuts

**Require:** A pair $(\hat{\mathbf{x}}, T)$

**Ensure:** A triplet $(T, L, \mathbf{q})$ where each component is as in Proposition 5.2

1: $i \leftarrow 1$; $L \leftarrow \emptyset$; $\mathbf{q} \leftarrow \mathbf{0}$

2: $\mathcal{G}' \leftarrow \mathcal{G} \setminus \mathcal{J}_{\hat{\mathbf{x}}}$

3: $L' \leftarrow T_0 \setminus T$

4: **while** $L' \neq \emptyset$ **do**

5: Select $f \in L'$

6: $\mathcal{G}' \leftarrow \mathcal{G}' \cup \{f\}$

7: Calculate MST $T_i$ of $\mathcal{G}'$

8: $q_i \leftarrow w(T_i)$

9: $L \leftarrow L \cup \{f\}$

10: $L' \leftarrow L' \setminus \{f\}$

11: $i \leftarrow i + 1$

12: **end while**

13: Return $(T, L, \mathbf{q})$

set $L'$, which characterizes the edges of $T_0$ that do not appear in $T$, is performed from Steps 4 to 12. Set $L'$ is composed of edges of $T_0$ that were not selected in $T$ since those edges will cause a decrement on the weights of the trees of $\mathcal{G}'$ when they are added to $\mathcal{G}'$. Since $|L'| \le |V| - 1$, Algorithm 3 ends in at most $|V| - 1$ iterations. The loop consists in selecting an edge $f \in L'$. Then the graph is augmented by adding this edge to $\mathcal{G}'$ and the MST is recalculated and its weight is retrieved. Finally, we include $f$ in $L$.

The output of Algorithm 3 is a triplet $(T, L, \mathbf{q})$. Due to the assumption stated above, set $L$ is a rearrangement of the edges of $L'$ to match the weights of the trees in $\mathbf{q}$. Note that $q_i \le q_{i-1}$ for $i = 1, \dots, |L|$ since, at each iteration of the loop of the Algorithm 3, the edges which belong to $T_0$ are added to $\mathcal{G}'$; the weight of the new tree is thus necessarily equal or smaller. For each pair $(\hat{\mathbf{x}}, T)$, a triplet $(T, L, \mathbf{q})$ is calculated by Algorithm 3 which is subsequently added to a collection $\mathcal{L}$.

Figure 5.1 presents an illustrative example of the lifting procedure. The initial graph and $T_0$ is shown in Figure 5.1a where the blue edges represent $T_0$. The weight of this tree is 10. By assuming total interdiction, a cardinality constraint and a budget $B = 2$, the graph in Figure 5.1b is obtained. $\mathcal{G}'$ is defined by the black and blue edges, dotted lines represent $\hat{\mathbf{x}}$ and the blue edges represent $T$ which is the MST with respect to $\hat{\mathbf{x}}$. Scalar $q_0$ is 19, i.e. the weight of $T$. Thus,
## 5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

$L' = \{\{1,5\}, \{4,5\}\}$. We select an edge of $L'$, in this case $\{4,5\}$. Edge $\{4,5\}$ is added to $G'$ and the MST is computed. The resulting graph is shown in 5.1c. The weight of the new tree is 13, thus $q_1 = 13$. The same procedure is repeated for edge $\{1,5\}$. The initial graph is obtained, i.e. the one shown in Figure 5.1a. Therefore, $q_2 = 10$. Now, it is possible to define the optimality constraint (5.5a) with respect to this example as:

$$ 
\begin{aligned}
z &\le \sum_{e \in T} (c_e + d_e x_e) + (13 - 19)(1 - x_{45}) + (10 - 13)(1 - x_{12}) \\
&= \sum_{e \in T} (c_e + d_e x_e) - 6(1 - x_{45}) - 3(1 - x_{12})
\end{aligned}
$$

Therefore, a decrement of 6 units in the weight of $T$ is obtained if $x_{45}$ is not interdicted. Analogously, the weight of $T$ diminishes by three units if $x_{12}$ is not interdicted.

<figure><img src="image_5.png" /></figure>
5.6.3 Implementation of the Revised BD Algorithm

In a classical BD algorithm, the MP and the sub-problem are iteratively solved to
optimality, one after the other, to converge to the optimal solution of the original
problem. In our revised algorithm, [MP($\mathcal{L}$, $\mathcal{SC}(v')$)] is solved only once via a
Branch-and-Cut algorithm managed by a commercial optimizer where constraints
(5.8b) and (5.8c) are dynamically added via user cut and lazy constraint callbacks.
Both user cut and lazy constraint callbacks allow to add user-defined cuts at each
node of the search tree.

A lazy constraint callback is a procedure that adds constraints that define the
feasible space of a problem. Those constraints are too many to include all at once
at the beginning of the optimization process. These are exactly constraints (5.8b)
originally defined with respect to $\mathcal{T}$. The lazy constraint callback is called when
an integer interdiction plan $\hat{\mathbf{x}}$ is found. The procedure generates a constraint
(5.8b) and checks whether this cut is violated by the integer solution. If yes, the
constraint is added to the full model. In addition, a constraint (5.8c) is defined,
and added to the model when it is violated. If constraint (5.8b) is not violated,
the candidate solution becomes the new incumbent of the problem.

When solving a node in a Branch-and-Cut algorithm, problem-specific cuts
are added through user cut callbacks that tighten the LP relaxation of the node.
User cut callbacks mainly separate fractional solutions, i.e. they try to find a
constraint that violates this solution to strengthen the LP relaxation. In this case,
constraints (5.8b) are defined to improve the relaxation. If the lifted optimality
cut is violated, a set covering constraint is generated too. If no violated cuts are
found, the node is solved and a new node is treated or the algorithm stops.

The classical BD algorithm is implicit in the optimization process explained
above. The lazy constraint callback plays the role of the sub-problem. When an
integer solution candidate is found, it means that this solution is optimal for the
current [MP($\mathcal{L}$, $\mathcal{SC}(v')$)] and a new cut that violates the solution is added, just
as in a classical Benders Decomposition. Algorithm 4 presents a pseudo-code of
our revised BD algorithm.

[MP($\mathcal{L}$, $\mathcal{SC}(v')$)] is implemented in a commercial solver with an initial number
of elements in $\mathcal{L}$ and $\mathcal{SC}(v')$. In Step 1 of Algorithm 4, $\mathcal{L}$ is initialized with the
triplet corresponding to the MST. [MP($\mathcal{L}$, $\mathcal{SC}(v')$)] has to be initialized with at
least the lifted optimality constraint with respect to $T_0$. Since $T_0$ is the MST
5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

**Algorithm 4 Revised Benders Decomposition for the MSTI problem**

**Require:** An instances of a MSTI problem

**Ensure:** Optimal interdiction plan **x** with its associated MST **y**

1: $\mathcal{L} \leftarrow \{(T_0, \emptyset, \mathbf{q})\}$ where $\mathbf{q} \in \mathbf{0}^{|L|+1}$

2: Generate feasible solution $(\hat{\mathbf{x}}', T')$ as in Section 5.4

3: Compute $(T', L, \mathbf{q})$ using Algorithm 3

4: $\mathcal{L} \leftarrow \mathcal{L} \cup \{(T', L, \mathbf{q})\}$

5: $\mathcal{S}\mathcal{C}(v') \leftarrow \emptyset$ where $v' = w(T')$

6: Provide $\hat{\mathbf{x}}'$ as initial solution to the solver

7: **if** Time limit is not met **then**

8: (Re)Optimize $[\text{MP}(\mathcal{L}, \mathcal{S}\mathcal{C}(v'))]$ for $\hat{\mathbf{x}}$

9: **if** Solver calls a callback **then**

10: In a Control Callback:

11: Obtain $T$ by solving $[\text{MST-Sub}(\hat{\mathbf{x}})]$

12: Compute $(T, L, \mathbf{q})$ using Algorithm 3

13: **if** (5.5a) is violated **then**

14: $\mathcal{L} \leftarrow \mathcal{L} \cup \{(T, L, \mathbf{q})\}$

15: **if** $w(\mathcal{T}) < v'$ **then**

16: $\mathcal{S}\mathcal{C}(v') \leftarrow \mathcal{S}\mathcal{C}(v') \cup \{T\}$

17: **end if**

18: **end if**

19: Go to Step 8

20: **end if**

21: **end if**

22: Compute **y** with respect to **x**

23: Return $(\mathbf{x}, \mathbf{y})$

of $\mathcal{G}$ or in other words $T_0$ is the optimal reaction of the follower to the trivial interdiction strategy, no non-empty edge set $L$ induces a decrement of the weight of $T_0$. Thus, $L = \emptyset$ and $\mathbf{q} \in \mathbf{0}^{|L|+1}$. In Steps from 2 to 6, one of the procedures for either cardinality or knapsack constraint presented in Section 5.4 is invoked to generate a feasible initial solution $T'$ in order to define a second optimality cut. Then, we update $\mathcal{S}\mathcal{C}(v')$ with $v' = w(T')$ and provide $\hat{\mathbf{x}}'$ as an incumbent solution to the solver. A lower bound for the MSTI problem is automatically computed by the solver from the incumbent solution. Adding a second triplet $(T', L, \mathbf{q})$ to $\mathcal{L}$ is optional. However, the latter is done in the hope of fathoming nodes of the search tree if a strong lower bound is provided.

The optimization via the Branch-and-Cut algorithm is launched in Step 8. During optimization, the solver can call a control callback, either user cut or lazy
constraint callback, to tighten the LP relaxation of a given node or to check if a
candidate integer solution can become the new incumbent of the problem. The
latter is declared in Step 9. From step 10 to 19, additional constraints (5.8b)
and (5.8c) are generated and added by both callbacks. The user cut and lazy
constraint callback procedures are implemented in the same manner. Both use a
non-optimal solution ˆx (either integer or fractional) to parameterize the [MST-
Sub(ˆx)]. The sub-problem is solved to obtain a spanning tree T. Then, the
pair (ˆx, T) is given as input to Algorithm 3 in order to define a lifted optimality
constraint. If the lifted optimality constraint with respect to T is violated, it
is added to L. A tolerance of 10% on the violation of (5.5a) with respect to
its right-hand side is considered for constraints generated by fractional solutions.
This is, a violated cut is only added to the collection L if z is greater than or
equal to 110% percent of the right-hand side value of constraint (5.5a). The latter
is done in the hope of speeding up the resolution of the problem by avoiding the
inclusion of violated cuts to the model that will not greatly improve the upper
bound of a Branch-and-Bound node.

The value of the incumbent integer solution of the initial solution or from
another solution found during the optimization process is denoted by $v'$. In
Step 15, $v'$ is compared to the weight of $T$. If this spanning tree has a smaller
weight than the incumbent value, it is added to the collection $SC(v')$. The value
$v'$ is automatically updated by the solver when a new incumbent solution is
found. Regardless that constraints where added or not by a control callback,
the procedure re-optimizes the model as stated in Step 19. Algorithm 4 jumps
to Step 22 when the solver has found the optimal solution or the time limit has
been met according to the conditions of Step 7. Vector $y$ is computed in this step
since $[MP(L, SC(v'))]$ only provides the optimal plan $x$. The computation of $y$ is
easily done by solving $[MST-Sub(x)]$. Finally, the algorithm ends by returning
the optimal solution $(x, y)$ for the MSTI problem.

The main advantage of the Algorithm 4 is that the solver handles the branch-
ing of variables with respect to the criteria it finds the most advantageous and
which are usually complicated for the user to identify. Note that the termination
condition is also imposed by the solver, the optimization process will not stop un-
til the branching is completed and all the nodes of the search tree are examined
or the time limit is met.
## 5.7 Computational Experiments

This section is divided into two parts. First, the generation of the test instances is explained. Four different types of instances are considered where the main differences are in the magnitude of the weights of the edges or the sparsity of the graph. This is explained in Section 5.7.1. The second part consists in the numerical results of our revised BD algorithm and are reported in Section 5.7.2. The results are discussed and conclusions are then given.

### 5.7.1 Instance Generation

A total of 408 graphs of different sizes and densities for our numerical experiments are proposed. We test, on each graph, both types of interdiction and both types of budget constraints. In addition, we vary the budget size for each setup. In total, 6744 instances, which include those of Chapters 3 and 4, are considered to determine the efficiency of the BD algorithm. The details of the instance data are as follow.

We classify the graphs into four types, namely Types 1 to 4. Type 1 instances are complete graphs, i.e. $|\mathcal{E}| = |\mathcal{V}|(|\mathcal{V}| - 1)/2$. The weights $c_e$ are randomly assigned from 1 to $|\mathcal{E}|$ to have edges with different weights. The latter can be done without loss of generality. Interdiction costs $b_e$ for each $e \in \mathcal{E}$ are randomly generated and uniformly distributed in $[1, |\mathcal{E}|]$. Two different interdiction augmentations are defined, one for total interdiction and the other one for partial interdiction. For each edge $e \in \mathcal{E}$, we define $d_e = |\mathcal{E}| - c_e + 1$ for total interdiction. For partial interdiction, $d_e$ is randomly generated and according to a uniform distribution in $[1, |\mathcal{E}| - c_e + 1]$.

The instances considered in the sections of computational experiments of Chapters 3 and 4 are what we refer to as Type 2 instances. The weights are randomly generated and uniformly distributed in $[1, 100]$. Without loss of generality, an arbitrary total order is proposed for edges of the same weight. Similarly as in Type 1 instances, the interdiction augmentation for total interdiction is defined as $d_e = \max_{f \in \mathcal{E}} c_f - c_e + 1$. For partial interdiction, a random value between $[1, \max_{f \in \mathcal{E}} c_f - c_e + 1]$ is generated. Last, the interdiction costs are randomly generated and uniformly distributed in $[1, 100]$.
Instances of Type 1 and 2 are complete graphs. We extend our experimenta-
tion to sparse graphs and retrieve Type 3 instances proposed in Wei et al. (2021).
The density of these networks ranges from 3% to 10%. Their instances contain
fractional weights and interdiction costs randomly generated in [1, 100]. We round
up these values and also generate the remaining parameters, i.e. the interdiction
augmentations for both total and partial interdiction, as in instances of Type 2.

The parameters of the last set of instances, Type 4, are generated exactly
as those of Type 2 instances. The difference between both of them lies in the
number of edges of the network. The generated graphs of Type 4 have a density
between 50% and 70%.

A total of 44 graphs were created for each of the instance Types 1, 2, and 4.
The size of the graphs are |V| = 20, 25, 30, 50, 75, 100, 125, 150 and 200. There are
300 instances of Type 3 that were modified as previously stated. They include
40, 80, 120, 160, and 200 nodes.

The budget considered depends on the size of the network and the type of
budget constraint. For a cardinality constraint, budgets of 3, 5, 7, 8 and 9 are set.
The budgets in the knapsack case are determined using the largest edge weight
of the network. A percentage of the largest $c_e$ is computed and used as $B$. These
fractions are $\eta = 0.2, 0.4, 0.6, 0.8, 1$ and $1.2$. Since budgets are impartially set
for all instances of Type 1, 2 and 4, it may happen that the allocated budget is
large enough to disconnect the network. If it occurs, the instance is disregarded.

Budgets for the cardinality case are different for Type 3 instances since those
networks have a much smaller density than the networks of other type of instances.
Therefore, budgets of 2, 3 and 4 are considered for the cardinality case. For the
knapsack case, we consider the same budgets as in the other instance types.
However, as in Type 4 instances, the allocated budget can be large enough to
disconnect the graph. Again, these instances are discarded in this case.

5.7.2 Computational Results

The efficiency of Algorithm 4 for the MSTI problem is assessed in this section.
All procedures and algorithms are implemented in C++. CPLEX 12.9 is the
commercial solver used to solve the MP and to implement the callback procedures.
Experiments are conducted on a 64-bit workstation with a 2.20GHz Intel(R)
Xeon(R) CPU E5-2630 v4 processor and 64 GB of RAM memory. A time limit
## 5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

<table><caption>Table 5.1: Computational results for Type 1, 2 and 4 instances under total interdiction and cardinality budget constraint.</caption><thead><tr><th rowspan="3">Config.</th><th rowspan="3">|V|</th><th rowspan="3">B</th><th colspan="10">Total Interdiction - Cardinality Budget Constraint</th></tr><tr><th colspan="4">Type 1</th><th colspan="4">Type 2</th><th colspan="4">Type 4</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="4">20</td><td>3</td><td></td><td>0.2</td><td>128.8</td><td>0.00</td><td>4/4</td><td>0.1</td><td>151.5</td><td>0.00</td><td>4/4</td><td>0.2</td><td>195.3</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>6.1</td><td>1973.8</td><td>0.00</td><td>4/4</td><td>5.4</td><td>2066.8</td><td>0.00</td><td>4/4</td><td>5.6</td><td>1948.3</td><td>0.00</td><td>3/3</td></tr><tr><td>7</td><td></td><td>399.6</td><td>19552.8</td><td>0.00</td><td>4/4</td><td>321.2</td><td>16679.3</td><td>0.00</td><td>4/4</td><td>323.8</td><td>19605.5</td><td>0.00</td><td>2/2</td></tr><tr><td>9</td><td></td><td>3171.4</td><td>35437.0</td><td>11.97</td><td>1/4</td><td>2550.2</td><td>38385.8</td><td>9.59</td><td>2/4</td><td>3600.0</td><td>52899.0</td><td>7.44</td><td>0/1</td></tr><tr><td rowspan="4">25</td><td>3</td><td></td><td>0.2</td><td>197.0</td><td>0.00</td><td>4/4</td><td>0.3</td><td>301.0</td><td>0.00</td><td>4/4</td><td>0.3</td><td>284.5</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>10.5</td><td>3120.3</td><td>0.00</td><td>4/4</td><td>7.2</td><td>1512.0</td><td>0.00</td><td>4/4</td><td>24.1</td><td>3778.8</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td></td><td>843.2</td><td>20619.8</td><td>0.00</td><td>4/4</td><td>179.8</td><td>10131.5</td><td>0.00</td><td>4/4</td><td>702.6</td><td>22477.3</td><td>0.00</td><td>4/4</td></tr><tr><td>8</td><td></td><td>2892.3</td><td>27151.0</td><td>6.80</td><td>2/4</td><td>1581.6</td><td>27425.5</td><td>0.81</td><td>3/4</td><td>2495.4</td><td>39200.7</td><td>2.63</td><td>2/3</td></tr><tr><td rowspan="3">30</td><td>3</td><td></td><td>0.6</td><td>499.0</td><td>0.00</td><td>4/4</td><td>0.7</td><td>826.0</td><td>0.00</td><td>4/4</td><td>0.5</td><td>455.3</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>43.6</td><td>9001.3</td><td>0.00</td><td>4/4</td><td>31.0</td><td>5288.5</td><td>0.00</td><td>4/4</td><td>13.0</td><td>3705.5</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td></td><td>3258.1</td><td>39565.5</td><td>3.81</td><td>1/4</td><td>2372.3</td><td>32272.3</td><td>3.03</td><td>2/4</td><td>1688.7</td><td>32093.3</td><td>1.57</td><td>3/4</td></tr><tr><td rowspan="3">50</td><td>3</td><td></td><td>3.5</td><td>3009.8</td><td>0.00</td><td>4/4</td><td>2.1</td><td>1409.8</td><td>0.00</td><td>4/4</td><td>4.0</td><td>2623.0</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>386.9</td><td>24758.8</td><td>0.00</td><td>4/4</td><td>229.7</td><td>16076.0</td><td>0.00</td><td>4/4</td><td>311.7</td><td>18363.0</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td></td><td>2922.1</td><td>16936.5</td><td>9.71</td><td>1/4</td><td>3600.0</td><td>23528.3</td><td>11.27</td><td>0/4</td><td>3406.1</td><td>23281.5</td><td>8.33</td><td>1/4</td></tr><tr><td rowspan="3">75</td><td>3</td><td></td><td>7.0</td><td>1748.3</td><td>0.00</td><td>4/4</td><td>8.4</td><td>5692.0</td><td>0.00</td><td>4/4</td><td>12.6</td><td>6857.3</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>329.9</td><td>16042.8</td><td>0.00</td><td>4/4</td><td>437.3</td><td>89611.5</td><td>0.00</td><td>4/4</td><td>1471.8</td><td>92709.3</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td></td><td>3600.0</td><td>16526.3</td><td>7.85</td><td>0/4</td><td>3600.0</td><td>47200.0</td><td>5.28</td><td>0/4</td><td>3600.0</td><td>17688.0</td><td>8.30</td><td>0/4</td></tr><tr><td rowspan="3">100</td><td>3</td><td></td><td>55.2</td><td>17399.0</td><td>0.00</td><td>4/4</td><td>759.4</td><td>66121.8</td><td>0.00</td><td>4/4</td><td>102.1</td><td>32823.8</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td></td><td>1904.6</td><td>98721.3</td><td>0.53</td><td>3/4</td><td>3600.0</td><td>357069.8</td><td>2.37</td><td>1/4</td><td>3056.3</td><td>261785.5</td><td>1.53</td><td>2/4</td></tr><tr><td>7</td><td></td><td>3600.0</td><td>16776.0</td><td>7.88</td><td>0/4</td><td>3600.0</td><td>42201.3</td><td>7.35</td><td>0/4</td><td>3600.0</td><td>24573.3</td><td>8.08</td><td>0/4</td></tr></tbody></table>

of one hour (3600 seconds) is imposed for each experiment. Wherever a MST needs to be computed, Kruskal's algorithm is used. For each instance, the MSTI problem is defined over the network $G_{\bar{B}}$, i.e. the $\bar{B}$-edge connected certificate. The certificate, which depends on the budget, is a reduction of the network that prunes edges that are not necessary to solve the problem. When considering a cardinality budget constraint, we set $\bar{B} = B$. In the case of the knapsack constraint, $\bar{B} = \max\{\sum_{e \in E} x_e \mid \sum_{e \in E} b_e x_e \le B\}$. The resulting certificate when considering a knapsack constraint is equivalent to the original network $G$ since $\bar{B}$ results in a large number.

The tables with the computational results contain the following data. The left column *Config.* is the configuration of each test instance, i.e. the number of nodes $|V|$ and the budget $B$. Each reported value is an average on the number of instances considered. The reported data are detailed in the following. *Time*, in seconds, is the resolution time of the tested instances. *Nodes* is the number of nodes in the search tree of the Branch-and-Cut algorithm. *Gap* is the percentage of the relative gap between the upper bound and the best known solution at the end of the algorithm when an instance has been solved optimally or has reached the time limit. Finally, *Opt/Tot* represents the number of optimally solved instances over the total number of instances tested.

Numerical results considering total interdiction and cardinality budget constraint are reported in Table 5.1. Note that for some instances of the Type 4
column, there are less than four instances tested. For some of these instances, the allocated budget is large enough to disconnect the networks due to their sparsity. Therefore, these instances are omitted. For each instance size, our BD algorithm is able to solve all instances with the smallest budget $B = 3$. The CPU time is in less than one minute with the exceptions of Type 2 and Type 4 instances in 100 size instances. As the budget increases, the instances becomes more challenging to solve which is supported by the large search tree sizes for the larger values of $B$. For instances of size 20, only one instance of Type 1, two of Type 2 and none of Type 4 with a budget of 9 are solved. The average gap over the three types is of 9.66%. The same remark is valid for the other sizes, none of the instances of size 75 and 100 with $B = 7$ are optimally solved. On the other hand, our algorithm is able to solve instances of 75 nodes or less when $B \le 5$ in less than 600 seconds; with the exception of 75 node instances of Type 4, where the time increased to nearly thirty minutes. For these instances, the time ranges from a few seconds for the smallest instances to 437.3 seconds for instances of size 75 except for the instances of Type 4 where the average time increased to 1471.8 seconds. Type 2 instances are the testbed of the computational experimentation of Chapter 3. The results obtained by the BD algorithm are fairly better than those obtained by the mathematical formulations for this setup. In this section, instances of 30 nodes and a budget of 5 are solved in 31 seconds. [MSTI_Dual] solves the same instances in more than 2000 seconds. Similar comparisons can be done for instances including 20, 25 and 50 nodes.

Table 5.2 shows experimentation with the same configuration as Table 5.1 but considering partial interdiction. The results are slightly different from total interdiction. The BD algorithm appears to efficiently solve instances up to 30 nodes in size with all allocated budgets in less than 147.2 seconds. Instances of 50 nodes with 3 and 5 of budget are solved optimally, but with a time increase of at least five times over smaller sizes. From this point on, the efficiency of the proposed algorithm starts to decrease. For $B = 7$, only 5 out of 12 instances are solved. For instances of 75 nodes and $B = 3$, we can still obtain the optimal solution in less than four minutes. Thereafter, only a few instances are solved. Note that in the Type 4 column, more instances are solved compared to the other columns, which is explained by the sparsity of those networks. Type 2 instances solved by the BD algorithm provides again better results for these assumptions
## 5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

<table><caption>Table 5.2: Computational results for Type 1, 2 and 4 instances under partial interdiction and cardinality budget constraint.</caption><thead><tr><th rowspan="3">Config.</th><th rowspan="3">|V| B</th><th colspan="10">Partial Interdiction - Cardinality Budget Constraint</th></tr><tr><th colspan="4">Type 1</th><th colspan="4">Type 2</th><th colspan="4">Type 4</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="4">20</td><td>3</td><td>0.1</td><td>62.3</td><td>0.00</td><td>4/4</td><td>0.2</td><td>144.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>34.3</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>0.5</td><td>534.5</td><td>0.00</td><td>4/4</td><td>0.8</td><td>793.8</td><td>0.00</td><td>4/4</td><td>0.2</td><td>369.8</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>1.9</td><td>1793.8</td><td>0.00</td><td>4/4</td><td>4.1</td><td>2639.3</td><td>0.00</td><td>4/4</td><td>0.4</td><td>827.3</td><td>0.00</td><td>4/4</td></tr><tr><td>9</td><td>11.6</td><td>6419.5</td><td>0.00</td><td>4/4</td><td>20.3</td><td>7315.8</td><td>0.00</td><td>4/4</td><td>1.1</td><td>1880.3</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="4">25</td><td>3</td><td>0.4</td><td>270.8</td><td>0.00</td><td>4/4</td><td>0.5</td><td>484.3</td><td>0.00</td><td>4/4</td><td>0.2</td><td>182.0</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>2.3</td><td>1818.8</td><td>0.00</td><td>4/4</td><td>2.5</td><td>1606.3</td><td>0.00</td><td>4/4</td><td>0.8</td><td>987.8</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>16.1</td><td>5335.5</td><td>0.00</td><td>4/4</td><td>9.7</td><td>4393.8</td><td>0.00</td><td>4/4</td><td>3.0</td><td>2472.5</td><td>0.00</td><td>4/4</td></tr><tr><td>8</td><td>33.4</td><td>8913.8</td><td>0.00</td><td>4/4</td><td>28.9</td><td>7788.0</td><td>0.00</td><td>4/4</td><td>22.2</td><td>9988.3</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="4">30</td><td>3</td><td>0.8</td><td>451.8</td><td>0.00</td><td>4/4</td><td>1.5</td><td>940.3</td><td>0.00</td><td>4/4</td><td>0.3</td><td>292.8</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>7.2</td><td>3734.5</td><td>0.00</td><td>4/4</td><td>12.7</td><td>2897.5</td><td>0.00</td><td>4/4</td><td>1.4</td><td>1447.8</td><td>0.00</td><td>4/4</td></tr><tr><td>7</td><td>45.3</td><td>9304.3</td><td>0.00</td><td>4/4</td><td>147.2</td><td>11212.0</td><td>0.00</td><td>4/4</td><td>10.6</td><td>6086.0</td><td>0.00</td><td>4/4</td></tr><tr><td>8</td><td>20.2</td><td>3518.5</td><td>0.00</td><td>4/4</td><td>25.6</td><td>2923.8</td><td>0.00</td><td>4/4</td><td>9.2</td><td>3138.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">50</td><td>3</td><td>723.3</td><td>16142.3</td><td>0.00</td><td>4/4</td><td>659.4</td><td>24700.3</td><td>0.00</td><td>4/4</td><td>479.6</td><td>32378.3</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>2842.8</td><td>29175.0</td><td>5.56</td><td>2/4</td><td>3143.5</td><td>30536.0</td><td>8.65</td><td>1/4</td><td>1886.4</td><td>38771.0</td><td>2.53</td><td>2/4</td></tr><tr><td>7</td><td>224.8</td><td>8392.0</td><td>0.00</td><td>4/4</td><td>225.9</td><td>15195.5</td><td>0.00</td><td>4/4</td><td>66.1</td><td>13212.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="3">75</td><td>3</td><td>3209.0</td><td>17356.5</td><td>4.02</td><td>1/4</td><td>3424.8</td><td>37458.8</td><td>4.24</td><td>1/4</td><td>1700.3</td><td>115594.25</td><td>0.00</td><td>4/4</td></tr><tr><td>5</td><td>3600.0</td><td>6782.5</td><td>14.86</td><td>0/4</td><td>3600.0</td><td>10600.0</td><td>11.77</td><td>0/4</td><td>3600.0</td><td>42362.3</td><td>6.65</td><td>0/4</td></tr><tr><td>7</td><td>2663.0</td><td>33777.0</td><td>2.26</td><td>2/4</td><td>3455.4</td><td>103914.0</td><td>1.23</td><td>1/4</td><td>1371.9</td><td>59859.0</td><td>1.15</td><td>3/4</td></tr><tr><td rowspan="3">100</td><td>3</td><td>3600.0</td><td>3387.3</td><td>15.10</td><td>0/4</td><td>3600.0</td><td>7752.0</td><td>10.07</td><td>0/4</td><td>3165.1</td><td>54111.0</td><td>4.67</td><td>1/4</td></tr><tr><td>5</td><td>3600.0</td><td>1456.3</td><td>21.71</td><td>0/4</td><td>3600.0</td><td>1697.5</td><td>17.12</td><td>0/4</td><td>3600.0</td><td>14173.8</td><td>10.89</td><td>0/4</td></tr></tbody></table>

of type of interdiction and budget constraint with respect to the models. The difference in computational time is in some cases greater than 1000 seconds.

In Table 5.3, we report the results obtained when we consider the total interdiction case and a knapsack budget constraint. The testbed is extended to consider networks including 125, 150 and 200 nodes. Most instances are solved optimally. The first unsolved instances appear for networks with 100 nodes and with the highest budget. Similarly, larger size instances are not solved with budgets of 0.8 or greater which marks the limits of our algorithm. For every size and $\eta = 0.2$, the time is of less than 31.1 seconds. Graphs of 50 nodes or less have a resolution time of less than 175 seconds, the only exception is a 75 nodes Type 1 instance and $\eta = 1.2$ with a time of 669.8. For 75 nodes instances, the average resolution time is less than 132.9 with $\eta \le 0.8$. Starting with networks of 75 nodes and the largest budgets, the resolution times increase to more than a thousand seconds. The best results are obtained for Type 4 instances where only two instances of size 125 and six of size 200 are not solved. This again can be explained by the sparsity of these networks that reduces the combinatorics of the problem. The computational results obtained by solving instances of Type 2 with the mathematical models are not better than those reported in this section. However, the differences in computational time are not very large. The exceptions are instances of 50 nodes that could not be solved for the larger budgets.

Table 5.4 presents the results for partial interdiction and knapsack constraint.
<table><caption>Table 5.3: Computational results for Type 1, 2 and 4 instances under total interdiction and knapsack budget constraint.</caption><thead><tr><th rowspan="3">Config.</th><th rowspan="3">[V]</th><th rowspan="3">η</th><th colspan="10">Total Interdiction - Knapsack Budget Constraint</th></tr><tr><th colspan="4">Type 1</th><th colspan="4">Type 2</th><th colspan="4">Type 4</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="6">20</td><td>0.2</td><td>0.0</td><td>0.3</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.0</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>6.3</td><td>0.00</td><td>4/4</td><td>0.1</td><td>1.5</td><td>0.0</td><td>4/4</td><td>0.1</td><td>2.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.2</td><td>19.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>15.8</td><td>0.0</td><td>4/4</td><td>0.1</td><td>6.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.3</td><td>75.5</td><td>0.00</td><td>4/4</td><td>0.2</td><td>64.5</td><td>0.0</td><td>4/4</td><td>0.1</td><td>45.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.5</td><td>195.0</td><td>0.00</td><td>4/4</td><td>0.3</td><td>193.8</td><td>0.0</td><td>4/4</td><td>0.2</td><td>137.3</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>1.0</td><td>359.5</td><td>0.00</td><td>4/4</td><td>0.5</td><td>385.5</td><td>0.0</td><td>4/4</td><td>0.2</td><td>237.5</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">25</td><td>0.2</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.3</td><td>0.0</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>1.5</td><td>0.00</td><td>4/4</td><td>0.1</td><td>2.0</td><td>0.0</td><td>4/4</td><td>0.1</td><td>4.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.4</td><td>31.0</td><td>0.00</td><td>4/4</td><td>0.2</td><td>7.5</td><td>0.0</td><td>4/4</td><td>0.2</td><td>32.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.7</td><td>104.5</td><td>0.00</td><td>4/4</td><td>0.5</td><td>64.3</td><td>0.0</td><td>4/4</td><td>0.3</td><td>80.5</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>1.2</td><td>324.8</td><td>0.00</td><td>4/4</td><td>0.7</td><td>224.8</td><td>0.0</td><td>4/4</td><td>0.5</td><td>395.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>3.0</td><td>692.5</td><td>0.00</td><td>4/4</td><td>1.7</td><td>545.5</td><td>0.0</td><td>4/4</td><td>0.7</td><td>507.3</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">30</td><td>0.2</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.0</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>8.8</td><td>0.00</td><td>4/4</td><td>0.1</td><td>9.0</td><td>0.0</td><td>4/4</td><td>0.1</td><td>4.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.7</td><td>76.3</td><td>0.00</td><td>4/4</td><td>0.3</td><td>69.8</td><td>0.0</td><td>4/4</td><td>0.4</td><td>35.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>1.4</td><td>197.8</td><td>0.00</td><td>4/4</td><td>0.9</td><td>260.8</td><td>0.0</td><td>4/4</td><td>0.7</td><td>178.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>4.1</td><td>673.8</td><td>0.00</td><td>4/4</td><td>2.2</td><td>681.3</td><td>0.0</td><td>4/4</td><td>1.0</td><td>513.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>9.0</td><td>1350.8</td><td>0.00</td><td>4/4</td><td>7.3</td><td>1561.3</td><td>0.0</td><td>4/4</td><td>2.7</td><td>1181.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">50</td><td>0.2</td><td>0.3</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>0.0</td><td>0.0</td><td>4/4</td><td>0.2</td><td>2.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>1.2</td><td>35.0</td><td>0.00</td><td>4/4</td><td>0.6</td><td>14.0</td><td>0.0</td><td>4/4</td><td>0.7</td><td>33.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>3.2</td><td>227.0</td><td>0.00</td><td>4/4</td><td>3.5</td><td>220.0</td><td>0.0</td><td>4/4</td><td>1.7</td><td>218.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>12.1</td><td>908.0</td><td>0.00</td><td>4/4</td><td>11.6</td><td>1188.0</td><td>0.0</td><td>4/4</td><td>5.9</td><td>1269.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>42.4</td><td>3482.0</td><td>0.00</td><td>4/4</td><td>37.3</td><td>1789.0</td><td>0.0</td><td>4/4</td><td>14.0</td><td>2062.5</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>669.8</td><td>10052.3</td><td>0.00</td><td>4/4</td><td>174.2</td><td>5395.5</td><td>0.0</td><td>4/4</td><td>80.6</td><td>5339.5</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">75</td><td>0.2</td><td>0.7</td><td>2.8</td><td>0.00</td><td>4/4</td><td>0.3</td><td>0.8</td><td>0.0</td><td>4/4</td><td>0.3</td><td>11.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>4.7</td><td>76.3</td><td>0.00</td><td>4/4</td><td>1.8</td><td>53.0</td><td>0.0</td><td>4/4</td><td>1.7</td><td>25.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>19.8</td><td>567.5</td><td>0.00</td><td>4/4</td><td>16.9</td><td>582.3</td><td>0.0</td><td>4/4</td><td>8.8</td><td>561.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>119.7</td><td>2909.0</td><td>0.00</td><td>4/4</td><td>132.9</td><td>4189.0</td><td>0.0</td><td>4/4</td><td>47.6</td><td>4690.5</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>768.6</td><td>9638.8</td><td>0.00</td><td>4/4</td><td>675.0</td><td>13464.0</td><td>0.0</td><td>4/4</td><td>128.7</td><td>8728.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>2405.7</td><td>14672.8</td><td>4.67</td><td>3/4</td><td>1896.4</td><td>18948.3</td><td>3.6</td><td>3/4</td><td>429.4</td><td>22061.3</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">100</td><td>0.2</td><td>2.9</td><td>12.3</td><td>0.00</td><td>4/4</td><td>2.4</td><td>23.3</td><td>0.0</td><td>4/4</td><td>1.8</td><td>11.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>19.8</td><td>172.0</td><td>0.00</td><td>4/4</td><td>20.7</td><td>393.5</td><td>0.0</td><td>4/4</td><td>7.8</td><td>201.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>141.4</td><td>3136.8</td><td>0.00</td><td>4/4</td><td>153.2</td><td>5856.0</td><td>0.0</td><td>4/4</td><td>42.2</td><td>2654.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>953.6</td><td>15976.3</td><td>0.00</td><td>4/4</td><td>1268.2</td><td>42886.5</td><td>0.0</td><td>4/4</td><td>201.5</td><td>11760.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>3502.9</td><td>12813.3</td><td>14.89</td><td>1/4</td><td>1960.7</td><td>28347.0</td><td>0.7</td><td>3/4</td><td>1387.1</td><td>43205.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>2405.7</td><td>14672.8</td><td>4.67</td><td>3/4</td><td>1896.4</td><td>18948.3</td><td>3.6</td><td>3/4</td><td>429.4</td><td>22061.3</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">125</td><td>0.2</td><td>5.6</td><td>6.5</td><td>0.00</td><td>4/4</td><td>5.6</td><td>18.8</td><td>0.0</td><td>4/4</td><td>3.1</td><td>10.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>59.4</td><td>429.3</td><td>0.00</td><td>4/4</td><td>56.9</td><td>670.3</td><td>0.0</td><td>4/4</td><td>15.0</td><td>159.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>495.2</td><td>10465.8</td><td>0.00</td><td>4/4</td><td>298.8</td><td>5746.8</td><td>0.0</td><td>4/4</td><td>138.6</td><td>3601.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>3208.1</td><td>17081.3</td><td>2.12</td><td>1/4</td><td>2427.0</td><td>26676.0</td><td>1.8</td><td>3/4</td><td>859.3</td><td>23457.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>3600.0</td><td>4.3</td><td>28.23</td><td>0/4</td><td>3600.0</td><td>1456.3</td><td>18.6</td><td>0/4</td><td>2336.7</td><td>20495.5</td><td>4.54</td><td>2/4</td></tr><tr><td>1.2</td><td>3600.0</td><td>4.3</td><td>28.23</td><td>0/4</td><td>3600.0</td><td>1456.3</td><td>18.6</td><td>0/4</td><td>2336.7</td><td>20495.5</td><td>4.54</td><td>2/4</td></tr><tr><td rowspan="6">150</td><td>0.2</td><td>17.6</td><td>55.0</td><td>0.00</td><td>4/4</td><td>7.9</td><td>14.8</td><td>0.0</td><td>4/4</td><td>5.9</td><td>126.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>142.8</td><td>698.5</td><td>0.00</td><td>4/4</td><td>106.3</td><td>417.5</td><td>0.0</td><td>4/4</td><td>53.2</td><td>832.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>2013.9</td><td>57984.8</td><td>0.01</td><td>4/4</td><td>744.5</td><td>13593.3</td><td>0.0</td><td>4/4</td><td>344.4</td><td>11272.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>3600.0</td><td>499.3</td><td>19.33</td><td>0/4</td><td>3600.0</td><td>30113.5</td><td>5.7</td><td>1/4</td><td>1957.7</td><td>55260.5</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>3600.0</td><td>4.3</td><td>28.23</td><td>0/4</td><td>3600.0</td><td>1456.3</td><td>18.6</td><td>0/4</td><td>2336.7</td><td>20495.5</td><td>4.54</td><td>2/4</td></tr><tr><td>1.2</td><td>3600.0</td><td>4.3</td><td>28.23</td><td>0/4</td><td>3600.0</td><td>1456.3</td><td>18.6</td><td>0/4</td><td>2336.7</td><td>20495.5</td><td>4.54</td><td>2/4</td></tr><tr><td rowspan="6">200</td><td>0.2</td><td>31.1</td><td>24.8</td><td>0.00</td><td>4/4</td><td>29.6</td><td>74.5</td><td>0.0</td><td>4/4</td><td>19.3</td><td>187.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>698.4</td><td>1056.5</td><td>0.00</td><td>4/4</td><td>394.7</td><td>1423.0</td><td>0.0</td><td>4/4</td><td>290.0</td><td>3101.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>3600.0</td><td>650.0</td><td>13.25</td><td>0/4</td><td>3271.7</td><td>16141.3</td><td>4.7</td><td>1/4</td><td>3065.5</td><td>42554.0</td><td>1.85</td><td>2/4</td></tr><tr><td>0.8</td><td>3600.0</td><td>0.0</td><td>32.58</td><td>0/4</td><td>3600.0</td><td>0.0</td><td>16.7</td><td>0/4</td><td>3600.0</td><td>802.3</td><td>12.24</td><td>0/4</td></tr></tbody></table>
5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

<table><caption>Table 5.4: Computational results for Type 1, 2 and 4 instances under partial interdiction and knapsack budget constraint.</caption><thead><tr><th rowspan="3">Config.</th><th rowspan="3">V</th><th rowspan="3">η</th><th colspan="10">Partial Interdiction - Knapsack Budget Constraint</th></tr><tr><th colspan="4">Type 1</th><th colspan="4">Type 2</th><th colspan="4">Type 4</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="6">20</td><td>0.2</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.0</td><td>4.8</td><td>0.00</td><td>4/4</td><td>0.0</td><td>8.8</td><td>0.00</td><td>4/4</td><td>0.0</td><td>7.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.1</td><td>28.3</td><td>0.00</td><td>4/4</td><td>0.1</td><td>21.8</td><td>0.00</td><td>4/4</td><td>0.0</td><td>9.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.1</td><td>51.8</td><td>0.00</td><td>4/4</td><td>0.1</td><td>47.3</td><td>0.00</td><td>4/4</td><td>0.1</td><td>53.3</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.1</td><td>87.5</td><td>0.00</td><td>4/4</td><td>0.1</td><td>154.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>98.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>0.2</td><td>193.0</td><td>0.00</td><td>4/4</td><td>0.2</td><td>254.5</td><td>0.00</td><td>4/4</td><td>0.1</td><td>187.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">25</td><td>0.2</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>1.8</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>5.5</td><td>0.00</td><td>4/4</td><td>0.1</td><td>7.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>5.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.1</td><td>30.3</td><td>0.00</td><td>4/4</td><td>0.1</td><td>10.8</td><td>0.00</td><td>4/4</td><td>0.1</td><td>26.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.2</td><td>80.8</td><td>0.00</td><td>4/4</td><td>0.2</td><td>49.5</td><td>0.00</td><td>4/4</td><td>0.1</td><td>62.5</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.4</td><td>377.0</td><td>0.00</td><td>4/4</td><td>0.3</td><td>173.3</td><td>0.00</td><td>4/4</td><td>0.1</td><td>134.3</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>0.5</td><td>593.3</td><td>0.00</td><td>4/4</td><td>0.3</td><td>324.3</td><td>0.00</td><td>4/4</td><td>0.2</td><td>328.8</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">30</td><td>0.2</td><td>0.0</td><td>0.3</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.0</td><td>0.00</td><td>4/4</td><td>0.0</td><td>0.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.1</td><td>5.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>7.3</td><td>0.00</td><td>4/4</td><td>0.1</td><td>6.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>0.3</td><td>60.8</td><td>0.00</td><td>4/4</td><td>0.2</td><td>48.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>51.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>0.5</td><td>137.0</td><td>0.00</td><td>4/4</td><td>0.4</td><td>150.0</td><td>0.00</td><td>4/4</td><td>0.2</td><td>156.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>0.7</td><td>489.8</td><td>0.00</td><td>4/4</td><td>0.7</td><td>655.8</td><td>0.00</td><td>4/4</td><td>0.2</td><td>231.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>1.0</td><td>671.3</td><td>0.00</td><td>4/4</td><td>1.3</td><td>1121.8</td><td>0.00</td><td>4/4</td><td>0.4</td><td>565.5</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">50</td><td>0.2</td><td>0.2</td><td>4.8</td><td>0.00</td><td>4/4</td><td>0.1</td><td>3.0</td><td>0.00</td><td>4/4</td><td>0.1</td><td>5.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>0.6</td><td>50.0</td><td>0.00</td><td>4/4</td><td>0.5</td><td>31.3</td><td>0.00</td><td>4/4</td><td>0.4</td><td>45.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>1.1</td><td>224.8</td><td>0.00</td><td>4/4</td><td>1.4</td><td>197.3</td><td>0.00</td><td>4/4</td><td>0.8</td><td>301.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>2.7</td><td>1080.8</td><td>0.00</td><td>4/4</td><td>2.8</td><td>747.8</td><td>0.00</td><td>4/4</td><td>1.2</td><td>521.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>5.6</td><td>2233.3</td><td>0.00</td><td>4/4</td><td>5.6</td><td>1887.3</td><td>0.00</td><td>4/4</td><td>2.4</td><td>1434.5</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>13.8</td><td>4757.8</td><td>0.00</td><td>4/4</td><td>14.1</td><td>4135.0</td><td>0.00</td><td>4/4</td><td>5.1</td><td>2785.3</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">75</td><td>0.2</td><td>0.6</td><td>8.3</td><td>0.00</td><td>4/4</td><td>0.3</td><td>3.8</td><td>0.00</td><td>4/4</td><td>0.2</td><td>9.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>2.2</td><td>190.0</td><td>0.00</td><td>4/4</td><td>1.8</td><td>98.0</td><td>0.00</td><td>4/4</td><td>0.8</td><td>124.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>4.9</td><td>357.0</td><td>0.00</td><td>4/4</td><td>5.8</td><td>762.3</td><td>0.00</td><td>4/4</td><td>2.3</td><td>583.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>17.2</td><td>2544.3</td><td>0.00</td><td>4/4</td><td>23.1</td><td>4416.0</td><td>0.00</td><td>4/4</td><td>7.2</td><td>2641.3</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>46.8</td><td>6122.8</td><td>0.00</td><td>4/4</td><td>64.3</td><td>12093.3</td><td>0.00</td><td>4/4</td><td>16.6</td><td>6838.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>134.8</td><td>13725.8</td><td>0.00</td><td>4/4</td><td>184.0</td><td>26834.3</td><td>0.00</td><td>4/4</td><td>39.6</td><td>14244.8</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">100</td><td>0.2</td><td>2.0</td><td>26.5</td><td>0.00</td><td>4/4</td><td>2.1</td><td>71.3</td><td>0.00</td><td>4/4</td><td>1.3</td><td>116.8</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>9.4</td><td>417.0</td><td>0.00</td><td>4/4</td><td>12.6</td><td>1318.3</td><td>0.00</td><td>4/4</td><td>6.8</td><td>1261.5</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>46.1</td><td>4022.5</td><td>0.00</td><td>4/4</td><td>66.8</td><td>8064.3</td><td>0.00</td><td>4/4</td><td>25.7</td><td>4852.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>300.1</td><td>22957.5</td><td>0.00</td><td>4/4</td><td>397.7</td><td>40418.0</td><td>0.00</td><td>4/4</td><td>112.3</td><td>18144.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>739.1</td><td>53330.0</td><td>0.00</td><td>4/4</td><td>1246.0</td><td>92237.3</td><td>0.00</td><td>4/4</td><td>207.3</td><td>35710.0</td><td>0.00</td><td>4/4</td></tr><tr><td>1.2</td><td>2147.0</td><td>64481.0</td><td>2.02</td><td>3/4</td><td>3092.2</td><td>140224.8</td><td>1.09</td><td>3/4</td><td>853.4</td><td>97739.0</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">125</td><td>0.2</td><td>3.5</td><td>34.8</td><td>0.00</td><td>4/4</td><td>4.5</td><td>56.5</td><td>0.00</td><td>4/4</td><td>2.6</td><td>169.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>22.8</td><td>1080.8</td><td>0.00</td><td>4/4</td><td>21.3</td><td>1025.0</td><td>0.00</td><td>4/4</td><td>8.8</td><td>922.3</td><td>0.00</td><td>4/4</td></tr><tr><td>0.6</td><td>228.5</td><td>16414.5</td><td>0.00</td><td>4/4</td><td>199.6</td><td>15685.5</td><td>0.00</td><td>4/4</td><td>114.9</td><td>12250.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.8</td><td>1101.3</td><td>56660.3</td><td>0.01</td><td>4/4</td><td>1576.4</td><td>73335.0</td><td>0.51</td><td>3/4</td><td>608.2</td><td>55224.3</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>2629.9</td><td>80940.0</td><td>1.13</td><td>2/4</td><td>3600.0</td><td>130033.5</td><td>2.46</td><td>0/4</td><td>2480.9</td><td>109520.5</td><td>0.61</td><td>3/4</td></tr><tr><td>1.2</td><td>12.1</td><td>346.5</td><td>0.00</td><td>4/4</td><td>5.9</td><td>92.5</td><td>0.00</td><td>4/4</td><td>14.6</td><td>1806.5</td><td>0.00</td><td>4/4</td></tr><tr><td rowspan="6">150</td><td>0.2</td><td>12.1</td><td>346.5</td><td>0.00</td><td>4/4</td><td>65.2</td><td>3340.3</td><td>0.00</td><td>4/4</td><td>70.9</td><td>7707.0</td><td>0.00</td><td>4/4</td></tr><tr><td>0.4</td><td>114.2</td><td>7598.3</td><td>0.00</td><td>4/4</td><td>872.9</td><td>34955.0</td><td>0.00</td><td>4/4</td><td>1089.3</td><td>45267.5</td><td>0.15</td><td>4/4</td></tr><tr><td>0.6</td><td>1688.2</td><td>69318.3</td><td>0.41</td><td>3/4</td><td>3238.0</td><td>98469.0</td><td>2.10</td><td>1/4</td><td>2939.6</td><td>152951.8</td><td>0.65</td><td>3/4</td></tr><tr><td>0.8</td><td>3369.8</td><td>86787.0</td><td>1.63</td><td>1/4</td><td>50.9</td><td>1520.8</td><td>0.00</td><td>4/4</td><td>36.9</td><td>1890.8</td><td>0.00</td><td>4/4</td></tr><tr><td>1.0</td><td>19.0</td><td>105.8</td><td>0.00</td><td>4/4</td><td>1663.7</td><td>22516.8</td><td>0.41</td><td>3/4</td><td>2242.7</td><td>56680.8</td><td>1.10</td><td>2/4</td></tr><tr><td>1.2</td><td>284.5</td><td>6089.8</td><td>0.01</td><td>4/4</td><td>3600.0</td><td>53259.5</td><td>2.90</td><td>0/4</td><td>3600.0</td><td>83116.8</td><td>2.98</td><td>1/4</td></tr><tr><td>200</td><td>0.2</td><td>3138.6</td><td>46454.0</td><td>1.95</td><td>2/4</td><td>3600.0</td><td>41230.5</td><td>5.98</td><td>0/4</td><td>3600.0</td><td>73966.3</td><td>5.04</td><td>0/4</td></tr><tr><td>0.4</td><td>3600.0</td><td>7867.3</td><td>10.49</td><td>0/4</td><td>3600.0</td><td>41230.5</td><td>5.98</td><td>0/4</td><td>3600.0</td><td>73966.3</td><td>5.04</td><td>0/4</td></tr></tbody></table>
<table><caption>Table 5.5: Computational results for Type 3 instances considering a cardinality budget constraint.</caption><thead><tr><th rowspan="2">Config.<br>|V| B</th><th colspan="4">Total Interdiction</th><th colspan="4">Partial Interdiction</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="3">40</td><td>2</td><td>0.3</td><td>164.9</td><td>0.00</td><td>21/21</td><td>0.0</td><td>25.4</td><td>0.00</td><td>60/60</td></tr><tr><td>3</td><td>6.3</td><td>2220.7</td><td>0.00</td><td>7/7</td><td>0.1</td><td>113.3</td><td>0.00</td><td>60/60</td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td>0.1</td><td>253.1</td><td>0.00</td><td>60/60</td></tr><tr><td rowspan="3">80</td><td>2</td><td>2.0</td><td>562.1</td><td>0.00</td><td>19/19</td><td>0.1</td><td>68.6</td><td>0.00</td><td>60/60</td></tr><tr><td>3</td><td>15.4</td><td>5499.8</td><td>0.00</td><td>4/4</td><td>0.2</td><td>276.4</td><td>0.00</td><td>60/60</td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td>0.7</td><td>940.4</td><td>0.00</td><td>60/60</td></tr><tr><td rowspan="3">120</td><td>2</td><td>3.9</td><td>1803.6</td><td>0.00</td><td>21/21</td><td>0.5</td><td>210.9</td><td>0.00</td><td>60/60</td></tr><tr><td>3</td><td>92.9</td><td>20994.0</td><td>0.00</td><td>5/5</td><td>4.0</td><td>1394.2</td><td>0.00</td><td>60/60</td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td>40.0</td><td>6994.1</td><td>0.00</td><td>60/60</td></tr><tr><td rowspan="3">160</td><td>2</td><td>18.4</td><td>2857.3</td><td>0.00</td><td>20/20</td><td>0.7</td><td>282.9</td><td>0.00</td><td>60/60</td></tr><tr><td>3</td><td>165.6</td><td>26422.4</td><td>0.00</td><td>5/5</td><td>6.3</td><td>2430.3</td><td>0.00</td><td>60/60</td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td>100.6</td><td>12509.9</td><td>0.00</td><td>60/60</td></tr><tr><td rowspan="3">200</td><td>2</td><td>183.4</td><td>5380.6</td><td>0.00</td><td>18/18</td><td>4.8</td><td>373.0</td><td>0.00</td><td>60/60</td></tr><tr><td>3</td><td>490.8</td><td>58323.0</td><td>0.00</td><td>5/5</td><td>68.2</td><td>5544.7</td><td>0.01</td><td>59/60</td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td>157.1</td><td>20855.2</td><td>0.06</td><td>59/60</td></tr></tbody></table>

The results are very similar to total interdiction. For each instance type, instances of up to 100 nodes are solved for every budget with two exceptions. The computation times for instances of 100 nodes already exceed 1000 seconds and keep increasing for larger instances. However, networks of 150 and 200 nodes are still solved in reasonable times for $\eta = 0.2$ and $0.4$. In this case, the BD algorithm is able to solve Type 2 instances beyond the limits of the mathematical models. These limits are instances including 50 nodes.

Type 3 instances were not mentioned in our previous discussion since they are of different size. The results for Type 3 networks are summarized in Table 5.5 and Table 5.6. Table 5.5 presents the experimentation for both total and partial interdiction with a cardinality budget constraint. The results for both types of interdiction with a knapsack constraint are reported in Table 5.6. As stated above, there are 60 different graphs for each size $|V|$. Note that for total interdiction, the instances tested are less than 60. This occurs for two reasons, for several instances the budget defined either is too small to interdict any edge in the MST or is sufficiently large to disconnect the network. This comes from the fact that instances of Type 3 are very sparse Last, all Type 3 graphs have a connectivity number of 4 or less. All instances are trivial when $B = 4$ in the cardinality case or $B$ sufficiently large in the knapsack case. No results are reported if the latter occurs.
## 5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

<table><caption>Table 5.6: Computational results for Type 3 instances considering a knapsack budget constraint.</caption><thead><tr><th rowspan="2">Config.<br>|V|</th><th rowspan="2">η</th><th colspan="4">Total Interdiction</th><th colspan="4">Partial Interdiction</th></tr><tr><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th><th>Time (s)</th><th>Nodes</th><th>Gap (%)</th><th>Opt/Tot</th></tr></thead><tbody><tr><td rowspan="6">40</td><td>0.2</td><td>0.0</td><td>5.2</td><td>0.00</td><td>53/53</td><td>0.0</td><td>2.3</td><td>0.00</td><td>60/60</td></tr><tr><td>0.4</td><td>0.1</td><td>70.4</td><td>0.00</td><td>42/42</td><td>0.0</td><td>14.2</td><td>0.00</td><td>60/60</td></tr><tr><td>0.6</td><td>0.1</td><td>147.3</td><td>0.00</td><td>31/31</td><td>0.1</td><td>55.8</td><td>0.00</td><td>60/60</td></tr><tr><td>0.8</td><td>0.3</td><td>482.1</td><td>0.00</td><td>26/26</td><td>0.1</td><td>118.7</td><td>0.00</td><td>60/60</td></tr><tr><td>1.0</td><td>0.8</td><td>1275.8</td><td>0.00</td><td>14/14</td><td>0.1</td><td>215.5</td><td>0.00</td><td>60/60</td></tr><tr><td>1.2</td><td>1.4</td><td>1789.6</td><td>0.00</td><td>8/8</td><td>0.2</td><td>398.0</td><td>0.00</td><td>60/60</td></tr><tr><td rowspan="6">80</td><td>0.2</td><td>0.1</td><td>48.7</td><td>0.00</td><td>49/49</td><td>0.0</td><td>13.0</td><td>0.00</td><td>60/60</td></tr><tr><td>0.4</td><td>0.4</td><td>464.0</td><td>0.00</td><td>33/33</td><td>0.1</td><td>106.5</td><td>0.00</td><td>60/60</td></tr><tr><td>0.6</td><td>3.1</td><td>2442.9</td><td>0.00</td><td>24/24</td><td>0.2</td><td>337.2</td><td>0.00</td><td>60/60</td></tr><tr><td>0.8</td><td>14.4</td><td>7131.9</td><td>0.00</td><td>16/16</td><td>0.7</td><td>1050.4</td><td>0.00</td><td>60/60</td></tr><tr><td>1.0</td><td>219.0</td><td>28947.0</td><td>0.00</td><td>8/8</td><td>1.5</td><td>1911.0</td><td>0.00</td><td>60/60</td></tr><tr><td>1.2</td><td>36.7</td><td>20205.5</td><td>0.00</td><td>2/2</td><td>4.0</td><td>3776.1</td><td>0.00</td><td>60/60</td></tr><tr><td rowspan="6">120</td><td>0.2</td><td>0.3</td><td>253.3</td><td>0.00</td><td>44/44</td><td>0.1</td><td>59.6</td><td>0.00</td><td>60/60</td></tr><tr><td>0.4</td><td>9.9</td><td>3007.6</td><td>0.00</td><td>30/30</td><td>0.4</td><td>408.6</td><td>0.00</td><td>60/60</td></tr><tr><td>0.6</td><td>168.2</td><td>14366.8</td><td>0.00</td><td>18/18</td><td>1.4</td><td>1484.5</td><td>0.00</td><td>60/60</td></tr><tr><td>0.8</td><td>850.1</td><td>65915.2</td><td>0.14</td><td>7/9</td><td>4.1</td><td>3310.2</td><td>0.00</td><td>60/60</td></tr><tr><td>1.0</td><td>1077.4</td><td>83273.8</td><td>0.37</td><td>3/4</td><td>36.7</td><td>8287.1</td><td>0.00</td><td>60/60</td></tr><tr><td>1.2</td><td>154.3</td><td>81319.0</td><td>0.00</td><td>1/1</td><td>105.0</td><td>16493.9</td><td>0.01</td><td>59/60</td></tr><tr><td rowspan="6">160</td><td>0.2</td><td>0.9</td><td>639.0</td><td>0.00</td><td>39/39</td><td>0.2</td><td>137.3</td><td>0.00</td><td>60/60</td></tr><tr><td>0.4</td><td>79.6</td><td>13213.8</td><td>0.00</td><td>26/26</td><td>2.6</td><td>1539.8</td><td>0.00</td><td>60/60</td></tr><tr><td>0.6</td><td>869.0</td><td>71853.7</td><td>0.05</td><td>13/15</td><td>39.3</td><td>8011.2</td><td>0.00</td><td>60/60</td></tr><tr><td>0.8</td><td>1045.8</td><td>80504.1</td><td>0.50</td><td>5/7</td><td>159.0</td><td>22732.8</td><td>0.02</td><td>59/60</td></tr><tr><td>1.0</td><td>2153.4</td><td>184462.5</td><td>1.08</td><td>1/2</td><td>364.5</td><td>33741.8</td><td>0.11</td><td>55/60</td></tr><tr><td>1.2</td><td></td><td></td><td></td><td></td><td>405.8</td><td>44518.6</td><td>0.19</td><td>55/60</td></tr><tr><td rowspan="6">200</td><td>0.2</td><td>5.4</td><td>2097.7</td><td>0.00</td><td>35/35</td><td>0.4</td><td>279.5</td><td>0.00</td><td>60/60</td></tr><tr><td>0.4</td><td>664.1</td><td>52399.5</td><td>0.06</td><td>23/25</td><td>17.4</td><td>4169.5</td><td>0.00</td><td>60/60</td></tr><tr><td>0.6</td><td>1917.4</td><td>155321.7</td><td>0.47</td><td>10/16</td><td>172.3</td><td>19129.2</td><td>0.07</td><td>58/60</td></tr><tr><td>0.8</td><td>2362.4</td><td>194469.4</td><td>1.20</td><td>3/7</td><td>382.9</td><td>37788.0</td><td>0.18</td><td>55/60</td></tr><tr><td>1.0</td><td>3600.2</td><td>198632.0</td><td>2.59</td><td>0/1</td><td>504.7</td><td>40435.5</td><td>0.37</td><td>53/60</td></tr><tr><td>1.2</td><td></td><td></td><td></td><td></td><td>576.7</td><td>46845.8</td><td>0.50</td><td>52/60</td></tr></tbody></table>

Under a cardinality constraint, the instances considered are solved optimally. Times range from 0.3 in the smallest case to 490.8 seconds. For partial interdiction, only two instances with 200 nodes are not solved. However their gaps are of less than 1%. The remaining instances are solved in less than three minutes. The increased efficiency of the BD algorithm for Type 3 instances is due to the sparsity of the graph. For a $|V| = 100$ nodes network, a Type 1 or Type 2 instance includes $|V|(|V| - 1)/2$ edges whereas a Type 3 instance has a number of edges equal to around 6% of that value.

Table 5.6 presents good results for both total and partial interdiction. Some instances with the largest sizes are not solved, such as 120, 160 and 200 nodes instances with $\eta \ge 0.8$, nevertheless their gaps are of less than 2.59%. Computa-
tional times are reasonable for networks including less than 120 nodes, climbing up to 1077.4 seconds. Resolution time and the search tree size start to increase for graphs with 160 nodes. However, our BD algorithm still solves 84 out of 89 instances of size 160 and 71 out of 84 for networks with 200 nodes in the case of total interdiction. For partial interdiction, the resolution time is at most 576.7 seconds for the largest configuration and only 34 out of 1800 instances are not solved.

A total of 5047 instances out of 6744 originally proposed were tested out. Those 1697 instances were discarded since, as previously indicated, they were trivially solved. We tested 1498 and 3549 instances assuming a cardinality and a knapsack budget constraint, respectively. The revised BD algorithm succeeded to solve 92.39% of the instances for both types of interdiction assuming a cardinality constraint. Whereas for the knapsack case, 95.9% of the instances were optimally solved. Those small percentages of unsolved problems represent the limits of the algorithm, i.e. networks of 100 nodes with $\eta \ge 5$ for the cardinality case and graphs including 125 nodes or more with $B \ge 0.8$ for the knapsack case. The revised BD algorithm is able to efficiently solve all instances defined on sparse graphs when the number of nodes is less than 200. Only a few instances remain unsolved when the graph includes 200 nodes.

## 5.8 Conclusions

Based on the experimentation, the proposed BD algorithm can efficiently solve instances including network of medium to relatively large sizes considering a variety of budgets. The main contribution of our algorithm is its versatility. Most of the research on the MSTI problem presented in Chapter 2 focuses on the $\bar{B}$-most vital edges which is a complicated version of the MSTI problem due to the significantly larger feasible space that a cardinality constraint defines. However, the other versions are also important, since it is not always desired to completely remove a link of the network or the cost of doing so is not necessarily equal for each link. For example, in a war situation, if the enemy wishes to block the use of a segment of road he can destroy it by bombing it with planes, tanks or some other explosive device, or simply send some units to patrol the area. Either of these options clearly does not have the same cost in terms of manpower or resources.
5. BENDERS DECOMPOSITION FOR THE MSTI PROBLEM

The algorithm proposed can handle any of the four version of the MSTI problem.
In addition, it can also solve the partial interdiction version when the augmenta-
tion of an interdicted edge can be fractional, i.e. $c_e + d_e x_e$ where $x_e$ is continuous.
The latter is obtained by solving the root node of the Branch-and-Cut algorithm
only.
# Chapter 6

# Conclusion and Recommendations

## 6.1 Thesis Summary

This thesis addresses the MSTI problem, providing modeling techniques and solution methods. Chapter 3 introduces four original formulations. The first one is a max – min non-linear model. Optimality constraints are developed in order to define a single-level formulation. In turn, the model is linearized using classical linearization techniques and [MSTI<sub>Opt</sub>] is obtained. The second model is derived by considering the dual of the inner problem of the max – min formulation and thus obtaining a single-level linear problem. i.e. [MSTI<sub>Dual</sub>]. A more compact dual formulation of [MSTI<sub>Opt</sub>] is derived by redefining several of its constraints and by following the same dualization procedure. The resulting model is [MSTI<sub>SDual</sub>]. The last formulation [MSTI<sub>Tot</sub>] is only equivalent to the other formulations when total interdiction is considered and only under certain parameter values. Finally, two sets of valid inequalities are developed to strengthen [MSTI<sub>Opt</sub>]. These four models, two versions of [MSTI<sub>Opt</sub>] with the set of valid inequalities and a formulation retrieved from the literature are tested and compared. The results do not allow us to determine a unique efficient formulation. However, the best results are obtained with [MSTI<sub>Opt</sub>], [MSTI<sub>Dual</sub>] and [MSTI<sub>SDual</sub>]. Furthermore, the computational experimentation show that all models start to struggle to solve networks including 20 or more nodes. Therefore, modeling techniques are not sufficient if instances defined on larger networks need to be solved.

Chapter 4 presents a Branch-and-Price algorithm. First, a Dantzig-Wolfe decomposition is applied on [MSTI<sub>SDual</sub>]. The master problem is obtained by
relaxing the integrality constraint. The Restricted Master Problem is defined
on the collection $\hat{\mathcal{P}}$ of interdiction plans defined by the feasible set $\mathcal{X}$. The Re-
stricted Master Problem is solved by column generation, i.e. a column with a
positive reduced cost is found by the pricing problem which is then added to
$\hat{\mathcal{P}}$ and $[RMP(\hat{\mathcal{P}})]$ is reoptimized. The pricing problem turns to be a knapsack
problem with a modified objective function. Furthermore, the sub-problem is
strengthen with a new original family of constraints. The iterative procedure of
solving $[RMP(\hat{\mathcal{P}})]$ and the pricing problem is repeated until no column with posi-
tive reduced cost is found. A Branch-and-Price algorithm is a Branch-and-Bound
framework where at each node of the search tree the Restricted Master Problem
is solved by column generation. An integer solution can be calculated for each
generated column during the column generation procedure. The latter allows us
not to check if integer solutions are found during the branching and only update
the incumbent with the solutions provided by the columns. The computational
experimentation shows that this approach is inefficient with respect to the math-
ematical formulations since much better computation times where obtained even
for the small instances.

The revised Benders Decomposition presented in Chapter 5 is the main con-
tribution of this thesis. The MSTI problem is decomposed in a master problem
and a sub-problem. The master problem is defined over a restricted collection
of trees. The objective of the master problem is to find the optimal interdiction
plan that maximizes the weight of these spanning trees simultaneously. The sub-
problem is parameterized with the solution of the master problem which, when
solved, generates a new tree that is added to the collection of trees. The classical
BD algorithm solves iteratively the master problem and sub-problem. In this
thesis, we proposed a revised BD algorithm embedded in a CPLEX framework.
The master problem is implemented in CPLEX, then the sub-problem is solved
via control callbacks to dynamically add new trees. Moreover, the constraints
of the master problem are lifted and a second family of valid inequalities is also
defined to strengthen the master problem.

Different test instances were generated to test the BD algorithm. The differ-
ences between the instances are in the density or the edge weights. The results
obtained with the revised BD algorithm are much better of those of Chapters 3
and 4. In the total interdiction case, instances of up to 75 nodes can be solved
fairly efficiently for both the cardinality and knapsack budget assumptions. Under the same assumptions, 100 nodes instances with a small budget are solved as well but with a significant resolution time. The BD algorithm behaves even more efficiently in the knapsack case. Instances of up to 125 nodes are solved. Instances of 150 and 200 are also solved but the efficiency start to decrease when the budget increases. Finally, a final instance set retrieved from the literature was as well efficiently solved by the algorithm proposed.

The three solution approaches presented in this manuscript, i.e. mathematical formulations, the B&P algorithm and the revised Benders Decomposition are conceived to handle the four configurations of type of interdiction and budget constraints. Whereas in the literature, the case of partial interdiction has been neglected. Therefore, the research of this thesis addresses a generalization of the MSTI problem.

## 6.2 Future Research

Two families of constraints are considered in our BD algorithm: the optimality constraints which are mandatory in order to have a well-defined problem and the set covering constraints which are meant to strengthen the MP. More families of constraints could be added to the MP with this same goal. The so-called Critical Edge Set constraints (Wei et al. (2021)) are a stronger variation of the set covering constraints. Each critical edge set constraint represents a subset of edges whose elements are part of several spanning trees. Thus, interdicting one edge in the critical edge set means the interdiction of one edge of all those spanning trees. The latter implies to have less constraints with less variables than those of the set covering constraints. The next step of our research is to include this new family of constraints in our algorithm. However, separating these inequalities from a fractional solution is NP-hard. Wei et al. (2021) propose a separation algorithm from integer solutions nevertheless it remains fairly more complex than separating the set covering constraints. A first step is to incorporate this algorithm in the lazy callbacks to test its efficiency. If positive results are obtained, the second step is to design an algorithm to separate a fraction of critical edge set constraints from fractional solutions.
A direct extension of our work is to consider the MSTI problem with multiple interdiction resources. Two assumptions can be made: an edge needs different resources to be interdicted or an edge can be interdicted by one of the different resources. The modifications in our formulations and in the BD algorithm concern only the budget constraint which have to be modified to handle multiple resources.

The research of this manuscript concerns the MSTI problem where the inter-
dictor has the capacity of interdicting any edge of the network. After interdiction,
the network operator reacts optimally to this interdiction. This problem is mod-
eled as a particular case of a bilevel problem, i.e. a max – min problem with
the same objective function. The edge reinforcement variant of the MFI and SPI
problems were studied in different occasions as stated in Chapter 2. To the best of
our knowledge, the MSTI problem with edge reinforcement has not been studied
in the literature. This variant is normally modeled as a two-player game where
the network operator plays twice. Constrained by a budget, he moves first by
selecting a subset of edges that will be reinforced, i.e. edges that the interdictor
cannot interdict. Then, the interdictor proceeds to interdict the network. Lastly,
the network operator computes the MST after the network has been interdicted.
The resulting formulation is a min – max – min problem with the same objective
function. Our formulations can be easily adapted to this variant.

The bi-objective MSTI problem is once more a variant that, to the best of
our knowledge, has not been studied in the literature. The bi-objective variant
optimizes simultaneously the maximization of the weight MST and the minimiza-
tion of the cost of the interdiction strategy. The optimal solution of the MSTI
problem is only one of the solutions of the Pareto front of the bi-objective MSTI
problem. Thus, this variant is a generalization of the MSTI problem.

Sensibility analyses of real networks is a direct application of our research.
Gas pipelines, electric grids or transportation lines are examples that up to some
extent can be modeled as spanning trees. They connect cities, neighborhoods
or regions in order to provide services or deliver products. These networks can
be subject to interdiction by malicious agents which can alter their proper func-
tioning. A path to follow for the near future is to test out the mathematical
formulations and the revised BD decomposition on these type of networks in or-
der to locate the critical links. The latter will be used by the network operator to
prepare countermeasures in case of failures or to reinforce these links to prevent them from being tampered with.
# 6. CONCLUSION AND RECOMMENDATIONS
References

ACHTERBERG, T. (2007). *Constraint integer programming*. Ph.D. thesis, Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften. 71

AFSHARI RAD, M. & KAKHKI, H.T. (2017). Two extended formulations for cardinality maximum flow network interdiction problem. *Networks*, **69**, 367–377. 13

AKÇAY, Y., LI, H. & XU, S.H. (2007). Greedy algorithm for the general multidimensional knapsack problem. *Annals of Operations Research*, **150**, 17–29. 63

ALTNER, D.S., ERGUN, O. & UHAN, N.A. (2010). The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability. *Operations Research Letters*, **38**, 33–38. 13

BAÏOU, M. & BARAHONA, F. (2008). A linear programming approach to increasing the weight of all minimum spanning trees. *Networks*, **52**, 227–234. 3, 16

BALL, M.O., GOLDEN, B.L. & VOHRA, R.V. (1989). Finding the most vital arcs in a network. *Operations Research Letters*, **8**, 73–76. 13, 20

BAYCIK, N.O., SHARKEY, T.C. & RAINWATER, C.E. (2018). Interdicting layered physical and information flow networks. *IISE Transactions*, **50**, 316–331. 19

BAYRAK, H. & BAILEY, M.D. (2008). Shortest path network interdiction with asymmetric information. *Networks*, **52**, 133–140. 20
BAZGAN, C., TOUBALINE, S. & VANDERPOOTEN, D. (2012). Efficient determination of the *k* most vital edges for the minimum spanning tree problem. *Computers & Operations Research*, **39**, 2888–2898. iii, 3, 16, 20, 21, 22, 23, 42, 62

BEDROSIAN, S. (1964). Generating formulas for the number of trees in a graph. *Journal of the Franklin Institute*, **277**, 313–326. 79

BENDERS, J. (1962). Partitioning procedures for solving mixed-variables programming problems. *Numerische mathematik*, **4**, 238–252. 74

BERTSIMAS, D., NASRABADI, E. & ORLIN, J.B. (2016). On the power of randomization in network interdiction. *Operations Research Letters*, **44**, 114–120. 20

BROWN, G., CARLYLE, M., SALMERÃŞN, J. & WOOD, K. (2006). Defending critical infrastructure. *Interfaces*, **36**, 530–544. 18

BROWN, G.G., CARLYLE, W.M., SALMERÃŞN, J. & WOOD, K. (2005). *Analyzing the Vulnerability of Critical Infrastructure to Attack and Planning Defenses*, 102–123. INFORMS. 20

BURCH, C., CARR, R., KRUMKE, S., MARATHE, M., PHILLIPS, C. & SUNDBERG, E. (2003). *A Decomposition-Based Pseudoapproximation Algorithm for Network Flow Inhibition*, vol. 22, 51–68. Kluwer Academic Publishers. 20

CALUDE, C., MARCUS, S. & TEVY, I. (1979). The first example of a recursive function which is not primitive recursive. *Historia Mathematica*, **6**, 380–384. 15

CHURCH, R.L., SCAPARRA, M.P. & MIDDLETON, R.S. (2004). Identifying critical infrastructure: The median and covering facility interdiction problems. *Annals of the Association of American Geographers*, **94**, 491–502. 20

COOK, W.J., CUNNINGHAM, W.H., PULLEYBLANK, W.R. & SCHRIJVER, A. (1997). *Combinatorial Optimization*. John Wiley & Sons, Ltd. 24

CORLEY, H. & SHA, D.Y. (1982). Most vital links and nodes in weighted networks. *Operations Research Letters*, **1**, 157–160. 13, 17
CORLEY, H.W. & CHANG, H. (1974). Finding the *n* most vital nodes in a flow network. *Management Science*, **21**, 362–364. 17, 20

CORMICAN, K.J., MORTON, D.P. & WOOD, R.K. (1998). Stochastic network interdiction. *Operations Research*, **46**, 184–197. 18, 20

DELGADILLO, A., ARROYO, J.M. & ALGUACIL, N. (2010). Analysis of electric grid interdiction with line switching. *IEEE Transactions on Power Systems*, **25**, 633–641. 18

DEMPE, S. (2002). *Foundations of bilevel programming*. Springer Science & Business Media. 7

DEMPE, S., KALASHNIKOV, V., PÃREZ-VALDÃES, G.A. & KALASHNYKOVA, N. (2015). *Bilevel Programming Problems*. Energy Systems, Springer Berlin Heidelberg. 8

DINITZ, M. & GUPTA, A. (2013). *Packing Interdiction and Partial Covering Problems*, vol. 7801, 157–168. Springer Berlin Heidelberg. 20

ETESAMI, S.R. & BAŞAR, T. (2019). Dynamic games in cyber-physical security: An overview. *Dynamic Games and Applications*, **9**, 884–913. 19

FREDERICKSON, G.N. & SOLIS-OBA, R. (1999). Increasing the weight of minimum spanning trees. *Journal of Algorithms*, **33**, 244–266. 3, 16, 20

FULKERSON, D.R. & HARDING, G.C. (1977). Maximizing the minimum source-sink path subject to a budget constraint. *Mathematical Programming*, **13**, 116–118. 13, 20

FURINI, F., LJUBIĆ, I., MARTIN, S. & SAN SEGUNDO, P. (2019). The maximum clique interdiction problem. *European Journal of Operational Research*, **277**, 112–127. 20

GOLDEN, B. (1978). A problem in network interdiction. *Naval Research Logistics Quarterly*, **25**, 711–713. 14

HELD, H., HEMMECKE, R. & WOODRUFF, D.L. (2005a). A decomposition algorithm applied to planning the interdiction of stochastic networks. *Naval Research Logistics*, **52**, 321–328. 18
HELD, H., HEMMECKE, R. & WOODRUFF, D.L. (2005b). A decomposition algorithm applied to planning the interdiction of stochastic networks. *Naval Research Logistics*, **52**, 321–328. 20

HEMMECKE, R., SCHULTZ, R. & WOODRUFF, D.L. (2003). *Interdicting Stochastic Networks with Binary Interdiction Effort*, vol. 22, 69–84. Kluwer Academic Publishers. 18, 20

HSU, L.H., JAN, R.H., LEE, Y.C. & HUNG, C.N. (1991). Finding the most vital edge with respect to minimum spanning tree in weighted graphs. *Information Processing Letters*, **39**, 5. 3, 15, 20

ISRAELI, E. & WOOD, R.K. (2002). Shortest-path network interdiction. *Networks: An International Journal*, **40**, 97–111. 2, 14, 17, 20, 77

IWANO, K. & KATOH, N. (1993). Efficient algorithms for finding the most vital edge of a minimum spanning tree. *Information Processing Letters*, **48**, 21–213. 15

JABARZARE, Z., ZOLFAGHARINIA, H. & NAJAFI, M. (2019). Dynamic interdiction networks with applications in illicit supply chains. *Omega*. 18

JAN, R.H., HSU, L.H. & LEE, Y.Y. (1992). The most vital edges with respect to the number of spanning trees in two-terminal series-parallel graphs. *BIT*, **32**, 403–412. 3

JANJARASSUK, U. & LINDEROTH, J. (2008). Reformulation and sampling to solve a stochastic network interdiction problem. *Networks*, **52**, 120–132. 18

KHACHIYAN, L., GURVICH, V. & ZHAO, J. (2006). *Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction*, vol. 3967, 221–234. Springer Berlin Heidelberg, Berlin, Heidelberg. 17

KHACHIYAN, L., BOROS, E., BORYS, K., ELBASSIONI, K., GURVICH, V., RUDOLF, G. & ZHAO, J. (2008). On short paths interdiction problems: Total and node-wise limited interdiction. *Theory of Computing Systems*, **43**, 204–233. 17, 20
KLEINERT, T., LABBÉ, M., LJUBIĆ, I. & SCHMIDT, M. (2021). A survey on mixed-integer programming techniques in bilevel optimization. *EURO Journal on Computational Optimization*, **9**, 8

KONRAD, R.A., TRAPP, A.C., PALMBACH, T.M. & BLOM, J.S. (2017). Overcoming human trafficking via operations research and analytics: Opportunities for methods, models, and applications. *European Journal of Operational Research*, **259**, 733–745. 19

LACHHWANI, K. & DWIVEDI, A. (2018). Bi-level and multi-level programming problems: Taxonomy of literature review and research issues. *Archives of Computational Methods in Engineering*, **25**, 847–877. 8

LIANG, W. & SHEN, X. (1997). Finding the *k* most vital edges in the minimum spanning tree problem. *Parallel Computing*, **23**, 1889–1907. 15, 20

LIM, C. & SMITH, J.C. (2007). Algorithms for discrete and continuous multi-commodity flow network interdiction problems. *IIE Transactions*, **39**, 15–26. 20

LIN, K.C. & CHERN, M.S. (1993). The most vital edges in the minimum spanning tree problem. *Information Processing Letters*, **45**, 25–31. 15, 20

LUBORE, S.H., RATLIFF, H. & SICILIA, G. (1971). Determining the most vital link in a flow network. *Naval Research Logistics Quarterly*, **18**, 497–502. 12

MAGNANTI, T.L. & WOLSEY, L.A. (1995). Optimal trees. *Handbooks in operations research and management science*, **7**, 503–615. 22

MALAVIYA, A., RAINWATER, C. & SHARKEY, T. (2012). Multi-period network interdiction problems with applications to city-level drug enforcement. *IIE Transactions*, **44**, 368–380. 18

MALIK, K., MITTAL, A.K. & GUPTA, S.K. (1989). The most vital *k* arcs in the shortest path problem. *Operation Research Letters*, **8**, 5. 13

MARTIN, R.K. (1991). Using separation algorithms to generate mixed integer model reformulations. *Operations Research Letters*, **10**, 119–128. iii, 4, 21, 24, 25, 44, 54
MCMASTERS, A.W. & MUSTIN, T.M. (1970). Optimal interdiction of a supply network. *Naval Research Logistics Quarterly*, **17**, 261–268. 12

MORTON, D.P. (2010). Stochastic network interdiction. *Wiley encyclopedia of operations research and management science*. 18

MORTON, D.P., PAN, F. & SAEGER, K.J. (2007). Models for nuclear smuggling interdiction. *IIE Transactions*, **39**, 3–14. 2, 20

PAN, F. (2005). *Stochastic network interdiction: models and methods*. The University of Texas at Austin. 18

PAN, F., CHARLTON, W.S. & MORTON, D.P. (2003). *A Stochastic Program for Interdicting Smuggled Nuclear Material*, vol. 22, 1–19. Kluwer Academic Publishers. 20

PAY, B.S., MERRICK, J.R.W. & SONG, Y. (2019). Stochastic network interdiction with incomplete preference. *Networks*, **73**, 3–22. 20

PHILLIPS, C.A. (1993). The network inhibition problem. In *Proceedings of the twenty-fifth annual ACM symposium on Theory of computing*, 776–785. 12

POWELL, R. (2007). Defending against terrorist attacks with limited resources. *American Political Science Review*, **101**, 527–541. 19

RAHMANIANI, R., CRAINIC, T.G., GENDREAU, M. & REI, W. (2017). The benders decomposition algorithm: A literature review. *European Journal of Operational Research*, **259**, 801–817. 74

RATLIFF, H.D., SICILIA, G.T. & LUBORE, S. (1975). Finding the *n* most vital links in flow networks. *Management Science*, **21**, 531–539. 12

ROCCO S., C.M. & RAMIREZ-MARQUEZ, J.E. (2010). A bi-objective approach for shortest-path network interdiction. *Computers & Industrial Engineering*, **59**, 232–240. 18, 20

ROCCO S., C.M., EMMANUEL RAMIREZ-MARQUEZ, J. & SALAZAR A., D.E. (2010). Bi and tri-objective optimization in the deterministic network interdiction problem. *Reliability Engineering & System Safety*, **95**, 887–896. 18
ROYSET, J.O. & WOOD, R.K. (2007). Solving the bi-objective maximum-flow network-interdiction problem. *INFORMS Journal on Computing*, **19**, 175–184.
18

SADEGHI, S., SEIFI, A. & AZIZI, E. (2017). Trilevel shortest path network interdiction with partial fortification. *Computers & Industrial Engineering*, **106**, 400–411.
18, 20

SALMERON, J., WOOD, K. & BALDICK, R. (2004). Analysis of electric grid security under terrorist threat. *IEEE Transactions on power systems*, **19**, 905–912.
2, 19

SALMERON, J., WOOD, K. & BALDICK, R. (2009). Worst-case interdiction analysis of large-scale electric power grids. *IEEE Transactions on Power Systems*, **24**, 96–104.
18

SCAPARRA, M.P. & CHURCH, R.L. (2008). A bilevel mixed-integer program for critical infrastructure protection planning. *Computers & Operations Research*, **35**, 1905–1923.
20

SCHRIJVER, A. (1998). *Theory of linear and integer programming*. John Wiley & Sons.
58

SCHRIJVER, A. (2003). *Combinatorial optimization: polyhedra and efficiency*, vol. 24. Springer Science & Business Media.
26

SEFAIR, J.A. & SMITH, J.C. (2016). Dynamic shortest-path interdiction. *Networks*, **68**, 315–330.
20

SHEN, H. (1999). Finding the *k* most vital edges with respect to minimum spanning tree. *Acta Informatica*, **36**, 405–424.
16

SULLIVAN, K.M., MORTON, D.P., PAN, F. & COLE SMITH, J. (2014). Securing a border under asymmetric information. *Naval Research Logistics (NRL)*, **61**, 91–100.
18

TANERGÜÇLÜ, T., KARAŞAN, O.E., AKGÜN, İ. & KARAŞAN, E. (2019). Radio communications interdiction problem under deterministic and probabilistic jamming. *Computers & Operations Research*, **107**, 200–217.
19
TSAI, J., YIN, Z., KWAK, J.Y., KEMPE, D., KIEKINTVELD, C. & TAMBE, M. (2010). Urban security: Game-theoretic resource allocation in networked domains. In *Twenty-Fourth AAAI Conference on Artificial Intelligence*. 2

VICENTE, L.N. & CALAMAI, P.H. (1994). Bilevel and multilevel programming: A bibliography review. *Journal of Global Optimization*, **5**, 291–306. 8

VON STACKELBERG, H. (1934). Marktform und gleichgewicht; hill, r.; bazin, d.; urch, l., translators. 7

WEI, N., WALTEROS, J.L. & PAJOUH, F.M. (2021). Integer programming formulations for minimum spanning tree interdiction. *INFORMS Journal on Computing*, **33**, 1461–1480. 3, 20, 77, 87, 99

WOLLMER, R. (1964). Removing arcs from a network. *Operations Research*, **12**, 934–940. 2, 12, 20

WOLLMER, R.D. (1963). *Some methods for determining the most vital link in a railway network*. Rand Corporation. 12

WOOD, R.K. (1993). Deterministic network interdiction. *Mathematical and Computer Modelling*, **17**, 1–18. 2, 12, 13, 17, 18, 20

WU, X. & CONEJO, A.J. (2017). An efficient tri-level optimization model for electric grid defense planning. *IEEE Transactions on Power Systems*, **32**, 2984–2994. 18

WU, Y., CHEN, Z., GONG, H., FENG, Q., CHEN, Y. & TANG, H. (2021). Defender-Attacker-Operator: Tri-level game-theoretic interdiction analysis of urban water distribution networks. *Reliability Engineering & System Safety*, **214**. 18

YATES, J. & SANJEEVI, S. (2013). A length-based, multiple-resource formulation for shortest path network interdiction problems in the transportation sector. *International Journal of Critical Infrastructure Protection*, **6**, 107–119. 20

YUAN, W., ZHAO, L. & ZENG, B. (2014). Optimal power grid protection through a defender-attacker-defender model. *Reliability Engineering & System Safety*, **121**, 83–89. 18
YUAN, W., WANG, J., QIU, F., CHEN, C., KANG, C. & ZENG, B. (2016). Robust optimization-based resilient distribution network planning against natural disasters. *IEEE Transactions on Smart Grid*, **7**, 2817–2826. 2

YUAN, Y., LI, Z. & REN, K. (2011). Modeling load redistribution attacks in power systems. *IEEE Transactions on Smart Grid*, **2**, 382–390. 2

ZHUANG, J. & BIER, V.M. (2007). Balancing terrorism and natural disasters-defensive strategy with endogenous attacker effort. *Operations Research*, **55**, 976–991. 19
Résumé Etendu

La prévention est un aspect important pour tout système pour en assurer le bon fonctionnement. Les transports, les livraisons ou la production sont des pro-
cessus où la prévention joue un rôle essentiel. Les catastrophes naturelles et les perturbations causées par l'homme sont des exemples de ce qui peut provoquer un dysfonctionnement de ces systèmes, ce qui, dans la plupart des cas, conduit à un fonctionnement indésirable, voire à l'absence totale de fonctionnement. Par ex-
emple, une entreprise doit savoir comment réagir lorsque la panne d'une machine compromet sa chaîne logistique. Elle doit prévoir une absence de production, des délais, des pertes de profits, entre autres. Une analyse des opérations dans un cadre d'optimisation est indispensable.

La modélisation de ces situations dans le cadre d'un Jeu d'Interdiction (JI)
est l'un des moyens les plus pratiques de garantir les meilleurs résultats. Un JI
cherche à identifier une stratégie qui cause le plus de dommages aux opérations
d'un processus. Il est alors possible de décider d'investir dans des mesures de
sécurité supplémentaires aux points critiques ou de déployer des procédures al-
ternatives une fois que le pire scénario que les opérations peuvent subir est connu.

Un JI implique deux entités non coopératives qui interagissent l'une avec l'autre. La première entité, appelée *l'interdicteur*, cherche à perturber les processus d'optimisation ou les paramètres de la seconde entité, appelée le *défenseur*. Dans le cadre normal d'un JI, l'interdicteur agit en premier, puis le défenseur réagit en toute connaissance des actions de l'interdicteur. L'interdicteur peut modifier les ressources du défenseur voire les détruire afin d'aggraver l'objectif du défenseur.

Les JI ont fait l'objet d'une forte attention en raison de leur grande application pratique. Les opérations militaires, la structure critique des réseaux électriques, le
maintien de l'ordre et la prévention des catastrophes naturelles sont quelques-uns des domaines d'applications des JIs.

L'un des problèmes les plus étudiés est celui du chemin le plus fiable. On modélise une situation dans laquelle un individu se déplace à travers un réseau entre une origine et un destination. Chaque lien du réseau est associé à une probabilité de le traverser sans être détecté. L'objectif de cet individu est de traverser le réseau sans être détecté pendant que l'interdicteur tente de l'intercepter. La détection se fait en interdisant des liens de telle sorte que les probabilités associées soient diminuées. Ce problème doit son nom au fait que le défenseur tente de trouver un chemin qui maximise ses chances d'arriver Àã destination.

Un autre problème étudié est celui de l'Interdiction de Flux Maximum (IFM). Le défenseur souhaite calculer le flux maximum dans un réseau où des capacités sont imposés. L'objectif de l'interdicteur est de minimiser le flux maximum du réseau en éliminant certains de ses arcs. Cependant, l'interdicteur a des ressources limitées pour le faire. Une application directe du problème de l'IFM est apparue dans la dégradation des flux de drogue en Amérique du Sud.

Le problème d'Interdiction du Plus Court Chemin (IPCC) est un des problèmes qui a reçu le plus d'attention. Le plus court chemin dans un réseau entre les nœuds source et destination est calculé par le défenseur tandis que l'interdicteur, contraint par un budget, perturbe le réseau en modifiant le poids des arcs. Les formulations proposées peuvent gérer une interdiction partielle, c'est-à-dire une augmentation du poids des arcs ou une destruction complète de l'arc, c'est-à-dire une interdiction totale.

Le problème de l'Interdiction de l'Arbre Couvrant Minimal (IACM) est défini de façon similaire aux deux problèmes précédents. L'interdicteur cherche à al louer ses ressources dans le but de modifier la topologie du réseau dans lequel le défenseur calcule l'arbre couvrant minimal de façon à ce que le poids de ce dernier subisse le plus grand incrément. Le nombre maximum d'arêtes que l'interdicteur peut interdire est imposé par une contrainte budgétaire. La contrainte budgétaire peut être définie comme une contrainte de cardinalité, le poids d'interdiction de chaque arête étant alors égal, ou comme contrainte de sac à dos, les poids d'interdiction étant différents. Le premier travail sur le problème IACM est un cas particulier où l'interdicteur élimine une seule arête du réseau. Les travaux ont été ensuite étendus au cas où l'interdicteur élimine un nombre arbitraire d'arêtes.
Différentes formulations mathématiques ont été présentées. Ces modèles tirent
avantage de la structure du problème IACM. Les articles concernant le problème
IACM fournissent une diversité de modèles et de méthodes de résolution, mais ils
considèrent tous certains cas particuliers. Par exemple, il existe un algorithme ef-
ficace qui résout le problème IACM lorsque l'interdicteur élimine un nombre fixe
d'arêtes. La variante d'interdiction partielle, c'est-à-dire lorsque l'interdicteur
augmente seulement le poids des arêtes, a reçu peu d'attention. Des algorithmes
qui résolvent cette variante existent mais une étude sur les formulations mathé-
matiques est manquante.

A notre connaissance, aucun algorithme n'a été explicitement conçu pour
résoudre le problème IACM général. Cette thèse propose des modèles et des al-
gorithmes pour une généralisation du problème IACM. Cette dernière est obtenue
en considérant les deux types d'interdiction, l'interdiction totale et l'interdiction
partielle. De plus, l'interdicteur peut être limité par une contrainte de budget,
modélisée comme une contrainte de sac à dos. La contrainte de cardinalité, qui
est un cas particulier, est également considérée. Le travail présenté dans cette
thèse est structuré comme suit.

Une revue de la littérature sur les problèmes IFM, IPCC et IACM est présentée
au chapitre 2. Nous commençons par introduire le concept de jeux de Stackelberg
et d'optimisation à deux niveaux. Ensuite, leur relation avec le JI est expliquée.
Une formulation générale des problèmes d'interdiction de réseau déterministe est
proposée. La littérature relative aux trois problèmes de réseau considérés est
discutée. La discussion se concentre principalement sur les cas particuliers qui
ont été traités et les différents algorithmes qui ont été conçus. Les variantes et
les applications de chacun des problèmes de réseau sont également examinées.

Le chapitre 3 présente sept modèles mathématiques pour le problème IACM.
Une première formulation venant de la littérature est rappelée. Un deuxième
modèle original basé sur une formulation linéaire du problème ACM est présenté.
Cette dernière formulation est un problème non linéaire de max – min. Elle
est donc reformulée et linéarisée pour obtenir un problème linéaire à un seul
niveau. De plus, des inégalités valides sont développées pour renforcer le mod-
èle. Deux formulations supplémentaires sont proposées. Elles sont basées sur
le problème dual du problème non linéaire max – min. Toutes les formulations
traitent les deux types d'interdiction. Un dernier modèle qui ne considère que le
cas d'interdiction totale est présenté. Des instances sont générées comme celles
de la littérature et utilisées pour comparer les efficacités de nos formulations.

Le problème IACM est ensuite résolu par un algorithme de Branch-and-Price
dans le chapitre 4. La formulation la plus compacte définie au chapitre 3 est util-
isée pour définir le problème maître restreint et le problème de pricing. Ce dernier
est obtenu en appliquant une décomposition de Dantzig-Wolfe. Une famille de
contraintes qui excluent les stratégies d'interdiction non pertinentes est dévelop-
pée et ajoutée au problème de pricing. Ensuite, un algorithme de génération de
colonnes intégré dans un schéma Branch-and-Bound est présenté. Les expériences
numériques sont réalisées sur l'ensemble d'instances générées au chapitre 3.

La principale contribution de cette thèse est présentée au chapitre 5. Un
algorithme de décomposition de Benders est développé pour traiter le prob-
lème IACM. Le problème IACM est décomposé en un Problème Maître (PM)
et un sous-problème. Une famille de contraintes pour le PM, appelée contraintes
d'optimalité, est introduite et liftée. Une famille d'inégalités valides est égale-
ment proposée pour renforcer la relaxation linéaire du PM. Le sous-problème,
paramétré par la solution du PM, consiste uniquement en la détermination d'un
ACM. L'algorithme de décomposition de Benders est implémenté à l'aide d'un
solveur commercial. Le PM est résolu à l'optimalité une seule fois et le sous-
problème est résolu dans des méthodes définies par l'utilisateur qui sont données
au solveur. Quatre types d'instances sont générés. Les instances se différencient
les unes des autres par le poids des arêtes et la densité du réseau. L'algorithme
est évalué pour chacune des quatre configurations possibles en fonction du type
d'interdiction et des contraintes budgétaires.

Le manuscrit se termine au chapitre 6 par les conclusions générales de la thèse.
Les limites et les travaux futurs sont également discutés.
# Models and Algorithms for the Minimum Spanning Tree Interdiction Problem

## ABSTRACT

In this thesis, we study the Minimum Spanning Tree Interdiction (MSTI) problem. This problem is a two-player game between a network operator and an interdictor. The former aims to determine a Minimum Spanning Tree (MST) in a network. Constrained by a budget, the latter seeks to change the network topology to increase the weight of a MST. Two types of interdiction are considered: total and partial interdiction. A total interdicted edge is considered absent while the weight of a partial interdicted edge is augmented by a predefined amount. The interdictor's budget is modeled as a cardinality, each edge has the same interdiction weight, or knapsack constraint, the interdiction weights might be different. Seven mathematical formulations for the MSTI problem are devised. They proved to be efficient on small and medium-size graphs. A Branch-and-Price algorithm and a Benders Decomposition algorithm are designed for larger graphs. In addition, valid inequalities are proposed to strengthen the models and improve the efficiency of the proposed methods. Instances including up to 200 nodes and 19900 edges are solved to optimality.

**Keywords:** minimum spanning tree, network interdiction problems, interdiction problems, Benders decomposition, branch-and-price, integer programming, operations research, graph theory, algorithms.

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

## RÉSUMÉ

Dans cette thèse, nous étudions le problème de l'Interdiction de l'Arbre Couvrant Minimal (IACM). Ce problème est un jeu à deux joueurs entre un opérateur de réseau et un interdicteur. Le premier détermine un Arbre Couvrant Minimal (ACM) dans un réseau. Limité par un budget, le second cherche à changer la topologie du réseau pour augmenter le poids de l'ACM. Deux types d'interdiction sont considérés : l'interdiction totale et l'interdiction partielle. Une arête totalement interdite est considérée comme absente tandis que le poids d'une arête partiellement interdite est augmentée d'une quantité predéfinie. Le budget de l'interdicteur est modélisé par une contrainte de cardinalité, chaque arête a le même poids d'interdiction, ou une contrainte de sac à dos, les poids d'interdiction peuvent être différents. Sept formulations mathématiques du problème IACM ont été élaborées. Elles se sont avérées efficaces pour des graphes de petite et moyenne taille. Un algorithme de type "Branch-and-Price" et un algorithme basé sur la décomposition de Benders ont été conçus pour les graphes de plus grande taille. En outre, des inégalités valides sont proposées pour renforcer les modèles et améliorer les performances des algorithmes. Des instances de 200 sommets et 19900 arêtes ont ainsi pu être résolues optimalement.

**Mots-clés:** arbre couvrant de poids minimal, problèmes d'interdiction, problèmes d'interdiction de réseaux, decomposition de Benders, "branch-and-price", programmation en nombres entiers, recherche operationnelle, théorie des graphes, algorithmes.
<figure><img src="image_6.png" /></figure>