---
abstract: 'We consider the Bilevel Knapsack with Interdiction Constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower’s profits. The presence of two decision levels makes this problem very difficult to solve in practice: the current state-of-the-art algorithms can solve to optimality instances with 50-55 items at most. We derive effective lower bounds and present a new exact approach that exploits the structure of the induced follower’s problem. The approach successfully solves all benchmark instances within one second in the worst case and larger instances with up to 500 items within 60 seconds.'
address:
- |
    Dipartimento di Ingegneria Gestionale e della Produzione, Politecnico di Torino,\
    Corso Duca degli Abruzzi 24, 10129 Torino, Italy,\
    [{federico.dellacroce, rosario.scatamacchia}@polito.it ]{}
- 'CNR, IEIIT, Torino, Italy'
author:
- Federico Della Croce
- Rosario Scatamacchia
title: A new exact approach for the Bilevel Knapsack with Interdiction Constraints
---

Bilevel Knapsack with Interdiction Constraints ,Exact approach ,Bilevel programming

Introduction {#sec:Intro}
============

In the recent years, a growing attention has been centered to multilevel programming. This emerging field considers optimization problems with a hierarchal structure where many decision makers sequentially operate to reach conflicting objectives. Each agent takes decisions that may affect objectives and decisions of the agents at lower levels. At the same time, the latter decisions impact on the objectives of the agents at upper levels. Hierarchal contexts arise in many real-life applications in supply chains, energy sector, logistics and telecommunication networks among others. The presence of many decision levels makes these problems very challenging to solve.\
The most relevant research in the field has been pursued for bilevel optimization where two agents, denoted as a leader and a follower, play a Stackelberg game ([@St52]). In this game, the leader takes the first decision and then the follower reacts taking into account the leader’s strategy. Eventually, the agents receive a pay-off which depends on both leader’s and follower’s choices. The goal is typically to find a strategy for the leader that optimizes his own objective. Two standard assumptions are considered in a Stackelberg game: *perfect knowledge*, that is each agent knows the problem solved by the other agent; *rationale behavior*, namely each agent has no interest in deviating from his own objective.\
Bilevel optimization considers Mixed-Integer Bilevel Linear Programs (MIBLP) where both the leader and the follower solve a combinatorial optimization problem with linear objective function and constraints and with either continuous or integer variables. The first generic Branch and Bound approach for MIBLP was provided in [@BaMo90]. Branch and Cut schemes were introduced in [@DeRa09], [@Den11]. Further approaches were proposed in [@CaMa15; @FiLjMoSi16; @XuWa14]. An improved generic MIBLP solver has been recently proposed in [@FiLjMoSi17]. We refer to [@FiLjMoSi17] and the references therein for an overview on MIBLP solvers and related applications.\
In this paper, we consider the Bilevel Knapsack with Interdiction Constraints (BKP), as introduced in [@Den11]. The problem is an extension of the classic 0-1 Knapsack Problem (KP) (see monographs [@KePfPi04] and [@MarTot90]) formulated as a Stackelberg game. More precisely, the leader and the follower choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower’s profits.\
In [@CaCarLoWo13] it is shown that BKP is $\Sigma_{2}^p$-complete in the polynomial hierarchy complexity. Essentially, BKP cannot be formulated as a single level problem unless the polynomial hierarchy collapses (as also pointed out in [@CaCarLoWo16]). This makes the problem even more difficult to solve than an NP-Complete problem. We refer to [@Je85] for an introduction on polynomial hierarchy.\
One of the best performing algorithms for BKP is given in [@CaCarLoWo16]. The algorithm, denoted as CCLW, relies on the dualization of the continuous relaxation of the follower’s problem and on iteratively computing upper bounds for the problem until a stopping criterion applies. The approach is motivated by the lack of significant lower bounds for the problem. Algorithm CCLW solves to optimality instances with 50 items within a CPU time limit of 3600 seconds, running out of time in instances with 55 items only. Very recently, an improved branch-and-cut algorithm has been given in [@FiLjMoSi18]. The proposed approach manages to solve to optimality all benchmark instances in [@CaCarLoWo16], requiring at most a computation time of about 85 seconds in an instance with 55 items. However, no computational evidence is provided in [@FiLjMoSi18] about the performance of the derived algorithm on larger instances. We also mention the work of [@FiMoSiEJOR18] where a heuristic approach is proposed for BKP and for other interdiction games. Other bilevel knapsack problems have been tackled in the literature. We mention the work in [@BrHaMa13] where the leader cannot interdict items but modifies the follower’s capacity. In [@ChZh13], the leader can modify the follower’s objective function only. As discussed in [@CaCarLoWo16], these knapsack problems are easier to handle than BKP. Recently, a polynomial algorithm has been provided in [@CaLoMa18] for the BKP variation where the follower solves a continuous knapsack problem.\
Our contribution for BKP is twofold. First, we derive effective lower bounds based on mathematical programming. Second, we present a new exact approach that exploits the induced follower’s problem and the derived lower bounds. The proposed approach shows up to be very effective successfully solving all benchmark literature instances provided in [@CaCarLoWo16] within few seconds of computation. Moreover, our algorithm manages to solve to optimality instances with up to 500 items within a CPU time limit of 60 seconds.

The paper is organized as follows. In Section \[sec:themodel\], the bilevel linear programming formulation of the problem is introduced. In Section \[sec:LB\], we discuss the lower bounds for BKP. We outline the proposed exact solution approach in Section \[sec:ExaApp\] and discuss the computational results in Section \[sec:ComRes\]. Section \[sec:Concl\] provides some concluding remarks.

Notation and problem formulation {#sec:themodel}
================================

In BKP a set of $n$ items and two knapsacks are given. Each item $i$ $(=1,\dots, n)$ has associated a profit $p_i > 0$ and a weight $w_i > 0$ for the follower’s knapsack and a weight $v_i > 0$ for the leader’s knapsack. Leader and follower have different knapsack capacities denoted by $C_u$ and $C_l$, respectively. Quantities $p_i$, $v_i$, $w_i$ $(i=1,\dots, n)$, $C_u$, $C_l$ are assumed to be integer, with $v_i < C_u$ and $w_i < C_l$ for all $i$. To avoid trivial instances, it is also assumed that $\sum\limits_{i=1}^{n} v_{i} > C_u$ and $\sum\limits_{i=1}^{n} w_{i} > C_l$. We introduce $0/1$ variables $x_i$ $(i=1, \dots,n)$ equal to one if the leader selects items $i$ and $0/1$ variables $y_i$ equal to one if item $i$ is chosen by the follower. BKP can be modeled as follows:

$$\begin{aligned}
\text{min}\quad & \sum\limits_{i=1}^{n} p_{i}y_{i} \label{eq:ObjL}\\
    \text{subject to}\quad
    & \sum\limits_{i=1}^{n} v_{i}x_{i} \leq C_u \label{eq:capL}\\
    & x_{i} \in\{0,1\} \qquad i= 1,\dots,n \label{eq:varDefX} \\
    \text{where $y_1, \dots, y_n$ solve} \nonumber\\
    \text{the follower's problem:}\quad
    \text{max}\quad & \sum\limits_{i=1}^{n} p_{i}y_{i} \label{eq:ObjF}\\
    \text{subject to}\quad
    & \sum\limits_{i=1}^{n} w_{i}y_{i} \leq C_l \label{eq:capF}\\
    &y_{i} \leq 1 - x_{i} \qquad i= 1,\dots,n \label{eq:Interd} \\
    &y_{i} \in\{0,1\} \qquad i= 1,\dots,n \label{eq:varDefY} \end{aligned}$$

The leader’s objective function minimizes the profits of the follower through the interdiction constraints . These constraints ensure that each item $i$ can be selected by the follower, i.e. $y_i \leq 1$, only if the item is not interdicted by the leader, i.e. $x_i = 0$. Constraint represents the leader’s capacity constraint. The objective function maximizes the follower’s profits and constraint represents the follower’s capacity constraint. Constraints and define the domain of the variables.

The optimal solution value of model - is denoted by $z^*$. The optimal solution vectors of variables $x_i$ and $y_i$ are respectively denoted by $x^*$ and $y^*$. Notice that in model - there always exists an optimal solution for the leader which is maximal, namely where items are included in the leader’s knapsack until there is no enough capacity left. Let us now recall the optimal solution of the continuous relaxation of a standard KP, namely the follower’s model - without constraints and constraints replaced by inclusion in $[0, 1]$. Under the assumption $\sum\limits_{i=1}^{n} w_{i} > C_l$, this solution has the following structure. Consider the sorting of the items by non-increasing ratios of profits over weights:

$$\label{eq:SortByEff}
\frac{p_1}{w_1} \geq \frac{p_2}{w_2} \geq \dots \geq \frac{p_n}{w_n}.$$

According to this order, items $j = 1,2,\dots$ are inserted into the knapsack as long as $\sum\limits_{k=1}^{j} w_{k} \leq C_l$. The first item $s$ which cannot be fully packed is commonly denoted in the knapsack literature as the *split* item (or *break*/*critical* item). The optimal solution of the KP linear relaxation is given by setting $y_j = 1$ for $j= 1,\dots,s-1$, $y_j = 0$ for $j= s+1,\dots,n$ and $y_s = (C_l - \sum\limits_{j=1}^{s-1} w_j)/w_s$. The solution with items $1, \dots, (s-1)$ is a feasible solution for KP and is commonly denoted as the *split solution*. In the remainder of the paper, we assume the ordering of the items . We denote by $KP(x)$ the follower’s knapsack problem induced by a leader’s strategy encoded in vector $x$, i.e. a knapsack problem with item set $$S:=\{i: x_i = 0, x_i \in x \}.$$ We also denote by $KP^{LP}(x)$ the corresponding Linear Programming (LP) relaxation. If $\sum_{i \in S} w_i > C_l$, we define the *critical* item $c$ of $KP^{LP}(x)$ as the last item with a strictly positive value in its optimal solution. Thus, we have $y_c \in (0, 1]$ and a corresponding split solution with profit $$\label{eq:SplitSol}
\sum\limits_{i \in  S: i < c} p_i = \sum\limits_{i = 1}^{c-1} p_i(1 - x_i)$$ which constitutes a feasible solution for $KP(x)$. Notice that we denote by $z(M)$ the optimal solution value of any given mathematical model $M$.

Computing lower bounds on BKP {#sec:LB}
=============================

Consider the optimal solution vector $x^*$. In the induced follower’s knapsack problem $KP(x^*)$ with item set $S$, two cases can occur: either there is no critical item in $KP^{LP}(x^*)$, namely $\sum_{i \in S} w_i  \leq C_l$, or one critical item exists, namely $\sum_{i \in S} w_i > C_l$. The first case can be easily handled by considering that the follower will pack all items not interdicted by the leader. This case is discussed in Section \[NOcrit\].\
In the second case, we derive effective lower bounds on BKP that constitute the main ingredient of the exact approach presented in Section \[sec:ExaApp\]. Since we don’t know a priori the leader’s optimal solution $x^*$, we proceed by guessing the critical item of $KP^{LP}(x^*)$, namely we formulate an Integer Linear Programming (ILP) model where we impose that a given item $c$ must be critical and evaluate the profit of the corresponding split solution. We consider binary variables $k_j$ $(j= 1, \dots, w_c)$ associated with the weight contribution of the critical item and introduce the following model (denoted as $CRIT_1(c)$).

$$\begin{aligned}
\text{min}\quad & \sum\limits_{i=1}^{c-1} p_{i}(1-x_i) \label{eq:ObjCRIT}\\
    \text{subject to}\quad
    & \sum\limits_{i=1}^{n} v_{i}x_{i} \leq C_u \label{eq:capLeadCRIT}\\
    & \sum\limits_{i=1}^{c-1} w_{i}(1-x_{i}) + \sum\limits_{j=1}^{w_c} jk_j = C_l \label{eq:capFollCRIT}\\
    & \sum\limits_{j=1}^{w_c} k_j = 1 \label{eq:capSOSCRIT}\\
    & x_c = 0 \label{eq:NotInterCRIT}\\
    & x_{i} \in\{0,1\} \qquad i= 1,\dots,n \label{eq:varDefXCRIT} \\
    & k_{j} \in\{0,1\} \qquad j= 1,\dots,w_c \label{eq:varDefKCRIT} \end{aligned}$$

The objective function minimizes the value of the split solution. Constraint represents the leader’s capacity constraint. Constraints and ensure that item $c$ is critical as it is the last item packed, with a weight in the interval $[1, w_c]$. Constraint indicates that item $c$ can be critical only if it is not interdicted by the leader. Constraints and indicate that all variables are binary. We can state the following proposition.

\[firstProp\] If there exists a critical item $c$ in $KP^{LP}(x^*)$, then $z(CRIT_1(c))$ is a valid lower bound on $z^*$.

Under the assumption that item $c$ is critical in $KP^{LP}(x^*)$, the optimal BKP solution $x^*$ constitutes a feasible solution for model $CRIT_1(c)$. Let denote by $z_1$ the corresponding solution value that coincides with the value of the split solution in $KP(x^*)$. Since the follower maximizes the profits in $KP(x^*)$ obtaining a solution with a value greater than (or equal to) the one of the split solution, we have $z_1 \leq z^*$. But this means that there exists an optimal solution of model $CRIT_1(c)$ such that $z(CRIT_1(c)) \leq z_1$ which implies a lower bound on $z^*$.

The previous proposition already provides a first significant lower bound for the problem. However, following the reasoning in the proof of Proposition \[firstProp\], we remark that improved bounds on $z^*$ can be derived by considering any feasible solution for $KP(x^*)$ that might be obtained by removing (adding) items that were not interdicted by the leader and that were selected (not selected) by the split solution, provided that the follower capacity is not exceeded. Indeed, this corresponds to removing tuples of items $i \in [1,c-1]: x_i=0$ and/or to adding tuples of items $i \in [c,n]: x_i=0$ from the split solution without exceeding the follower capacity.

Notice that, the state-of-the-art algorithms for KP, *Minknap* ([@Pis97]) and *Combo* ([@MarPisTot99]) consider that in general only few items with ratio $p_i/w_i$ close to that of the critical item change their values in an optimal solution with respect to the values taken in the split solution. These items constitute the so-called *core* of the knapsack. *Minknap* and *Combo* start with the computation of the split solution and an expanding core initialized with the critical item only. Then, the algorithms iteratively enlarge the core by evaluating both the removal of items from the split solution and the addition of items after the critical item. The empirical evidence illustrates that an optimal (or close to be optimal) KP solution is typically found after few iterations.

We cannot precisely characterize the features of these exact algorithms by a set of constraints within an ILP model, but we can mimic the same algorithmic reasoning by considering subsets of the items set $c-\delta,...,c+\delta$ including the critical item $c$ for any given core size $2\delta+1$. In each subset, the items $i: i \leq c-1$ are removed from the split solution, while the items $j: j \geq c$ are added to the solution. Correspondingly, the initial profit and weight of the split solution are modified by subtracting the profits and the weights of the removed items and by summing up the profits and the weights of the added items.

Then, for any given subset $\tau$ of the items set $c-\delta,...,c+\delta$, let $p^{\tau}$ and $w^{\tau}$ be the overall profit (namely the value of the improvement upon the split solution) and weight contributions of the items in $\tau$, namely: $$\begin{aligned}
p^{\tau} = -\sum\limits_{i \in \tau: i < c} p_i + \sum\limits_{j \in \tau: j \geq c} p_j; \label{pT}\\
w^{\tau} = -\sum\limits_{i \in \tau: i < c} w_i + \sum\limits_{j \in \tau: j \geq c} w_j. \label{wT}\end{aligned}$$

A subset $\tau$ with $p^\tau \leq 0$ is not considered since it does not improve upon the split solution. Instead, an improving subset with $p^\tau > 0$ is feasible only if $w^{\tau} \leq w_c$ and all items in $\tau$ are not interdicted by the leader. In that case, by keeping the notation of model $CRIT_1(c)$, an improvement $\pi$ can be determined if the following constraint is added:

$$\label{TupleCons}
\pi \geq p^\tau(\sum\limits_{j = \max\{1;w^\tau\}}^{w_c} k_j - \sum\limits_{i \in \tau} x_i). 
$$

Correspondingly, a new model can be generated by introducing a non-negative variable $\pi$ that carries the maximum additional profit to the split solution value provided by any of the additional constraints (\[TupleCons\]) indicated above. These constraints, denoted as $\mathcal{F}(\pi, x, k)$, link variable $\pi$ to variables $x_i$ and $k_j$. The model (denoted as $CRIT_2(c)$) is as follows.\
[$\quad CRIT_2(c)$:]{} $$\begin{aligned}
\text{min}\quad & \sum\limits_{i=1}^{c-1} p_{i}(1-x_i) + \pi \label{eq:ObjCRIT2}\\
    \text{subject to}\quad
    & \mathcal{F}(\pi,x,k) \label{genConstonPi2} \\
    & \eqref{eq:capLeadCRIT}, \eqref{eq:varDefKCRIT} \tag*{} \\ 
    & \pi \geq 0 \label{eq:varDefPi}  \end{aligned}$$

Clearly, due to the addition of constraints in $\mathcal{F}(\pi,x,k)$, for any $c$ we have $z(CRIT_1(c)) \leq  z(CRIT_2(c))$. Notice that, in all these additional constraints, only items which will not be interdicted by the leader can be packed and the follower’s capacity constraint is not violated. We denote as *proper* any set $\mathcal{F}(\pi,x,k)$ that satisfies both conditions. After the set $\mathcal{F}(\pi, x, k)$ is built, variable $\pi$ will carry the maximum profit obtainable in addition to the profit of the split solution.

\[secTh\] If $KP^{LP}(x^*)$ admits a critical item $c$ and model $CRIT_2(c)$ has a proper set $\mathcal{F}(\pi, x, k)$, then $z(CRIT_2(c)) \leq z^*$.

Since model $CRIT_2(c)$ considers feasible solutions for $KP(x^*)$, the inequality holds by applying the same argument of Proposition \[firstProp\].

A new exact approach for BKP {#sec:ExaApp}
============================

Overview
--------

We propose an exact algorithm for BKP that considers the possible existence of a critical item in $KP^{LP}(x^*)$ and exploits the bounds provided by model $CRIT_2(c)$. The approach involves two main steps. In the first step, the possible non-existence of a critical item is first evaluated. Then, the approach assumes the existence of a critical item and identifies a set of possible candidate items. For each candidate item $c$ and a parameter $\delta$ to identify the core size, model $CRIT_2(c)$ is built by considering several subsets of additional constraints (\[TupleCons\]). Then the linear relaxation $CRIT_2^{LP}(c)$ is solved, where the integrality constraints and are replaced by inclusion in $[0,1]$.

The feasible problems $CRIT_2^{LP}(c)$ are sorted by increasing optimal value so as to identify an order of the most promising subproblems to explore. A limited number of feasible BKP solutions is also computed in this step.

In the second step, each relevant subproblem is explored by constraint generation until the subproblem can be pruned. An optimal BKP solution is eventually returned. The approach takes as input five parameters $\alpha$, $\beta$, $\delta$, $\mu$, $\gamma$ and relies on an ILP solver along its steps. We discuss the steps of the algorithm in the following. The corresponding pseudo code is then provided.

Step 1 {#TheStep1}
------

### Handling the possible non-existence of a critical item {#NOcrit}

We first consider the case where there does not exist a critical item in $KP^{LP}(x^*)$. Thus, the follower will select all available items which are not interdicted by the leader and an optimal solution of BKP is found by solving the following problem $NCR$.\
$$\begin{aligned}
\text{min}\quad & \sum\limits_{i=1}^{n} p_{i}(1-x_{i})  \label{eq:ObjFirst}\\
    \text{subject to}\quad
    & \sum\limits_{i=1}^{n} v_{i}x_{i} \leq C_u \label{eq:capLFirst}\\
    & \sum\limits_{i=1}^{n} w_{i}(1-x_{i}) \leq C_l \label{eq:capFWmax}\\
& x_{i} \in\{0,1\} \qquad i= 1,\dots,n \label{eq:varDefXFirst}\end{aligned}$$ If problem $NCR$ is feasible, let denote by $x'$ the related optimal solution representing the leader’s strategy. The corresponding follower’s solution is denoted by $y'$, with $y'_i = 1 - x'_i$ $(i=1, \dots, n)$. The current best solution $(x^*, y^*)$ with value $z^*$ (which will be optimal at the end of the algorithm) is initialized accordingly (Lines \[NoC\]-\[endNoC\] of the pseudo code).

### Identifying the relevant critical items {#criticalitems}

We now assume that there exists a critical item $c$ in $KP^{LP}(x^*)$ (Lines \[CritItems\]-\[endCritItems\]) and estimate the first and last possible items $l$ and $r$ that can be critical according to ordering . For item $l$ we have $$\begin{aligned}
\label{comL}
l := \min \{ j: \sum\limits_{i=1}^{j} w_{i} \geq C_l\}. \end{aligned}$$ All items $1, \dots, (l-1)$ cannot in fact be critical even without the leader’s interdiction. For the last item $r$, we first compute the maximum weight of the follower that can be interdicted by the leader (similarly as in [@CaCarLoWo16]) by solving the following problem (denoted by $LW$).\
$$\begin{aligned}
\text{max}\quad & \sum\limits_{i=1}^{n} w_{i}x_{i}  \label{eq:ObjWmax}\\
    \text{subject to}\quad
    & \sum\limits_{i=1}^{n} v_{i}x_{i} \leq C_u \label{eq:capLWmax}\\
& x_{i} \in\{0,1\} \qquad i= 1,\dots,n \label{eq:varDefXWmax}\end{aligned}$$ Item $r$ is defined as $$\begin{aligned}
\label{comR}
r := \min \{ j: \sum\limits_{i=1}^{j} w_{i} \geq C_l + z(LW)\}. \end{aligned}$$ Since from we have$\sum\limits_{i=1}^{r} w_{i}(1 -x_i) \geq C_l$ for any leader’s strategy, all items from $(r+1)$ to $n$ cannot be critical.

### Building models $CRIT_2(c)$ {#BuildMod}

For each candidate critical item $c \in  [l,r]$, we formulate model $CRIT_2(c)$ by constructing a proper set $\mathcal{F}(\pi, x, k)$ as follows. Consider the subsets involving items in the interval $[c - \delta, c + \delta]$. Even for small value of $\delta$, the number of subsets can be very large. Hence, in order to limit the number of constraints in $\mathcal{F}(\pi, x, k)$, we propose a different strategy that greedily selects the subsets according to the procedure denoted as $ComputeTuples$ and sketched below. For a given value of $\delta$, we consider the interval of items $[a, b]$, with $a=\max\{1;c-\delta\}$ and $b=\min\{c+\delta;n\}$. Starting by the empty set, we enumerate at most $\alpha$ “backward” sets with items $(c-1), \dots, a$ in increasing order of size. Each set has a profit and weight equal to the sum of profits and weights of the included items. We also compute at most $\beta$ “forward” sets with items $c, \dots, b$ in increasing order of size and with a weight not superior to the maximum weight of a backward set. This in order to exclude forward sets having less chance to be combined with a backward set.

Then the backward (resp. forward) sets are ordered by increasing (resp. decreasing) profit. We combine each backward set with a forward set and generate a tuple $\tau$. If $p^{\tau} > 0$ and $w^{\tau} \leq w_c$, we add constraint to $\mathcal{F}(\pi, x, k)$. We continue adding constraints to $\mathcal{F}(\pi, x, k)$ until their number is superior to an input parameter $\mu$. If not previously included, we also add to set $\mathcal{F}(\pi, x, k)$ the constraint $\pi \geq p_c k_{w_c}$ which handles the possible adding of the critical item to the split solution if the residual capacity is equal to $w_c$.

\[algo:Tuples\]

.

Then we solve models $CRIT_2^{LP}(c)$ for each $c \in [l,r]$ and order the models by increasing optimal value so as to have an order of most promising subproblems to explore. If for the first subproblem we have $z(CRIT_2^{LP}(c)) \geq z^*$, an optimal BKP solution is already certified (Line \[endCritItems\] of the pseudo code).

### Computing feasible BKP solutions {#heursol}

According to the previous order of subproblems, we compute BKP feasible solutions by considering the first $\gamma$ subproblems (Lines \[FeasGammaSol\]-\[endFeasGammaSol\]). For a given item $c$, we solve model $CRIT_2(c)$ obtaining a solution $\hat{x}$.\
If $z(CRIT_2(c)) < z^*$, we solve the induced follower’s problem $KP(\hat{x})$ with optimal solution $\hat{y}$ and update the current best solution if $z(KP(\hat{x})) < z^*$.

Step 2 {#TheStep2}
------

This step consider all relevant (ordered) suproblems $CRIT_2(c)$. For each subproblem, we first test for standard variables fixing and then each subproblem is explored by means of a constraint generation approach (Lines \[solveSub\]-\[endsolveSub\]).

### Fixing variables in subproblems {#fixvar}

For a given problem $CRIT_2^{LP}(c)$, denote the optimal values of variables $x_{i}$ and $k_j$ by $x_{i}^{LP}$ and $k_j^{LP}$ respectively. Let $r_{x_i}$ and $r_{k_j}$ be the reduced costs of non basic variables in the optimal solution of $CRIT_2^{LP}(c)$. We apply then standard variable-fixing techniques from Integer Linear Programming: if the gap between the best feasible solution available and the optimal solution value of the continuous relaxation solution is not greater than the absolute value of a non basic variable reduced cost, then the related variable can be fixed to its value in the continuous relaxation solution. Thus, the following constraints are added to $CRIT_2(c)$:

$$\begin{aligned}
& \forall\, i: |r_{x_i}| \geq z^* - z(CRIT_2^{LP}(c)) , \quad x_i = x_i^{LP}; \label{eq:rxi}\\
& \forall\, j: |r_{k_j}| \geq  z^* - z(CRIT_2^{LP}(c)), \quad k_j = k_j^{LP}.\label{eq:rkj}\end{aligned}$$

### Solving subproblems {#solvesub}

For each open subproblem $CRIT_2(c)$, we first solve $CRIT_2(c)$ obtaining a solution $\bar{x}$. If the corresponding objective value is lower than the current best feasible solution value, we solve $KP(\bar{x})$ with solution $\bar{y}$ and if an improving solution is found, the current best solution is updated, as in Section \[heursol\]. Then, we add to $CRIT_2(c)$ constraints

$$\begin{aligned}
\sum\limits_{i : \bar{x_i} = 0}^{n} x_i + \sum\limits_{i : \bar{x_i} = 1}^{n} (1-x_i) \geq 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 $w_i$ of the follower and weights $v_i$ of the leader are integers randomly distributed in $[1,100]$: 10 instances are generated for each value of $n$. The follower’s capacity $C_l$ is set to $\lceil (INS/11)\sum_i^{n}w_i\rceil$ where $INS$ $(=1, \dots, 10)$ denotes the instance identifier. The leader’s capacity is randomly selected in the interval $[C_l - 10; C_l + 10]$.

We first tested our approach on these 50 benchmark instances. After some preliminary computational tests, we chose the following parameter entries for our approach: $\alpha = 100 $, $\beta = 100$, $\delta = 10$, $\mu = 150$, $\gamma = 2$. The corresponding results are presented in Table \[tab:CPUTime1\]. For each instance, we report the optimal solution value, the CPU time to obtain an optimal solution and the number of subproblems explored in Step 2. The last column also reports the number of times model $CRIT_2(c)$ is solved along the two steps.

Algorithm CCLW in [@CaCarLoWo16] solves all instances with 50 items within a CPU time limit of 3600 seconds but runs out of time limit in instances 55-3, 55-4. Algorithm in [@FiLjMoSi18] solves all benchmark instances, requiring at most a computation time of about 85 seconds for solving instance 55-3. As the results in the table illustrate, the proposed exact approach outperforms the competing algorithms, successfully solving to optimality each instance in at most 1 second (this maximum CPU time is reached in instance 55-3) with an average of 0.2 seconds. Also, the number of subproblems explored in Step 2 and the number of models $CRIT_2(c)$ solved are very limited. Notice that the tests in [@CaCarLoWo16] and in [@FiLjMoSi18] were carried out on different but comparable machines in terms of hardware specifications.

[|rr||\*[1]{}[c|]{}\*[1]{}[c|]{}\*[1]{}[c|]{}\*[1]{}[c|]{}]{}

& & Optimal & CPU & \# Subprob. & \# $CRIT_2(\cdot)$\
*n* & *INS* & Value & Time & in Step 2 & solved\

35 & 1 & 279 & 0.11 & 3 & 5\
& 2 & 469 & 0.36 & 0 & 2\
& 3 & 448 & 0.43 & 2 & 4\
& 4 & 370 & 0.15 & 2 & 4\
& 5 & 467 & 0.14 & 2 & 4\
& 6 & 268 & 0.05 & 0 & 0\
& 7 & 207 & 0.04 & 0 & 0\
& 8 & 41 & 0.03 & 0 & 0\
& 9 & 80 & 0.03 & 0 & 0\
& 10 & 31 & 0.02 & 0 & 0\
40 & 1 & 314 & 0.16 & 1 & 3\
& 2 & 472 & 0.33 & 1 & 3\
& 3 & 637 & 0.70 & 4 & 6\
& 4 & 388 & 0.16 & 0 & 2\
& 5 & 461 & 0.11 & 0 & 2\
& 6 & 399 & 0.05 & 0 & 0\
& 7 & 150 & 0.04 & 0 & 0\
& 8 & 71 & 0.04 & 0 & 0\
& 9 & 179 & 0.03 & 0 & 0\
& 10 & 0 & 0.01 & 0 & 0\
45 & 1 & 427 & 0.21 & 3 & 5\
& 2 & 633 & 0.36 & 1 & 3\
& 3 & 548 & 0.61 & 3 & 5\
& 4 & 611 & 0.27 & 1 & 3\
& 5 & 629 & 0.22 & 2 & 4\
& 6 & 398 & 0.06 & 0 & 0\
& 7 & 225 & 0.04 & 0 & 0\
& 8 & 157 & 0.04 & 0 & 0\
& 9 & 53 & 0.03 & 0 & 0\
& 10 & 110 & 0.02 & 0 & 0\
50 & 1 & 502 & 0.35 & 5 & 7\
& 2 & 788 & 0.52 & 1 & 3\
& 3 & 631 & 0.28 & 2 & 4\
& 4 & 612 & 0.22 & 0 & 2\
& 5 & 764 & 0.18 & 0 & 2\
& 6 & 303 & 0.06 & 0 & 0\
& 7 & 310 & 0.05 & 0 & 0\
& 8 & 63 & 0.04 & 0 & 0\
& 9 & 234 & 0.04 & 0 & 0\
& 10 & 15 & 0.03 & 0 & 0\
55 & 1 & 480 & 0.37 & 3 & 5\
& 2 & 702 & 0.31 & 1 & 3\
& 3 & 778 & 1.11 & 8 & 10\
& 4 & 889 & 0.56 & 5 & 7\
& 5 & 726 & 0.09 & 0 & 0\
& 6 & 462 & 0.07 & 0 & 0\
& 7 & 370 & 0.06 & 0 & 0\
& 8 & 387 & 0.05 & 0 & 0\
& 9 & 104 & 0.04 & 0 & 0\
& 10 & 178 & 0.03 & 0 & 0\

The computational tests in both [@CaCarLoWo16] and [@FiLjMoSi18] are limited to instances with 55 items. We then tested larger instances with $n=100, 200, 300, 400, 500$ according to the generation scheme in [@CaCarLoWo16]. For each value of $n$ and $INS$, we generated 10 instances for a total of 500 instances. For these large instances, we set the parameters of our algorithm to the following values: $\alpha = 500 $, $\beta = 500$, $\delta = 20$, $\mu = 1000$, $\gamma = 5$. It is pointed out in [@CaCarLoWo16] that in instances with $INS \geq 5$ the follower’s capacity constraint is expected to be inactive for any maximal leader’s interdiction strategy. This makes these instances easy to solve. Our computational experiments confirm this trend also on larger instances: the proposed algorithm solves each instance with $n$ from 100 to 500 and $INS \geq 5$ in at most 8 seconds without never invoking Step 2. In the light of this consideration, we report in the following Table \[tab:CPUTime2\] only the results for instances with $INS \leq 4$.

[|rr|\*[1]{}[c|]{}\*[2]{}[c|]{}\*[2]{}[c|]{} \*[2]{}[c|]{}]{}

& & & & &\
& & & & &\
*n* & *INS* & \#Opt & Average & Max & Average & Max&Average&Max\
100 & 1 & 10 & 2.1 & 3.0 & 0.7 & 2.0 & 4.8 & 7.0\
& 2 & 10 & 5.6 & 9.9 & 3.8 & 9.0 & 8.9 & 16.0\
& 3 & 10 & 4.3 & 6.4 & 2.5 & 7.0 & 7.5 & 12.0\
& 4 & 10 & 2.3 & 4.5 & 0.7 & 4.0 & 5.2 & 9.0\
200 & 1 & 10 & 5.3 & 10.7 & 3.4 & 7.0 & 8.9 & 17.0\
& 2 & 10 & 7.8 & 12.2 & 5.0 & 9.0 & 10.1 & 14.0\
& 3 & 10 & 9.1 & 13.6 & 6.4 & 12.0 & 12.3 & 19.0\
& 4 & 10 & 6.0 & 8.6 & 3.5 & 8.0 & 8.3 & 13.0\
300 & 1 & 10 & 6.4 & 8.3 & 3.9 & 8.0 & 9.0 & 13.0\
& 2 & 10 & 15.5 & 37.4 & 7.2 & 14.0 & 13.5 & 23.0\
& 3 & 10 & 14.0 & 17.7 & 10.9 & 15.0 & 16.8 & 24.0\
& 4 & 10 & 8.7 & 13.2 & 4.9 & 11.0 & 9.9 & 16.0\
400 & 1 & 10 & 8.8 & 12.3 & 6.7 & 10.0 & 12.8 & 17.0\
& 2 & 10 & 15.2 & 18.7 & 9.1 & 12.0 & 15.1 & 20.0\
& 3 & 10 & 19.0 & 30.5 & 12.0 & 17.0 & 18.8 & 32.0\
& 4 & 10 & 12.6 & 16.5 & 8.4 & 23.0 & 13.8 & 30.0\
500 & 1 & 10 & 11.9 & 18.2 & 7.6 & 13.0 & 13.1 & 20.0\
& 2 & 10 & 20.6 & 26.6 & 11.0 & 20.0 & 17.0 & 25.0\
& 3 & 10 & 21.2 & 25.8 & 12.7 & 17.0 & 17.8 & 22.0\
& 4 & 10 & 15.1 & 17.1 & 4.7 & 8.0 & 9.8 & 13.0\

The results in the table are summarized in terms of average, maximum CPU time and number of optimal solutions obtained with a time limit of 60 seconds. Similarly as in Table \[tab:CPUTime1\], we also report the average and maximum number of subproblems explored in Step 2, and the average and maximum number of times model $CRIT_2(c)$ is solved. The results illustrate the effectiveness of our approach. All instances are solved to optimality requiring 37.4 seconds at most for an instance with 300 items. The number of subproblems handled by Step 2 is in general limited, reaching a maximum value of 23 (in an instance with 400 items). Also, the number of models $CRIT_2(c)$ to be solved is generally limited and never superior to 32. We finally point out that the number of constraints - added to each subproblem is also limited: in the tested instances, the while–loop of Step 2 is executed 8 iterations at most.

Acknowledgments {#acknowledgments .unnumbered}
---------------

We thank M. Carvalho for providing us the benchmark instances of [@CaCarLoWo16].

Concluding remarks {#sec:Concl}
==================

We proposed for the Bilevel Knapsack with Interdiction Constraints a new exact approach which outperforms the state-of-the-art algorithms available in the literature. The algorithm relies on a new lower bound derived for the problem, which is improved by exploiting the expected features of an optimal solution of the classical knapsack problem. In future research, it will be worthy on one hand to investigate different correlations between profits and weights of the items in the follower’s knapsack problem and on the other hand to which extent the proposed approach could be generalized to other bilevel optimization problems.

[1]{}

Brotcorne, L., Hanafi, S., Mansi, R.: One-level reformulation of the bilevel Knapsack problem using dynamic programming. Discrete Optimization. 10, 1–10 (2013)

Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.: A Complexity and Approximability Study of the Bilevel Knapsack Problem. Proceedings of IPCO 2013. Volume 7801 of LNCS, 98–109 (2013)

Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.: Bilevel Knapsack with Interdiction Constraints. INFORMS Journal on Computing. 28, 319–333 (2016)

Caramia, M., Mari, R.: Enhanced exact algorithms for discrete bilevel linear problems. Optimization Letters, 9, 1447–1468 (2015)

Carvalho, M., Lodi, A., Marcotte, P.: A polynomial algorithm for a continuous bilevel knapsack problem. Operations Research Letters. 46, 185–188 (2018)

Chen, L., Zhang, G.: Approximation algorithms for a bi-level knapsack problem. Theoretical Computer Science. 497, 1–12 (2013)

DeNegre, S.: Interdiction and discrete bilevel linear programming. PhD thesis. Lehigh University (2011)

DeNegre, S., Ralphs, T.K.: A Branch-and-cut Algorithm for Integer Bilevel Linear Programs. Operations Research and Cyber-Infrastructure, voleme 47 of Operations Research/Computer Science Interfaces, 65–78 (2009)

Fischetti, M., Ljubi[ć]{}, I., Monaci, M., Sinnl, M.: A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs. Operations Research. 65, 1615–1637 (2017)

Fischetti, M., Ljubi[ć]{}, I., Monaci, M., Sinnl, M.: Interdiction Games and Monotonicity, with Application to Knapsack Problems. INFORMS Journal on Computing, to appear (2018), technical report available at: <https://homepage.univie.ac.at/ivana.ljubic/research/publications/interdiction_games_and_monotonicity.pdf>

Fischetti, M., Ljubi[ć]{}, I., Monaci, M., Sinnl, M.: On the use of intersection cuts for bilevel optimization. Mathematical Programming. 172, 77–103 (2018)

Fischetti, M., Monaci, M., Sinnl, M.: A dynamic reformulation heuristic for Generalized Interdiction Problems. European Journal of Operational Research. 267, 40–51 (2018)

Jeroslow, R.: The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming. 32, 146–164, (1985)

Kellerer, H., Pferschy. U., Pisinger, D.: Knapsack Problems. Springer (2004)

Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0–1 knapsack problem. Management Science. 45, 414–424 (1999)

Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley (1990)

Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Operations Research. 38, 911–921 (1990)

Pisinger, D.: A minimal algorithm for the 0–1 knapsack problem. Operations Research. 45, 758–767 (1997)

Stackelberg, H.V.: The Theory of the Market Economy. Oxford University Press (1952)

Xu, P., Wang, L.: An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Computers & Operations Research. 41, 309–318 (2014)
