1; \label{changeone} \\
\sum\limits_{i : \bar{y_i} = 1}^{n} x_i \geq 1. \label{interdone}\end{aligned}$$

These cuts impose that at least one variable $x_i$ in solution vector $\bar{x}$ must be discarded (constraint ) and at least one item selected by the follower in solution $\bar{y}$ must be interdicted (constraint ). We solve $CRIT_2(c)$ with two more constraints and apply the same procedure until $z(CRIT_2(c)) \geq z^*$ or the problem becomes infeasible. At the end of Step 2, the optimal BKP solution $(x^*, y^*)$ is returned (Line \[returnOpt\]).

\[algo:ExAp\]

$x^* = x'$, $y^* = y'$, $z^*= z(NCR)$; \[endNoC\] [  ]{}

$(x^*, y^*)$; \[endCritItems\]

\[FeasGammaSol\] $\hat{x} \leftarrow$ solve $CRIT_2(c_i)$; $\hat{y} \leftarrow$ solve $KP(\hat{x})$; $x^* = \hat{x}$, $y^* = \hat{y}$, $z^*= z(KP(\hat{x}))$;

\[endFeasGammaSol\]

\[solveSub\]

$(x^*, y^*)$;

$x^* = \bar{x}$, $y^* = \bar{y}$, $z^*= z(KP(\bar{x}))$;

\[endsolveSub\] \[returnOpt\]

Computational results {#sec:ComRes}
=====================

All tests were performed on an Intel i7 CPU @ 2.4 GHz with 8 GB of RAM. The code was implemented in the C++ programming language. The ILP solver used along the steps of the algorithm is CPLEX 12.6.2.

The parameters of the ILP solver were set to their default values. The BKP instances with $n=35,40,45,50,55$ are generated in [@CaCarLoWo16] as follows. Profits $p_i$ and weights 