1 Introduction

Recently, a growing attention has been centered to multilevel programming. Here we focus on bilevel optimization where two agents, denoted as a leader and a follower, play a Stackelberg game [11]. In this game, the leader takes the first decision and then the follower reacts taking into account the leader’s strategy. Two standard assumptions hold 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.

In this paper, we consider the Bilevel Knapsack with Interdiction Constraints (BKP), as introduced in [6]. The problem is an extension of the classic 0-1 Knapsack Problem (KP) 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 profits. One of the best performing algorithms for BKP is given in [2]. The algorithm, denoted as 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. Very recently, an improved branch-and-cut algorithm was given in [7]. The proposed approach manages to solve to optimality all benchmark instances in [2], requiring at most a computation time of about 85 s in an instance with 55 items. We also mention the work of [8] where a heuristic approach is proposed for BKP and other interdiction games.

Other bilevel knapsack problems have been tackled in the literature. In [1], the leader cannot interdict items but modifies the follower’s capacity. In [4], the leader can modify the follower’s objective function only. As discussed in [2], both problems are easier to handle than BKP. Recently, a polynomial algorithm has been provided in [3] for the continuous BKP.

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 lower bounds. The proposed approach shows up to be very effective successfully solving all benchmark literature instances provided in [2] within few seconds of computation. Moreover, our algorithm manages to solve to optimality all instances with up to 500 items within a CPU time limit of 60 s. Further details are available in [5].

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 \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 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 \\ \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, i.e. \(y_i \le 1\), only if the item is not interdicted by the leader, i.e. \(x_i = 0\). Constraint (2) represents the leader’s capacity constraint. The objective function (4) maximizes the follower’s profits 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 until 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 \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:

$$\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 \limits _{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 \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 (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 can 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.

In the second case, we derive effective lower bounds on BKP by guessing the critical item of \(KP^{LP}(x^*)\) and correspondingly computing the related split solution of the follower’s problem. These bounds constitute the main ingredient of the exact approach presented in Sect. 4. Since we do not know a priori the leader’s optimal solution \(x^*\), 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_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} CRIT_1(c): \qquad \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 _{j=1}^{w_c} jk_j = C_l \end{aligned}$$
(12)
$$\begin{aligned}&\sum \limits _{j=1}^{w_c} k_j = 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_{j} \in \{0,1\} \qquad j= 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. We can state the following proposition.

Proposition 1

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

Proof

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 \le z^*\). But this means that there exists an optimal solution of model \(CRIT_1(c)\) such that \(z(CRIT_1(c)) \le z_1\) which implies a lower bound on \(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’s 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’s capacity.

Notice that, the state-of-the-art algorithms for KP, Minknap [10] and Combo [9] 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 \le c-1\) are removed from the split solution, while the items \(j: j \ge 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 \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. Instead, an improving subset with \(p^\tau > 0\) is feasible only if \(w^{\tau } \le 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:

$$\begin{aligned} \pi \ge p^\tau (\sum \limits _{j = \max \{1;w^\tau \}}^{w_c} k_j - \sum \limits _{i \in \tau } x_i). \end{aligned}$$
(19)

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 (19) 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.

$$\begin{aligned} CRIT_2(c): \qquad \text {min}\quad&\sum \limits _{i=1}^{c-1} p_{i}(1-x_i) + \pi \end{aligned}$$
(20)
$$\begin{aligned} \text {subject to}\quad&\mathcal {F}(\pi ,x,k) \end{aligned}$$
(21)
$$\begin{aligned}&(11), (16) \nonumber \\&\pi \ge 0 \end{aligned}$$
(22)

Clearly, due to the addition of constraints in \(\mathcal {F}(\pi ,x,k)\), we have \(z(CRIT_1(c)) \le z(CRIT_2(c))\) for any 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.

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)\), 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_j\) 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.

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 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 a parameter \(\delta \) to identify the core size, model \(CRIT_2(c)\) is built by considering several subsets of additional constraints (19). 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 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 provided in Appendix.

4.2 Step 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.

$$\begin{aligned} \quad NCR: \qquad \text {min}\quad&\sum \limits _{i=1}^{n} p_{i}(1-x_{i}) \end{aligned}$$
(23)
$$\begin{aligned} \text {subject to}\quad&\sum \limits _{i=1}^{n} v_{i}x_{i} \le C_u \end{aligned}$$
(24)
$$\begin{aligned}&\sum \limits _{i=1}^{n} w_{i}(1-x_{i}) \le C_l \end{aligned}$$
(25)
$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$
(26)

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).

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 l and r that can be critical according to ordering (8). For item l we have

$$\begin{aligned} l := \min \{ j: \sum \limits _{i=1}^{j} w_{i} \ge C_l\}. \end{aligned}$$
(27)

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 [2]) by solving the following problem (denoted by LW).

$$\begin{aligned} \quad LW: \qquad \text {max}\quad&\sum \limits _{i=1}^{n} w_{i}x_{i} \end{aligned}$$
(28)
$$\begin{aligned} \text {subject to}\quad&\sum \limits _{i=1}^{n} v_{i}x_{i} \le C_u \end{aligned}$$
(29)
$$\begin{aligned}&x_{i} \in \{0,1\} \qquad i= 1,\dots ,n \end{aligned}$$
(30)

Item r is defined as

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

Since from (31) we have \(\sum \limits _{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.

Building Models \({\varvec{CRIT}}_{\mathbf {2}}{{\varvec{(c)}}}\mathbf{.}\) 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 in Appendix.

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 } \le w_c\), we add constraint (19) 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 \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 [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)) \ge z^*\), an optimal BKP solution is already certified (Line 13 of the pseudo code).

Computing Feasible BKP Solutions. According to the previous order of subproblems, we compute BKP feasible solutions by considering the first \(\gamma \) subproblems (Lines 15–21). 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 23–33).

Fixing Variables in Subproblems. 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}| \ge z^* - z(CRIT_2^{LP}(c)) , \quad x_i = x_i^{LP}; \end{aligned}$$
(32)
$$\begin{aligned}&\forall \, j: |r_{k_j}| \ge z^* - z(CRIT_2^{LP}(c)), \quad k_j = k_j^{LP}. \end{aligned}$$
(33)

Solving Subproblems. 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 Sect. 4.2. Then, we add to \(CRIT_2(c)\) the constraint

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

Constraint (34) is a cut imposing that at least one item selected by the follower in solution \(\bar{y}\) must be interdicted. We solve \(CRIT_2(c)\) with one more constraint and apply the same procedure until \(z(CRIT_2(c)) \ge z^*\) or the problem becomes infeasible. At the end of Step 2, the optimal BKP solution \((x^*, y^*)\) is returned (Line 34).

5 Computational Results

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 [2] 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\). Algorithm CCLW in [2] solves all instances with 50 items within a CPU time limit of 3600 s but runs out of time limit in two instances with 55 items. Algorithm in [7] solves all benchmark instances, requiring at most a computation time of about 85 s for solving an instance with 55 items. The proposed exact approach outperforms the competing algorithms, successfully solving to optimality each instance in at most 1.1 s (the maximum CPU time is reached in an instance with 55 items) with an average of 0.2 s. Notice that the tests in [2] and in [7] were carried out on different but comparable machines in terms of hardware specifications. Furthermore, the computational tests in both [2] and [7] 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 [2]. 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 [2] that in instances with \(INS \ge 5\) the follower’s capacity constraint is expected to be inactive and this makes the instances easy to solve. Our computational experiments confirm this trend: the proposed algorithm solves each instance with n from 100 to 500 and \(INS \ge 5\) in at most 8 s never invoking Step 2. In the light of this consideration, we report in the following Table 1 only the results for instances with \(INS \le 4\).

Table 1. BKP instances with \(n = 100, 200, 300, 400, 500\) and \(INS \le 4\).
Full size table

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 s. We also report average and maximum number of subproblems explored in Step 2. The last column reports average and maximum number of times model \(CRIT_2(c)\) is solved along the two steps. The results illustrate the effectiveness of our approach. All instances are solved to optimality requiring 37.4 s 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 times constraint (34) is added to each subproblem is limited: in the tested instances, the while–loop of Step 2 executed 8 iterations at most.