An exact approach for the bilevel knapsack problem with interdiction constraints and extensions

Abstract

We consider the bilevel knapsack problem 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 total profit. We derive effective lower bounds for the bilevel knapsack problem and present an exact method that exploits the structure of the induced follower’s problem. The approach strongly outperforms the current state-of-the-art algorithms designed for the problem. We extend the same algorithmic framework to the interval min–max regret knapsack problem after providing a novel bilevel programming reformulation. Also for this problem, the proposed approach outperforms the exact algorithms available in the literature.

1 Introduction

Recently, 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 ([34]). 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: complete information, 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 [27]. Branch and cut schemes were introduced in [14, 15]. Further approaches were proposed in [5, 18, 36, 37]. An improved generic MIBLP solver has been proposed in [16]. We refer to [16] 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 [14]. The problem is an extension of the classic 0–1 knapsack problem (KP) (see monographs [23, 26]) to a Stackelberg game where 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 total profit.

In [3] it is shown that BKP is $\varSigma _{2}^p$-complete in the polynomial hierarchy complexity. Essentially, BKP cannot be formulated as an ILP model of polynomial size unless the polynomial hierarchy collapses (also pointed out in [4]). This makes the problem even more difficult to solve than an NP-complete problem. We refer to [22] for an introduction on polynomial hierarchy.

One of the best performing algorithms for BKP is given in [4]. 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 s, running out of time in instances with 55 items only. Another previous exact solution approach was proposed in [35]. Very recently, an improved branch-and-cut algorithm has been given in [17]. The proposed approach manages to solve to optimality all benchmark instances in [4], requiring at most a computation time of about 85 s in an instance with 55 items. The algorithm in [17] was shown to be superior to the other approaches also on the medium size instances with up to 50 items considered in [14, 35]. We also mention the work of [19] where a heuristic approach is proposed for BKP and for other interdiction games.

Other bilevel knapsack problems have been tackled in the literature. In [2] the leader cannot interdict items but modifies the follower’s capacity. In [7], the leader can modify the follower’s objective function only. In [33], a variant of the problem is considered in which an item can be taken by both the leader and the follower, in that case its profit changes (either increasing or decreasing). As discussed in [4], these knapsack problems are easier to handle than BKP. A polynomial algorithm has been provided in [6] for the BKP variation where the follower solves a continuous knapsack problem. Finally, a bilevel knapsack problem where the leader controls the weights of a subset of the follower’s items has been recently tackled in [28].

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 [4, 15, 35] within few seconds of computation. Our algorithm manages to solve to optimality larger instances generated according to the same generation scheme of [4] with up to 500 items requiring in the worst-case instance less than 14 seconds of CPU time. An extended computational campaign is also applied to the instances considered in [19] reaching very good results. A preliminary conference version of this work appeared in [13].

Further, we managed to extend the proposed approach to the interval min–max regret knapsack problem (MRKP), as introduced in [24]. This problem is a generalization of the KP where the profit of each item ranges between a minimum and a maximum value. A given assignment of the items profit levels defines a scenario which corresponds to a standard knapsack instance. The problem calls for finding a feasible solution that minimizes the maximum regret over all possible scenarios, where the regret represents the difference between the optimal solution value of a scenario and the value given by the selected solution. The authors of [9] show that the decision version of the MRKP is $\varSigma _{2}^p$-complete and thus very challenging to solve. In [20] different heuristic and exact algorithms are proposed for the problem based on classical optimization approaches such as Benders decomposition and branch and cut methods. We propose a bilevel programming reformulation of the MRKP and correspondingly apply the algorithmic framework proposed for BKP with proper integrations. The approach significantly outperforms the best performing exact algorithms given in [20].

2 Notation and problem formulation

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 \le C_u$ and $w_i \le C_l$ for all i. To avoid trivial instances, it is also assumed that $\sum \nolimits _{i=1}^{n} v_{i} > C_u$ and $\sum \nolimits _{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 item 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} \end{aligned}$$

(1)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} v_{i}x_{i} \le C_u \end{aligned}$$

(2)

$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(3)

$$\begin{aligned}&\text {where }y_1, \dots , y_n \text { solve} \nonumber \\&\quad \text {the follower's problem:}\quad \text {max}\quad \sum \limits _{i=1}^{n} p_{i}y_{i} \end{aligned}$$

(4)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} w_{i}y_{i} \le C_l \end{aligned}$$

(5)

$$\begin{aligned}&y_{i} \le 1 - x_{i} \qquad i= 1,\dots ,n \end{aligned}$$

(6)

$$\begin{aligned}&y_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(7)

The leader’s objective function (1) minimizes the profits of the follower through the interdiction constraints (6). These constraints ensure that each item i can be selected by the follower only if the item is not interdicted by the leader, i.e., if $x_i = 0$. Constraint (2) represents the leader’s capacity constraint. The objective function (4) maximizes the follower’s total profit and constraint (5) represents the follower’s capacity constraint. Constraints (3) and (7) define the domain of the variables.

The optimal solution value of model (1)–(7) 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 (1)–(7) there always exists an optimal solution for the leader which is maximal, namely where items are included in the leader’s knapsack as long as there is enough capacity left.

Let us now recall the optimal solution of the continuous relaxation of a standard KP, namely the follower’s model (4)–(7) without constraints (6) and constraints (7) replaced by inclusion in [0, 1]. Under the assumption $\sum \nolimits _{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 follower’s weights:

$$\begin{aligned} \frac{p_1}{w_1} \ge \frac{p_2}{w_2} \ge \dots \ge \frac{p_n}{w_n}. \end{aligned}$$

(8)

According to this order, items $j = 1,2,\dots$ are inserted into the knapsack as long as $\sum \nolimits _{k=1}^{j} w_{k} \le 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 \nolimits _{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 (8). 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

$$\begin{aligned} \sum \limits _{i \in S: i < c} p_i = \sum \limits _{i = 1}^{c-1} p_i(1 - x_i) \end{aligned}$$

(9)

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.

3 Computing lower bounds on BKP

Consider the optimal solution vector $x^*$. In the induced follower’s knapsack problem $KP(x^*)$ with item set S, two cases may occur: either there is no critical item in $KP^{LP}(x^*)$, namely $\sum _{i \in S} w_i \le 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 Sect. 4.2.1.

In the second case, we derive effective lower bounds on BKP that constitute the main ingredient of the exact approach presented in Sect. 4. 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 in the objective function. We consider binary variables $k_h$$(h= 1, \dots , w_c)$ associated with the weight contribution of the critical item and introduce the following model (denoted as $CRIT_1(c)$).

$\quad CRIT_1(c)$:

$$\begin{aligned}&\text {min}\quad \sum \limits _{i=1}^{c-1} p_{i}(1-x_i) \end{aligned}$$

(10)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} v_{i}x_{i} \le C_u \end{aligned}$$

(11)

$$\begin{aligned}&\sum \limits _{i=1}^{c-1} w_{i}(1-x_{i}) + \sum \limits _{h=1}^{w_c} hk_h = C_l \end{aligned}$$

(12)

$$\begin{aligned}&\sum \limits _{h=1}^{w_c} k_h = 1 \end{aligned}$$

(13)

$$\begin{aligned}&x_c = 0 \end{aligned}$$

(14)

$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(15)

$$\begin{aligned}&k_{h} \in \{0,1\} \qquad h= 1,\dots ,w_c \end{aligned}$$

(16)

The objective function (10) minimizes the value of the split solution. Constraint (11) represents the leader’s capacity constraint. Constraints (12) and (13) ensure that item c is critical as it is the last item packed, with a weight in the interval $[1, w_c]$. Constraint (14) indicates that item c can be critical only if it is not interdicted by the leader. Constraints (15) and (16) indicate that all variables are binary. Admittedly, instead of using $w_c$ binary variables $k_h$, an alternative model could be obtained by using a single integer positive variable in constraint (12). For sake of exposition, this issue is discussed at the end of this section.

We can state the following proposition.

Proposition 1

If c is the critical item in $KP^{LP}(x^*)$, then $z(CRIT_1(c))$ is a valid lower bound on $z^*$.

Proof

If c is the critical item in $KP^{LP}(x^*)$, an optimal BKP solution $x^*$ constitutes a feasible solution for model $CRIT_1(c)$. Let denote by $z_1$ the solution value of the split solution in $KP(x^*)$. Since the follower maximizes the profits in $KP(x^*)$, the value of $z^*$ is greater than (or equal to) the one of the related split solution, that is $z_1 \le z^*$. But then, as model $CRIT_1(c)$ searches for an interdiction of items by the leader inducing a minimum cost split solution (among all feasible split solutions for a given critical item c), we get $z(CRIT_1(c)) \le z_1 \le z^*$. $\square$

The previous proposition already provides a first significant lower bound for the problem. However, following the reasoning in the proof of Proposition 1, 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 considering only items i not interdicted by the leader and to removing tuples of items $i \in [1,c-1]$ and/or to adding tuples of items $i \in [c,n]$ from/to the split solution without exceeding the follower’s capacity.

Notice that, the state-of-the-art algorithms for KP, Minknap ([31]) and Combo ([25]) 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 define a 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 items $c-\varDelta ,...,c+\varDelta$ provided that these items are not interdicted by the leader. In each subset, the items $i: i \le c-1$ are removed from the split solution, while the items $j: j \ge c$ are added to the solution. Whenever this operation does not violate the capacity constraint, a new feasible solution is reached. 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 items $c-\varDelta ,...,c+\varDelta$, let $p^{\tau }$ and $w^{\tau }$ be the related profit and weight contributions, namely:

$$\begin{aligned} p^{\tau } = -\sum \limits _{i \in \tau : i < c} p_i + \sum \limits _{j \in \tau : j \ge c} p_j; \end{aligned}$$

(17)

$$\begin{aligned} w^{\tau } = -\sum \limits _{i \in \tau : i < c} w_i + \sum \limits _{j \in \tau : j \ge c} w_j. \end{aligned}$$

(18)

A subset $\tau$ with $p^\tau \le 0$ is not considered since it does not improve upon the split solution (whatever is the split solution originated by the relevant ILP model) associated with the critical item c. Instead, an improving subset with $p^\tau > 0$ is of interest only if it is feasible. Feasibility is obtained if $w^{\tau }$ does not exceed the residual capacity, that is if $w^{\tau } \le \sum \nolimits _{h = 1}^{w_c} hk_h$ which implies $\sum \nolimits _{h = w^\tau }^{w_c} k_h = 1$. Also, only items not interdicted by the leader can be considered, that is $x_i=0 \; \forall i \in \tau$ must hold. Correspondingly, an improving subset $\tau$ is detected inducing an additional profit $p^\tau$, if and only if the following expression holds:

$$\begin{aligned} \sum \limits _{h = w^\tau }^{w_c} k_h - \sum \limits _{i \in \tau } x_i=1. \end{aligned}$$

(19)

A new model can then be generated by introducing a non-negative variable $\pi$ that carries the maximum additional profit to the split solution value provided by any subset $\tau$ and related additional constraints of the type

$$\begin{aligned} \pi \ge p^{\tau }\left( \sum \limits _{h = w^\tau }^{w_c} k_h - \sum \limits _{i \in \tau } x_i\right) . \end{aligned}$$

(20)

Notice that the right-hand side of (20) is not larger than 0 whenever $\sum \nolimits _{h = w^\tau }^{w_c} k_h =0$ or $\sum \nolimits _{i \in \tau } x_i \ge 1$. Correspondingly, it equals $p^{\tau }$ if and only if expression (19) holds.

We can then consider a set of constraints (each corresponding to a subset of items), denoted (with a little abuse of notation) as ${\mathcal {F}}(\pi , x, k, \tau )$, linking variable $\pi$ to variables $x_i$ and $k_h$ for each considered subset $\tau$. 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 \end{aligned}$$

(21)

$$\begin{aligned}&\text {subject to}\quad {\mathcal {F}}(\pi ,x,k, \tau ) \end{aligned}$$

(22)

$$\begin{aligned}&(11){-}(16) \nonumber \\&\quad \pi \ge 0 \end{aligned}$$

(23)

Due to the addition of any set of constraints ${\mathcal {F}}(\pi ,x,k, \tau )$, for every c we have $z(CRIT_1(c)) \le z(CRIT_2(c))$ as in $CRIT_2(c)$ there are more constraints and the objective function contains an additional positive term $\pi$. Notice that, every additional constraint contains only items not interdicted by the leader (I) and does not violate the follower’s capacity (II). Every set ${\mathcal {F}}(\pi ,x,k, \tau )$ of constraints satisfying both requirements (I) and (II) is denoted as proper. Once set ${\mathcal {F}}(\pi ,x,k, \tau )$ is built, variable $\pi$ represents in the objective function the largest profit induced by the tuples of items that can be added to the profit of the split solution.

Proposition 2

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

Proof

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

We remark that models $CRIT_1(c)$ and $CRIT_2(c)$ contain a pseudo polynomial number of binary variables $k_h$ depending on the magnitude of the follower’s weights. Hence, the hardness of these ILP models may increase with the size increase of such input entries. At the same time, a different handling of models $CRIT_1(c)$ and $CRIT_2(c)$ is possible in presence of large follower’s weights. We can avoid to use a pseudo polynomial number of variables by replacing term $\sum \nolimits _{h=1}^{w_c} hk_h$ in constraint (12) with one integer variable and by introducing a binary variable and two constraints for each tuple considered in ${\mathcal {F}}(\pi ,x,k, \tau )$. For the sake of exposition, we show this alternative treatment of the ILP models only for the MRKP in Sect. 8.2. For BKP, after computational tests on benchmark instances, we noticed that the use of a pseudo polynomial number of variables $k_h$ appears to be more effective. This is because the data generation from the literature chooses rather small follower’s weights in the interval [1, 100] (see Sect. 5) thus limiting the number of variables $k_h$ in models $CRIT_1(c)$ and $CRIT_2(c)$.

4 A new exact approach for BKP

4.1 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 key idea of the algorithm is to compute appropriate leader’s solutions by exploring the most promising subproblems of the follower in terms of lower bounds. This strategy considerably speeds up in practice both the identification and certification of an optimal interdiction structure. 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 value of a parameter $\varDelta$ (that controls the core size), model $CRIT_2(c)$ is built by considering several subsets of items and related additional constraints (20). Then the linear relaxation $CRIT_2^{LP}(c)$ is solved, where the integrality constraints (15) and (16) 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 six parameters $\alpha$, $\beta$, $\varDelta$, $\mu$, $\gamma$, $\omega$ 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.

4.2 Step 1

4.2.1 Handling the possible non-existence of a critical item

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.

$\quad NCR$:

$$\begin{aligned}&\text {min}\quad \sum \limits _{i=1}^{n} p_{i}(1-x_{i}) \end{aligned}$$

(24)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} v_{i}x_{i} \le C_u \end{aligned}$$

(25)

$$\begin{aligned}&\sum \limits _{i=1}^{n} w_{i}(1-x_{i}) \le C_l \end{aligned}$$

(26)

$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(27)

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 3–4 of the pseudo code).

4.2.2 Identifying the relevant critical items

We now assume that there exists a critical item c in $KP^{LP}(x^*)$ (Lines 5–13) and estimate the first and last possible items q and r that can be critical according to ordering (8). For item q we have

$$\begin{aligned} q := \min \left\{ j: \sum \limits _{i=1}^{j} w_{i} \ge C_l\right\} . \end{aligned}$$

(28)

All items $1, \dots , (q-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 to [4]) by solving the following problem (denoted by LW).

$\quad LW$:

$$\begin{aligned}&\text {max}\quad \sum \limits _{i=1}^{n} w_{i}x_{i} \end{aligned}$$

(29)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} v_{i}x_{i} \le C_u \end{aligned}$$

(30)

$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(31)

Item r is defined as

$$\begin{aligned} r := \min \left\{ j: \sum \limits _{i=1}^{j} w_{i} \ge C_l + z(LW)\right\} . \end{aligned}$$

(32)

Since from (32) we have$\sum \nolimits _{i=1}^{r} w_{i}(1 -x_i) \ge C_l$ for any leader’s strategy, all items from $(r+1)$ to n cannot be critical.

4.2.3 Building models $CRIT_2(c)$

For each candidate critical item $c \in [q,r]$, we formulate model $CRIT_2(c)$ by constructing a proper set ${\mathcal {F}}(\pi ,x,k, \tau )$ as follows. Consider the subsets involving items in the interval $[c - \varDelta , c + \varDelta ]$. Even for small value of $\varDelta$, the number of subsets can be very large. Hence, in order to limit the number of constraints in ${\mathcal {F}}(\pi ,x,k, \tau )$, we propose a different strategy that greedily selects the subsets according to the procedure denoted as DefineTuples and sketched below. We remark that the adopted strategy slightly differs from the ComputeTuples procedure we used in [13] and contributes to further improving the performance of the proposed approach (see Sect. 5).

For a given value of $\varDelta$, we consider the interval of items [a, b], with $a=\max \{1;c-\varDelta \}$ and $b=\min \{c+\varDelta ;n\}$. Starting with the empty set, we enumerate all “backward” sets with at most $\alpha$ items among items $a, \dots , (c-1)$. Each set has a profit and weight equal to the sum of profits and weights of the included items. We also compute all “forward” sets with items $c, \dots , b$ and at most $\beta$ items. Then we combine each backward set with a forward set and generate a tuple $\tau$. If $p^{\tau } > 0$ and $w^{\tau } \le w_c$, we store the tuple for possible insertion in set ${\mathcal {F}}(\pi ,x,k, \tau )$. Then we sort all the stored tuples by nondecreasing cardinality with ties broken in favor of tuples with a higher ratio $p^{\tau }/w^{\tau }$. The rationale is to fill set ${\mathcal {F}}(\pi ,x,k, \tau )$ by considering tuples with a limited number of items (and so expected to be more difficult to interdict) while ensuring the insertion of tuples with high efficiency in terms of ratio profit over weight. Following the ordering of the tuples, we add the related constraints (20) to ${\mathcal {F}}(\pi ,x,k, \tau )$ until their number is larger than an input parameter $\mu$. If not previously included, we also add to set ${\mathcal {F}}(\pi ,x,k, \tau )$ the constraint $\pi \ge 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$.

Then we solve models $CRIT_2^{LP}(c)$ for each $c \in [q,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)) \ge z^*$, an optimal BKP solution is already certified (Line 13 of the pseudo code).

4.2.4 Computing feasible BKP solutions

According to the previous order of subproblems, we compute BKP feasible solutions by considering the first $\gamma$ subproblems (Lines 15–22). 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^*$.

4.3 Step 2

This step considers 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 24–42).

4.3.1 Fixing variables in subproblems

For a given problem $CRIT_2^{LP}(c)$, denote the optimal values of variables $x_{i}$ and $k_h$ by $x_{i}^{LP}$ and $k_h^{LP}$ respectively. Let $r_{x_i}$ and $r_{k_h}$ 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} x_i = x_i^{LP}&\;\; \forall \, i: |r_{x_i}| \ge z^* - z(CRIT_2^{LP}(c)) ; \end{aligned}$$

(33)

$$\begin{aligned} k_h = k_h^{LP}&\;\;\forall \, h: |r_{k_h}| \ge z^* - z(CRIT_2^{LP}(c)). \end{aligned}$$

(34)

4.3.2 Solving subproblems

For each open subproblem induced by a critical item c, we first solve $CRIT_2(c)$ (Line 27) 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 Sect. 4.2.4. In [13], the following straightforward cut was added to $CRIT_2(c)$ in order to impose that at least one item selected by the follower in solution ${\bar{y}}$ must be interdicted:

$$\begin{aligned} \sum \limits _{i : \bar{y_i} = 1}^{n} x_i \ge 1. \end{aligned}$$

(35)

Model $CRIT_2(c)$ is then solved with one more constraint and then the same procedure is applied until $z(CRIT_2(c)) \ge z^*$ or the problem becomes infeasible. Taking a closer look to the structure of the subproblems, at each iteration we can replace when possible constraint (35) with a new additional constraint (20) to induce more targeted changes of the interdiction structure in the leader’s solutions and speed up the exploration process of the subproblems.

Given solutions ${\bar{x}}$ and ${\bar{y}}$, let ${\bar{\tau }}$ be the subset of items $1,...,c-1$ not included in ${\bar{y}}$ and items c, ..., n included in ${\bar{y}}$. If ${\bar{\tau }}$ is not empty, we compute quantities $p^{{\bar{\tau }}}$, $w^{{\bar{\tau }}}$ according to (17), (18) respectively and add the corresponding constraint (20) to set ${\mathcal {F}}(\pi ,x,k, \tau )$ in model $CRIT_2(c)$. Two cases may occur when model $CRIT_2(c)$ is solved in the next iteration: either the same solution ${\bar{x}}$ is obtained but then we would have $z(CRIT_2(c)) = z(KP({\bar{x}})) \ge z^*$, or a solution different from ${\bar{x}}$ is obtained. In this second case, either at least one item in ${\bar{\tau }}$ is interdicted and/or the weight contribution of the critical item has a value smaller than $w^{{\bar{\tau }}}$ (corresponding to a different choice of a variable $k_h$ in constraint (12)).

Thus at each iteration we add a valid cut for subproblem $CRIT_2(c)$ when subset ${\bar{\tau }}$ is not empty or else we add constraint (35) as indicated in the pseudocode (Lines 31–35). In addition, if the value of $z(CRIT_2(c))$ stagnates for $\omega$ iterations, we add up to $\mu$ tuples with limited weight (Lines 36–39). At the end of Step 2, the optimal BKP solution $(x^*, y^*)$ is returned (Line 43).

5 Computational testing

All tests were performed on an Intel i5 CPU @ 3.0 GHz with 16 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.9. The parameters of the ILP solver were set to their default values. We considered first the BKP instances with $n=35,40,45,50,55$ that were generated in [4] 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]$.

These 50 benchmark instances were the most challenging ones solved to optimality in the literature. Indeed, the computational tests in both [4, 17] were limited to instances with 55 items. After some preliminary computational tests, we chose the following parameter entries for our approach: $\alpha = 2$, $\beta = 2$, $\varDelta = 10$, $\mu = 150$, $\gamma = 2$, $\omega = 5$. The corresponding results are presented in Table 1. For each instance, we report 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 [4] was executed on a Quad-Core Intel Xeon @ 2.66 GHz using solver Gurobi 5.5.0. This algorithm 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 [17] was executed on an Intel Xeon E3-1220V2 @ 3.1-GHz using solver CPLEX 12.6. This algorithm solves all benchmark instances, requiring at most a computation time of about 85 seconds for solving instance 55-3. As the results in Table 1 illustrate, the proposed exact approach successfully solves to optimality the whole batch of instances in approximately 5 seconds, that is 0.1 seconds on the average, requiring at most 0.34 seconds on instance 55-3. Also, the number of subproblems explored in Step 2 and the number of models $CRIT_2(c)$ solved are very limited. Even though the tests in [4] and in [17] were carried out on different machines and using different solvers, the improvement with respect to the current state of the art literature appears to be very significant.

Table 1 BKP instances from [4]

We considered also other instances considered in the literature proposed in [14] (available at http://coral.ise.lehigh.edu/data-sets/bilevel-instances/) and [35] (available at http://people.clemson.edu/~jcsmith/Test_Instances_files/BKPIns.zip). There is a total of 160 instances in [14] with size not larger than $n=50$ and there is a total of 210 instances in [35] with size not larger than $n=30$. We do not provide the complete results on those instances but just mention that our exact algorithm with the above mentioned settings solved the whole batch of 160 instances in [14] in 9.87 seconds (less than 0.06 seconds on average for instance) and the whole batch of 210 instances in [35] in 18.1 seconds (less than 0.09 seconds on average for instance). We then generated and tested larger instances with $n=100, 200, 300, 400, 500$ (available at https://drive.google.com/drive/folders/1LTDEB3b8gFDXbRJ-9b3RRjJ978BpynYm) according to the generation scheme in [4]. 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 = 2$, $\beta = 2$, $\varDelta = 20$, $\mu = 1000$, $\gamma = 5$, $\omega = 5$. It is pointed out in [4] that in instances with $INS \ge 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 \ge 5$ in at most 6 seconds without ever invoking Step 2. In the light of this consideration, we report in the following Table 2 only the results for instances with $INS \le 4$.

Table 2 BKP instances with $n = 100, 200, 300, 400, 500$ and $INS \le 4$

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 to Table 1, 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 13.6 seconds at most for an instance with 500 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 larger than 29. We finally point out that the number of times constraints (20)/(35) are added to each subproblem is also limited: in the tested instances, the while–loop of Step 2 is executed 5 iterations at most.

To get a broader picture, we also tackled the instances generated in the recent work [19] where a heuristic approach is proposed for BKP and for other interdiction games. These instances are classified according to different correlations between profits and weights following the schemes in [25]. Nine classes were listed in [19] having the following distribution where u.r. stands for uniformly random.

• 1. Uncorrelated : $w_j$ u.r. in [1, R] , $p_j$ u.r. in [1, R].

• 2. Weakly correlated : $w_j$ u.r. in [1, R], $p_j$ u.r. in $[w_j - R/10 , w_j + R/10]$ so that $p_j \ge 1$.

• 3. Strongly correlated : $w_j$ u.r. in [1, R] , $p_j = w_j + R / 10$.

• 4. Inverse strongly correlated : $p_j$ u.r. in $[1 , R ] , w_j = p_{j} + R / 10$.

• 5. Almost strongly correlated : $w_j$ u.r. in $[1 , R ], p_j$ u.r. in $[ w_j + R / 10 -R / 500 , w_j + R / 10 + R / 500].$

• 6. Subset-sum : $w_j$ u.r. in $[1 , R ] , p_j = w_j$.

• 7. Even-odd subset-sum : $w_j$ even value u.r. in $[1 , R ] , p_j = w_j$.

• 8. Even-odd strongly correlated: $w_j$ even value u.r. in $[1 , R ] , p_j = w_j + R / 10$.

• 9. Uncorrelated with similar weights: $w_j$ u.r. in $[100 R , 100 R + R / 10] , p_j$ u.r. in [1, R].

All the instances were generated with $R = 100$, the leader’s weights $v_j$ u.r. in [0, R] and follower’s and leader’s capacities generated as in [4]. We do not consider Class 9 here as it was mentioned in [19] that the instances of this class are trivial for BKP. Table 3 provides the relevant results in terms of average, maximum CPU time and number of optimal solutions obtained within a time limit of 300 seconds for the easier classes 1–2 where our algorithm kept the same parameters values indicated above.

Table 3 BKP instances from [19] (Classes 1–2)

Table 4 provides the relevant results on the harder correlations 3–8. For these instances, best performances were reached by slightly modifying the value of parameters $\varDelta$ ($\varDelta = 50$) and $\mu$ ($\mu = 2000$) while keeping unchanged the other parameters. For these instances, it is shown that the algorithm is capable of solving to optimality instances with size $n=100$ with only four instances (two of class 6 and two of class 7, respectively) exceeding a CPU time limit of 3600 s, thus further highlighting the effectiveness of the proposed approach. In the table, the average CPU time is computed without considering the four instances exceeding the time limit.

Table 4 BKP instances from [19] (Classes 3-8, $n = 100$)

Table 5 BKP instances from [19] (Classes 3–8, $n=200, 300, 400, 500$)

As mentioned at the end of Sect. 3, variables $k_h$ could be substituted by a single integer variable. We tested this alternative formulation but the performances were consistently inferior on every non trivial instance. The total CPU time (summed up on all considered instances) ratio between the formulation with a single integer variable and the formulation with $w_c$ binary variables is approximately equal to 4.

For sake of completeness, we tested also on our machine the exact approaches of [4, 17] (the related codes were kindly provided by the authors) with a time limit of 3600 seconds on the instances of Tables 3 and 4 with $n=100$ for a total of 80 instances. Both approaches were typically able to solve in limited time the so-called easy instances with $INS=$ 5–10, but ran out-of-time in most of the other instances. Specifically, the approach of [4] ran out of time on 28 instances while the approach of [17] ran out of time on 36 instances.

We tested then our approach on larger instances with $n=$ 200–500 on the harder correlations 3–8. Table 5 provides the relevant results regrouped in three main categories ($INS=$ 1–3, $INS=4$ and $INS=$ 5-10). For each category, we depict the number of problems solved to optimality along the six classes 3–8 and the average CPU time. The results clearly indicate that instances with $INS=4$ and $INS=$ 5–10 remain consistently easy to solve for the proposed approach, while instances with $INS=$1–3 are currently out of reach. For these instances involving strong correlations between the profits and the weights of the follower, we believe that dedicated approaches should be considered as it was done in the corresponding versions of the standard KP (see, e.g., the works [30, 32] for handling strongly correlated and subset-sum instances, respectively.)

Finally, we implemented a one-shot heuristic version of our procedure applying only step 1 and allowing a CPU time limit of 60 seconds. In the heuristic, the settings were the same used by our exact algorithm for the instances generated in [4] except for $\gamma = 5$ where for each model $CRIT_2(c)$ CPLEX 12.9 was allowed to run for 10 seconds. We compared our heuristic to the best heuristic algorithm denoted $DR_+$ in [19] on distributions [3–8] (as our exact algorithm solves all instances to optimality on distributions [1–2]). This heuristic procedure shows up to be just slightly inferior to the algorithm in [19] reaching the same objective function value on 281 over 300 instances and being outperformed on 19 instances only.

6 Extending the approach to the interval min–max regret knapsack problem

We now discuss the application of the derived algorithmic framework to the interval min–max regret knapsack problem (MRKP) first introduced in [24]. Some of the notation adopted for BKP recurs in this section with a different meaning. Consider the classical 0/1 Knapsack Problem (KP) and the related ILP formulation $\max \sum \nolimits _{i=1}^{n} p_{i}x_{i}$ subject to $\sum \nolimits _{i=1}^{n} w_{i}x_{i} \le C, \; \;$$x_{i} \in \{0,1\}, \; i= 1,\dots ,n.$ MRKP is a generalization of KP where the profit of each item i can assume any value between two values $p_i^-$ and $p_i^+$, with $p_i^+ > p_i^-$. A set s of n profits $p_i^s \in [p_i^-, p_i^+]$ defines a scenario. The set of all possible scenarios is denoted by $S_0$, namely $S_0 := \{s: p_i^s \in [p_i^-, p_i^+],\; i= 1,\dots , n \}$. We also denote by $z^s(opt)$ the KP optimal solution value under scenario s where each item has profit $p_i^s$ and by $z^s(x)$ the solution value given by a feasible solution vector x, i.e. $z^s(x) = \sum \nolimits _{i=1}^{n} p_{i}^sx_{i}$, $x_i \in x$. Correspondingly, the regret $r^s(x)$ associated with a solution x under scenario s is

$$\begin{aligned} r^s(x) = z^s(opt) - z^s(x). \end{aligned}$$

(36)

MRKP consists in finding a feasible solution vector x such that the maximum regret obtainable over all scenarios is minimized. More formally the problem can be stated as follows:

$$\begin{aligned}&\text {min}\quad \max _{s \in S_0} r^s(x) \end{aligned}$$

(37)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} w_{i}x_{i} \le C \end{aligned}$$

(38)

$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(39)

We denote by $x^*$ an optimal solution of model (37)–(39) with regret value $z^*$.

The authors of [9] prove that the MRKP is $\varSigma _{2}^p$-complete and point out that the solution of even moderately sized instances of the problem is challenging and seems to require innovative approaches. An attempt in this direction has been provided in [20], where heuristic and exact approaches are proposed for the solution of the MRKP. The authors of [20] evaluate the performance of the proposed algorithms through extensive computational experiments on instances with up to 70 items (see Sect. 6.2). We refer the interested reader to [20] for a literature review about other min–max regrets optimization problems.

6.1 Bilevel reformulation of the MRKP

The following crucial result was proved in [1] (and recalled in [20]) for the MRKP within a general context of min–max regrets problems:

Lemma 1

([1]) For any feasible solution x, the profits in its worst case scenario, denoted as $\sigma (x)$, are as follows:

$$\begin{aligned} p^{\sigma (x)}_i = {\left\{ \begin{array}{ll} p_i^- &{} \text {if } x_i = 1\\ p_i^+ &{} \text {otherwise} \end{array}\right. } \;\; (i=1, \dots , n) \end{aligned}$$

Therefore a given feasible solution x induces a unique worst case scenario ($\sigma (x)$) to be considered for the computation of the corresponding maximum regret $r^{\sigma (x)}$, namely

$$\begin{aligned}&r^{\sigma (x)} = z^{\sigma (x)}(opt) - z^{\sigma (x)} = z^{\sigma (x)}(opt) - \sum \limits _{i=1}^{n} p_{i}^-x_{i} \end{aligned}$$

(40)

Notice that the last summation in (40) representing $z^{\sigma (x)}$ does not include terms $p_i^+$ as they disappear when $x_i = 0$. Given the result in Lemma 1, we can alternatively see the problem as a Stackelberg game and propose a related bilevel programming reformulation. To the authors’ knowledge, this is the first time MRKP is formulated as a bilevel programming problem with interdiction constraints. Here the leader first chooses a feasible knapsack solution x with the goal of minimizing the regret $r^{\sigma (x)}$ associated with his decision. The follower aims to maximize the profits of the knapsack instance induced by the worst-case scenario $\sigma (x)$, thus computing $z^{\sigma (x)}(opt)$. To derive a bilevel linear program, we consider binary variables $x_i$$(i=1, \dots ,n)$ equal to one if the leader selects item i. We also introduce 2n items in the follower’s knapsack problem: for each i we define a “low” item $l_i$ with profit $p_i^{-}$ and weight $w_i$ and a “high” item $h_i$ with profit $p_i^{+}$ and weight $w_i$. Correspondingly, we introduce binary variables $y_i^-$ and $y_i^+$ equal to one if the follower selects item $l_i$ or $h_i$$(i=1, \dots ,n)$ respectively. MRKP can be modeled as follows:

$$\begin{aligned}&\text {min}\quad \sum \limits _{i=1}^{n} (p_{i}^{-}y_{i}^{-} + p_{i}^{+}y_{i}^{+}) - \sum \limits _{i=1}^{n} p_{i}^{-}x_{i} \end{aligned}$$

(41)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} w_{i}x_{i} \le C \end{aligned}$$

(42)

$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(43)

$$\begin{aligned}&\text {where }y_1^{-}, \dots , y_n^{-}, y_1^{+}, \dots , y_n^{+} \text { solve} \nonumber \\&\quad \text {the follower's problem:}\quad \text {max}\quad \sum \limits _{i=1}^{n} (p_{i}^{-}y_{i}^{-} + p_{i}^{+}y_{i}^{+}) \end{aligned}$$

(44)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} w_i(y_{i}^{-} + y_{i}^{+}) \le C \end{aligned}$$

(45)

$$\begin{aligned}&y_{i}^{-} \le x_{i} \qquad i= 1,\dots ,n \end{aligned}$$

(46)

$$\begin{aligned}&y_{i}^{+} \le 1 - x_{i} \qquad i= 1,\dots ,n \end{aligned}$$

(47)

$$\begin{aligned}&y_{i}^{-}, y_{i}^{+} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$

(48)

The leader’s objective function (41) minimizes the regret (40) given by the difference between the follower’s profits and $\sum \nolimits _{i=1}^{n} p_{i}^-x_{i}$. The objective function (44) maximizes the follower’s profits while constraints (42) and (45) respectively represent the leader’s and follower’s capacity constraint. Constraints (46) and (47) ensure that scenario $\sigma (x)$ is always induced in the follower’s knapsack problem for any leader’s solution x: the follower can in fact select only item $l_i$ (with profit $p_{i}^{-}$) if $x_i = 1$ and only item $h_i$ (with profit $p_{i}^{+}$) if $x_i = 0$ for each $i=1, \dots , n$. Constraints (43) and (48) define the domain of the variables.

Hence, we can generate a model which is structurally similar to the BKP bilevel formulation (1)–(7). This motivates us to employ the same algorithmic machinery setup for BKP with proper integrations. Model formulation and details of the approach are provided in Appendix.

Table 6 MRKP instances from [20] (Classes 1–3)

Table 7 MRKP instances from [20] (Classes 4–6)

Table 8 MRKP instances from [20] (Classes 7–9)

6.2 Computational results on MRKP

The authors of [20] introduce several heuristic and exact approaches to tackle the MRKP. The solution approaches are based on classical optimization techniques such as Benders decomposition and branch and cut methods. The best performing exact algorithm given in [20] (running on a Pentium 4 @3.2 GHz), denoted as FIMY, is capable of solving to optimality instances with up to 70 items with a time limit of 3600 s, running out of time in 95 out of 486 instances. The instances (available at http://www.or.deis.unibo.it/research_pages/ORinstances/MRKP_instances.zip) were generated by considering different distributions of processing times and weights according to the same nine classes indicated in Sect. 5 with $R = 1000/10000$ and the following additional settings.

• Number of items $n \in \{50, 60, 70\}$.

• Capacity $C \in \{\lfloor 0.45 W \rfloor , \lfloor 0.50 W \rfloor , \lfloor 0.55 W \rfloor \}$ with $W = \sum _{j=1}^n w_j$ (and C increased by 1, if even, for classes 7 and 8).

• profit interval $[p_j^-,p_j^+]$ with $p_j^-$ u.r. in $[(1-\delta )p_j,p_j]$, $p_j^+$ u.r. in $[p_j,(1+\delta )p_j]$ and $\delta \in \{0.1,0.2,0.3\}$.

After preliminary experiments, we set the the parameters of our exact approach to the following entries: $\alpha = 2$, $\beta = 2$, $\varDelta = 50$, $\mu = 1000$, $\gamma = 5$. $\omega = 5$ for Class 6, 7 and 8 which are the hardest classes to solve; $\alpha = 2$, $\beta = 2$, $\varDelta = 20$, $\mu = 200$, $\gamma = 5$. $\omega = 5$ for the remaining classes. Table 6 compares FIMY (running on a different machine) to our approach on classes 1–3. Each row in the table considers six instances aggregated by the number of items n and value of $\delta$. For both approaches, column “Sec” indicates the average CPU time, column “$\#f$” (failures) indicates the total number of instances not solved to proven optimality. Similarly, Table 7 relates to classes 4–6 and Table 8 relates to classes 7–9. Entry “t.l.” in the tables indicates that the approach reached an out of time status in all the instances of the category.

From the tables, even though tests were executed on different machines, we evince that the proposed approach strongly outperforms FIMY (except for Class 1 and Class 9 where FIMY is slightly faster but our approach requires 0.6 seconds at most) running out of time in six instances only (three of Class 6 and three of Class 7).

7 Concluding remarks

We proposed for the bilevel knapsack problem 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. It is shown that the proposed approach handles in few seconds uncorrelated instances with up to 500 items and is capable of solving all but four instances with $n=100$ for various correlation classes between follower’s weights and profits. The approach has been extended to deal with the interval min–max regret knapsack problem. Also in this case the proposed algorithm is shown up to be superior to the current state of the art literature. A very natural future research would be to study bilevel versions of several generalizations of KP, such as, for instance, Collapsing KP [12], Penalized KP [10], KP with Setups [11, 21, 29] and Product KP [8], for which very efficient exact algorithms have been recently proposed.

Appendix

1.1 Additional notation for MRKP

For further analysis, we define the set of items $l_i$ by L and the set of items $h_i$ by H. We consider the 2n items in the follower’s knapsack ordered by nonincreasing ratio profit over weight. For each item $j = 1, \dots , 2n$ in the ordering we denote by i(j) the corresponding index i. Similarly as in Sect. 2, we denote by KP(x) the follower’s knapsack problem induced by a leader’s solution x, here with item set

$$\begin{aligned} J := \left\{ \begin{array}{lr} j: x_{i(j)} = 1 \text { and } j \in L,\\ j: x_{i(j)} = 0 \text { and } j \in H,\\ x_i \in x \end{array}\right\} \end{aligned}$$

and denote by $KP^{LP}(x)$ the corresponding LP relaxation. We again denote as critical the last item with a strictly positive value in the optimal solution of $KP^{LP}(x)$. Notice that for each $x_i$ one item between $l_i$ and $h_i$ will be always available for insertion in the follower’s knapsack. Hence, under the standard assumption that $\sum \nolimits _{i = 1}^{n} w_i > C$ in the MRKP, we also have $\sum \nolimits _{j = 1}^{2n} w_{i(j)} > C$. This implies that there alway exists a critical item c in $KP^{LP}(x)$ and a split solution with value

$$\begin{aligned} \sum \limits _{\begin{array}{c} j \in J: \\ j< c, j \in L \end{array}} p_{i(j)}^{-} + \sum \limits _{\begin{array}{c} j \in J: \\ j< c, j \in H \end{array}} p_{i(j)}^{+} = \sum \limits _{j< c, j \in L} p_{i(j)}^{-}x_{i(j)} + \sum \limits _{j < c, j \in H} p_{i(j)}^{+}(1-x_{i(j)})\qquad \end{aligned}$$

(49)

1.2 Computing a lower bound for MRKP

As for BKP, we aim to guess the critical item of $KP^{LP}(x^*)$. To this purpose we modify model $CRIT_2(c)$ as follows. We replace term $\sum \nolimits _{h=1}^{w_c} hk_h$ with an integer variable $\theta$ associated with the weight contribution of the critical item c in the follower’s capacity constraint, with $1 \le \theta \le w_{i(c)}$. The objective function has term $\sum \nolimits _{i=1}^{n} p_{i}^{-}x_i$ as negative contribution plus the split solution value (49) and the additional profit contribution that can be gained by a feasible solution derived by the split solution. Such a profit is captured by variable $\pi$ through a set of constraints ${\mathcal {F}}(\pi ,x,\theta , v, \tau )$ involving additional binary variables $v_p$$(p = 1, \dots , \frac{|{\mathcal {F}}(\pi ,x,\theta , v,\tau )|}{2})$. We explain the construction of set ${\mathcal {F}}(\pi ,x,\theta , v,\tau )$ next. We obtain the following model, denoted as $CRIT_3(c)$.

$\quad CRIT_3(c)$:

$$\begin{aligned}&\text {min}\quad \sum \limits _{j< c, j \in L} p_{i(j)}^{-}x_{i(j)} + \sum \limits _{j < c, j \in H} p_{i(j)}^{+}(1-x_{i(j)}) + \pi - \sum \limits _{i=1}^{n} p_{i}^{-}x_i \end{aligned}$$

(50)

$$\begin{aligned}&\text {subject to}\quad \sum \limits _{i=1}^{n} w_{i}x_{i} \le C \end{aligned}$$

(51)

$$\begin{aligned}&\sum \limits _{j< c, j \in L} w_{i(j)}x_{i(j)} + \sum \limits _{j < c, j \in H} w_{i(j)}(1-x_{i(j)}) + \theta = C \end{aligned}$$

(52)

$$\begin{aligned}&1 \le \theta \le w_{i(c)} \end{aligned}$$

(53)

$$\begin{aligned}&{\mathcal {F}}(\pi ,x,\theta ,v,\tau ) \end{aligned}$$

(54)

$$\begin{aligned}&x_{i(c)} = 1 \text { if } c\in L \;, x_{i(c)} = 0 \text { if } c\in H \end{aligned}$$

(55)

$$\begin{aligned}&x_{i} \in \{0,1\} \quad i= 1,\dots ,n \end{aligned}$$

(56)

$$\begin{aligned}&v_p \in \{0,1\} \quad p= 1,\dots ,\frac{|{\mathcal {F}}(\pi ,x,\theta , v,\tau )|}{2} \end{aligned}$$

(57)

$$\begin{aligned}&\theta \in N \end{aligned}$$

(58)

$$\begin{aligned}&\pi \ge 0 \end{aligned}$$

(59)

The objective function (50) minimizes the difference between the value of a follower’s knapsack solution and sum $\sum \nolimits _{i=1}^{n} p_{i}^{-}x_i$. Constraint (51) represents the leader’s capacity constraint. Constraints (52) and (53) guarantee that item c is critical as it is the last item packed, with a weight in the interval $[1, w_{i(c)}]$. Constraint (55) enforces the availability of item c in the follower’s knapsack: if $c\in L$ we must have $x_{i(c)} = 1$ or else $x_{i(c)} = 0$. Constraints (56)–(59) define the domain of the variables.

We build a proper set ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$, namely a set of constraints that considers only feasible solutions in the follower’s knapsack, as follows. For a given subset $\tau$ of items around the critical item c, the corresponding profit $p^{\tau }$ and weight $w^{\tau }$ now are:

$$\begin{aligned} p^{\tau }&= - \sum \limits _{ \begin{array}{c} j \in \tau : \\ j< c, j \in L \end{array}} p_{i(j)}^{-} - \sum \limits _{ \begin{array}{c} j \in \tau : \\ j < c, j \in H \end{array}} p_{i(j)}^{+} + \sum \limits _{ \begin{array}{c} j \in \tau : \\ j \ge c, j \in L \end{array}} p_{i(j)}^{-} + \sum \limits _{ \begin{array}{c} j \in \tau : \\ j \ge c, j \in H \end{array}} p_{i(j)}^{+} \end{aligned}$$

(60)

$$\begin{aligned} w^{\tau }&= -\sum \limits _{j \in \tau : i < c} w_{i(j)} + \sum \limits _{j \in \tau : j \ge c} w_{i(j)}. \end{aligned}$$

(61)

We consider in set ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$ only subsets of items improving upon the split solution, i.e. with $p^\tau > 0$, that could be feasible, i.e. with $w^{\tau } \le w_{i(c)}$. Also we do not consider subsets with two items j and $j^{\prime }$ corresponding to the same $x_i$, namely with $i(j) = i(j')$, as these items cannot be both available for packing. For the $p-th$ subset $\tau$ considered for selection in ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$, we will have binary variable $v_p$ equal to one only if the follower’s capacity constraint is not violated, i.e. $w^{\tau } \le \theta$. This condition will be enforced by adding to ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$ the constraint $(w_{i(c)} - w^{\tau }) v_p \ge \theta - w^{\tau },$ that we translate as follows to be added as a linear constraint

$$\begin{aligned} \left( w_{i(c)} - w^{\tau } + \frac{1}{2}\right) v_p \ge \theta - w^{\tau } + \frac{1}{2}, \end{aligned}$$

(62)

where constant term $\frac{1}{2}$ is introduced to have $v_p = 1$ when $w^{\tau } = \theta$. Then an improvement $\pi$ can be determined by adding to ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$ the following constraint

$$\begin{aligned} \pi \ge p^\tau \left( v_p - \sum \limits _{j \in \tau , j \in L} (1-x_{i(j)}) - \sum \limits _{j \in \tau , j \in H} x_{i(j)}\right) . \end{aligned}$$

(63)

Notice that constraints (62) and (63) ensure that only items available for insertion in the follower’s knapsack are considered and the follower’s capacity constraint is not violated, validating tuple $\tau$. The following proposition holds.

Proposition 3

If $KP^{LP}(x^*)$ has critical item c and model $CRIT_3(c)$ has a proper set ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$, then $z(CRIT_3(c)) \le z^*$.

Proof

We apply the same argument of Propositions 1 and 2 and observe that model $CRIT_3(c)$ considers feasible solutions for $KP(x^*)$. Let $z_1$ denote the solution value of the best of these KP solutions. We have

$$\begin{aligned}&z(CRIT_3(c)) \le z_1 - \sum \limits _{i=1}^{n} p_{i}^{-}x_i^* \le z(KP(x^*)) - \sum \limits _{i=1}^{n} p_{i}^{-}x_i^* = z^*, \end{aligned}$$

where the first inequality is implied by noticing that $x^*$ is feasible but not necessarily optimal for model $CRIT_3(c)$. $\square$

We finally notice that the introduction of variable $\theta$ is motivated by the presence of large follower’s weights (with values up to 10,000) in the benchmark MRKP literature instances we considered in our computational tests. As remarked in Sect. 3, large weights compromise the use of variables $k_h$ and the solution of the corresponding ILP models.

1.3 A new exact approach for MRKP

We employ the same algorithmic framework of BKP with the following few modifications. We construct set ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$ in model $CRIT_3(c)$ by a procedure denoted as MRKPTuples. The procedure is very similar to DefineTuples, so we do not report the corresponding pseudo code. The only differences are the presence of 2n items in the follower’s knapsack and the insertion of $\mu$ pairs of constraints (62)–(63) to set ${\mathcal {F}}(\pi ,x,\theta ,v,\tau )$ and constraints related to the adding of the critical item (Lines 6–7 in the pseudo code of DefineTuples).

Similarly to (28), we then define the first possible critical item q as

$$\begin{aligned} q := \min \left\{ j: \sum \limits _{k=1}^{j} w_{i(k)} \ge C\right\} . \end{aligned}$$

(64)

We also test variables $x_i$ and $v_p$ for fixing by reduced costs and consider the following constraint instead of constraint (35) during the exploration of a subproblem $CRIT_3(c)$

$$\begin{aligned} \sum \limits _{i : \bar{x_i} = 0}^{n} x_i + \sum \limits _{i : \bar{x_i} = 1}^{n} (1-x_i) \ge 1. \end{aligned}$$

(65)

Finally notice that for MRKP we do not have to handle the absence of the critical item in the follower’s knapsack problem (see Sect. 8.1). Below is reported the pseudo code of the derived approach.