The Knapsack Problem and Its Variants: Formulations and Solution Methods

Abstract

The Knapsack Problem is among the most well-known and widely studied optimization problems. Given a set of items, each item with an associated weight, the problem asks for a subset of items with a total weight no larger than an available capacity and which maximizes a corresponding measure of profit. The problem appears in distinct versions and also in accompanying variants to these versions, each version being defined by a different type of objective function. Every variant, in turn, imposes some additional requirements on item selection. In this chapter we review a subset of these variants, with a focus on recent papers that bring interesting new applications for the problem.

1 Introduction

The knapsack problem asks for the selection of items from a set N with n elements, every item $j \in N$ with a non-negative integer weight $w_j$ associated with it. A subset of items $S \subseteq N$ is called feasible when $\sum _{j \in S} w_j \le c$ applies, where c is the capacity of a knapsack for carrying the items. Additionally, a profit is incurred by choosing a feasible subset of items and is measured through a properly defined function of N. The aim is to select a feasible $S \subseteq N$ which maximizes profit. The problem appears in distinct versions, each of them characterized by a different type of objective function. Variants to these versions, in turn, typically impose further restrictions on item selection. The linear and the quadratic objective function versions of the problem are those that attract the most interest, with the latter version lagging well behind the former.

The linear 0-1 Knapsack Problem (KP) maximizes a linear objective function. It associates a non-negative integer profit $p_j$ with the selection of every $j \in N$ and relies on binary variables, $x \in \{0,1\}^{n}$, for its standard formulation. Accordingly, $x_j = 1$ holds if j is selected and $x_j=0$ applies otherwise. The Quadratic Knapsack Problem (QKP) is similarly formulated but its objective function involves cross profits $q_{ij} \in \mathbb {Z}$, $i,j \in N$, $i \le j$, to account for eventual fringe benefits attained by simultaneously selecting items i and j (for simplicity, we assume that $q_{ii} = p_{i}$ holds for every $i \in N$). Additional versions of the problem will not be treated here since they only attract very marginal interest. The standard formulation of KP is given by:

$$\begin{aligned} \text {max}&\quad \sum \limits _{j=1}^{n} p_jx_j&\end{aligned}$$

(4.1)

$$\begin{aligned} \text {subject\,to:}&\quad \sum \limits _{j=1}^{n} w_jx_j \le c&\end{aligned}$$

(4.2)

$$\begin{aligned}&\quad x_j \in \{0,1\}&\quad j \in N = \{1,\ldots ,n\} \end{aligned}$$

(4.3)

Furthermore, to avoid trivial solutions, conditions

$$\begin{aligned} \max \{w_j : j \in N\}< c < \sum \limits _{j=1}^{n}w_j \end{aligned}$$

(4.4)

are generally assumed. A formulation for QKP is obtained by noting that $x_i = x_{i} x_{i}$ holds for every $i \in N$ and replacing objective function (4.1) by

$$\begin{aligned} \text {max}&\sum \limits _{i=1}^{n-1}\sum \limits _{j=i}^{n} q_{ij} x_i x_j . \end{aligned}$$

(4.5)

Given that the overwhelming majority of Knapsack Problem references are associated with KP, we will assume here that QKP and all its variants simply correspond to KP variants.

Historically, the first mention of KP dates back to 1896 [145], with references to the subject appearing on early studies in [41] (in folklore, the problem was probably studied under different names hundreds of years before). In the 1950s, the first dynamic programming (DP) approach for solving KP was introduced by Bellman in [13], and in the 1960s the branch-and-bound (B&B) paradigm brought additional solution alternatives to the problem. From that point on, KP has been intensively investigated, starting especially with the works in [73, 129] or [150]. Due to the number of knapsack variants and the associated contributions some books were dedicated to knapsack problems, such as [111, 143].

KP has a wide range of practical applications, such as:  cargo loading, cutting stock, capital budgeting or project selection (see, e.g., [129, 150]). The problem can be solved by DP, which means it is not strongly $\mathcal {NP}$-Hard [70], only being limited by the integral magnitude of capacity c (the complexity of such a DP algorithm is $O(n \cdot c)$). A first survey on solution approaches for KP appears in [166].

A few variants of KP directly follow from the standard formulation of the problem. Among these we consider first the fractional or the continuous knapsack problem, FKP, where (0, 1) fractions of the items are also allowed to be selected. A formulation for FKP is obtained by simply replacing (4.3) in the standard formulation of KP by

$$\begin{aligned} x_j \in \left[ 0,1\right] \quad \forall j \in N. \end{aligned}$$

(4.6)

This allows greedy techniques to work, as suggested by Dantzig in [40]. Indeed it is well-known that FKP can be solved in $O(n \log n)$ time, by greedily selecting the items in descending order of the ratios $\frac{p_j}{w_j}$, $j \in N$.

It is also possible to allow an integral selection of multiple items, leading to the unbounded knapsack problem. From the standard KP formulation we just need to replace (4.3) by

$$\begin{aligned} x_j \in \mathbb {Z}_{\ge 0} \quad \forall j \in N, \end{aligned}$$

(4.7)

in order to formulate the problem.

Finally, the mixed (linear) knapsack problem consists in a collection composed by $n_{\mathcal {D}}$ discrete and $n_{\mathcal {F}}$ fractional items (see, e.g., when $n_{\mathcal {F}} = 1$ [136]). This problem has several practical applications (see, e.g., [200]) and can be modeled in a generalized format, by allowing distinct lower and upper bounds for each item, namely $l_j$ and $u_j$:

$$\begin{aligned} \max&\quad \sum _{j = 1}^{n_{\mathcal {D}} + n_{\mathcal {F}}} p_j x_j&\end{aligned}$$

(4.8)

$$\begin{aligned} \text {s.t.}:&\quad \sum _{j = 1}^{n_{\mathcal {D}} + n_{\mathcal {F}}} w_j x_j \le c&\end{aligned}$$

(4.9)

$$\begin{aligned}&\quad l_j \le x_j \le u_j&\quad \forall j \in \{1, \dots , {n_{\mathcal {D}} + n_{\mathcal {F}}}\} \end{aligned}$$

(4.10)

$$\begin{aligned}&\quad x_j\, \text { integer }&\quad \forall j \in \{1,\dots , n_{\mathcal {D}}\} \end{aligned}$$

(4.11)

$$\begin{aligned}&\quad x_j \in \mathbb {R}&\quad \forall j \in \{n_\mathcal {D}+1,\dots , n_\mathcal {D}+n_\mathcal {F}\}\end{aligned}$$

(4.12)

In practice, instances of the KP variants we have just described involving hundreds of thousands of items are routinely solved by most of mixed-integer programming solvers. Among others, these solvers benefit from preprocessing techniques and the use of facet defining inequalities for the knapsack polytope, i.e., the convex hull of the feasible (integral) solutions to KP (see, e.g., [128] for details).

For the remaining of this chapter we consider several additional KP variants, classical or new. All of them can be formulated by changing the objective function or adding constraints to the standard KP formulation. In practice, these variants are generally much harder to solve than KP and while selecting them we focused on those associated with new interesting applications. First, in Sect. 4.2, we consider variants where a single knapsack constraint must be satisfied. Next, in Sect. 4.3, we discuss additional variants involving two or more knapsack constraints. We conclude the chapter in Sect. 4.4 by considering some future research directions on the topic.

2 Variants with a Single Knapsack Constraint

Several extensions of KP where only one knapsack constraint must be enforced can be identified in the literature. In this section we consider some of these variants where additional constraints conduct to some challenging problems.

2.1 The Multiple-Choice Knapsack Problem

The Multiple-Choice Knapsack Problem (MCKP) is a well-known variant of the KP in which the set of items is partitioned into classes (or groups). In this case the binary choice of taking an item or not in the knapsack is replaced by the selection of exactly one item out of each class of items. Let us denote by $n^{g}$ the number of disjoint groups $N_{1}, \ldots , N_{n^{g}}$ of items and by $n_k$ the number of items in group $N_k$. Then, $N=\bigcup _{k=1}^{n^g} N_k$ and the total number of items is $n = \sum _{k=1}^{n^{g}} n_{k}$. As for KP, every item $j \in N_{k}$ is associated with a profit $p_{kj}$ and a weight $w_{kj}$ and MCKP aims at choosing exactly one item from each class such that the profit sum is maximized and the knapsack capacity c is respected. By defining variable $x_{kj} = 1$ if and only item j in class $N_{k}$ is chosen, MCKP can be mathematically formulated as follows:

$$\begin{aligned} \text {max}&\quad \sum \limits _{k=1}^{n^{g}}\sum \limits _{j \in N_{k}} p_{kj}x_{kj}&\end{aligned}$$

(4.13)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{k=1}^{n^{g}}\sum \limits _{j \in N_{k}} w_{kj}x_{kj} \le c&\end{aligned}$$

(4.14)

$$\begin{aligned}&\quad \sum \limits _{j \in N_{k}} x_{kj} = 1&k = 1, \ldots , n^{g} \end{aligned}$$

(4.15)

$$\begin{aligned}&\quad x_{kj} \in \{0,1\},&k = 1, \ldots , n^{g}, j \in N_{k} \end{aligned}$$

(4.16)

Like KP it is always assumed that all coefficients $p_{kj}, w_{kj}$ and c are non-negative integers. It is interesting to observe that some additional variants of KP may be derived directly from MCKP. For instance when $p_{kj} = w_{kj}$ for all $k = 1, \ldots , n^{g}$ and for all $j \in N_{k}$ MCKP is called the multiple-choice subset-sum problem. In addition, the Multidimensional Multiple-Choice Knapsack Problem (MMCKP) can also be obtained by allowing into MCKP one or more properly defined additional knapsacks. Finally, the discounted 0-1 knapsack problem (see Sect. 4.2.2) can be viewed as a particular case of MCKP.

Several very efficient approaches were proposed to solve MCKP as those described in [51, 155, 173]. In particular, Pisinger developed in [155] an efficient dynamic programming-based algorithm using a list representation and a core problem. Classes are consecutively added to the core and reduction rules are also used to fix some of the variables. Kellerer et al. provided in their book [, Chap. 11] experiments to compare the performance of the approaches described in the last three articles cited above. The results demonstrated the efficiency of all the three approaches for all types of instances, except for strongly correlated ones for which only Pisinger’s approach was able to provide results in the fixed time limit of one hour to solve 100 instances. However, these works showed that MCKP can be solved in very reasonable time for large instances.111

The situation is quite different for the multidimensional case. Some of the current best approaches dealing with MMCKP are based on hybrid approaches combining mathematical programming and heuristic strategies like in [32, 33] where authors considered the use of column generation techniques, whereas authors in [38] extended an iterative relaxation-based procedure proposed in [83]. The proposed method was more general and introduced what authors called the semi-continuous relaxation, where variables are constrained to take values close to zero or one. Mansi et al. proposed some variants of an hybrid strategy consisting of new cuts and a reformulation procedure used at each iteration to improve the iterative relaxation-based heuristic framework in [132]. Chen et Hao developed in [31] a “reduce and solve” heuristic combining problem reduction techniques (based on group-fixing and variable-fixing rules) with an optimal solution of the resulting integer linear problem. Another interesting work is presented in [183] where authors introduced a reformulation of MMCKP as a set partitioning problem allowing to reduce the decision variable dimension regarding the classical model to one dimension, even if the total number of variables and constraints remain the same. Experiments were conducted to compare this new model with the classical one when using CPLEX and GUROBI solvers. The results showed that the new model improved on average the objective function values and the required computational time to converge to the best solutions. In addition the use of this new formulation was competitive when compared to some state-of-the-art approaches for solving MMCKP. We also noted the work in [69] where authors proposed an iterative pseudo-gap enumeration approach which is a two-step procedure. In the first step, a family of pseudo-cuts is derived from the reduced cost constraints with regarding what authors called a “pseudo-gap". In the second step the original problem enriched by these pseudo cuts is solved with CPLEX. The pseudo-gap is used as a hypothesized gap between the upper bound and the lower bound of the original problem and authors proposed a strategy to enumerate it. When the pseudo-gap become valid the proposed iterative approach converges to an optimal solution. This approach obtained very good results compared with other state-of-the art methods for solving MMCKP. Mansini and Zanotti proposed very recently in [135] a new and very effective core-based exact approach. It solves subproblems of increasing size by means of a recursive variable-fixing process and stops when an optimality condition is satisfied. The proposed method obtained 10 new optimal solutions on open benchmark instances in the literature and improved several other best-known solutions.

MCKP and MMCKP have a wide range of classical applications including resources allocation [71, 173], capital budgeting [157], telecommunication networks [93], the management of resources in multimedia systems [113], the VLSI design [146] or the reliability of complex systems [177]. They also appear as a subproblem in several other diverse applications: in nurse scheduling [78], in generalized assignment problems [10] or in the context of warehouse optimization [11]. Fisher showed that MCKP appears when using Lagrangian relaxation of several integer programming problems [62], whereas Kellerer [110] proposed an approximation algorithm for a scheduling problem based on a relaxation formulated as MCKP.

Several additional applications dealing with MCKP or MMCKP can be found in the literature as in [179] where authors introduced what they called the “selective MCKP” in the context of QoS-aware service evaluation and selection. The formulation corresponds to the MCKP in which the choice constraints are relaxed as $\sum _{j \in N_{k}} x_{kj} \le 1$. Zhong and Young used the MCKP to obtain optimal solutions of transportation programming problems when alternative versions of projects are under consideration in [202]. Authors provided six steps to build a MCKP and solved it with the method from [51]. Bae et al. considered in [9] the MCKP as a subproblem when solving a problem of finding a reconnaissance route of an unmanned combat vehicle in a terrain modeled as a grid. They proposed a two-phases method in which all feasible partial routes are generated in a first step. They showed that the problem of selecting partial routes from the set of candidates corresponds to a MCKP. Caserta and Voß  solved the reliability Redundancy Allocation Problem (RAP) via the MCKP in [25]. They introduced the fact that the RAP corresponds to look for an optimal distribution of resources among subsystems. Then, they showed that RAP can be optimally solved in two steps: in the first one a multidimensional knapsack problem (see Sect. 4.3.1) associated to each subsystem is solved, whereas in the second a MCKP is solved to select the specific amount of resources to be assigned to each subsystem. Ykman-Couvreur et al. showed in [199] how the MPSoC runtime management can be modeled as MMCKP, whereas Fischer et al. considered MCKP in a classification problem in [61]. Zhao et al. considered in [201] the optimization of the quality of experience of multiple clients for video streaming over wireless network. They showed that the problem of finding an optimal allocation of bitrate level for multiple wireless clients can be modeled via a MCKP. Tisch et al. dealt with the configuration of learning factories as a MMCKP combined with a two-dimensional bin-packing problem in [178]. Al-Dulaimy et al. showed in [3] that the placement of virtual machines selected for migration in the context of energy efficient cloud data centers management can be modeled as a MCKP, whereas authors in [148] considered an inventory problem under uncertain demand in which a seller stocks an item in anticipation of a single selling season. The corresponding problem is non-convex and they showed that it can be solved via the solution of a polynomial number of particular MCKPs called “two-sided” MCKP in which both lower and upper bounds exist on the knapsack capacity. They proposed a DP-based algorithm and a heuristic and showed their methods obtained better results than a global optimizer for non-convex mixed-integer nonlinear problems. Diallo et al. introduced in [48] a model for a selective maintenance problem for serial systems and proposed a two-phase approach in which the problem is transformed into a MMCKP. Finally, Rogeau et al. introduced very recently what they called a “coupling constraint” into MMCKP to model a retrofit planning problem at territory scale, with a building-level resolution [161].

2.2 The Discounted Knapsack Problem

An interesting variant of the KP is the discounted 0-1 knapsack problem (DKP), where items are selected from 3-sized item groups [89, 163]. Although much harder than KP, fully polynomial approximation schemes and DP-based solution approaches have been developed for it.

Given $n^{g}$ item groups having three items each, and one knapsack with capacity c, where the items in the i-th ($i=0,1,\cdots ,n^{g}-1$) group are denoted as $3i, 3i+1$ and $3i+2$, with value coefficients $p_{3i}$, $p_{3i+1}$ and $p_{3i+2} = p_{3i} + p_{3i+1}$, and weights $w_{3i}$, $w_{3i+1}$ and $w_{3i+2}$ (discounted weight), $w_{3i} + w_{3i+1} > w_{3i+2}$, $w_{3i+2} > w_{3i}$, and $w_{3i+2} > w_{3i+1}$, the goal is to maximize the profits by selecting at most one item in a group. We assume profits and weights to be positive integers, so as the capacity c. DKP can be formulated by (4.17)–(4.20):

$$\begin{aligned} \max&\quad \sum _{i = 0}^{n^{g}-1} (p_{3i} x_{3i} + p_{3i+1}x_{3i+1} + p_{3i+2}x_{3i+2} )&\end{aligned}$$

(4.17)

$$\begin{aligned} \text {s.t.}:&\quad \sum _{i = 0}^{n^{g}-1} ( w_{3i}x_{3i} + w_{3i+1}x_{3i+1} + w_{3i+2}x_{3i+2} ) \le c&\end{aligned}$$

(4.18)

$$\begin{aligned}&\quad x_{3i} + x_{3i+1} + x_{3i+2} \le 1&\, \forall i \in \{0,\ldots ,n^{g}-1\} \end{aligned}$$

(4.19)

$$\begin{aligned}&\quad x_{3i}, x_{3i+1}, x_{3i+2} \in \{0,1\}&\, \forall i \in \{0,l\dots ,n^{g}-1\} \end{aligned}$$

(4.20)

DKP has been introduced in the Master’s Thesis by Guldan [80] and it can be viewed as a particular case of MCKP where the number of items in each group is set to three. Specific relations between items in a group are defined in DKP, which is not the case in MCKP.

DP-based algorithms were proposed to deal with DKP in [80, 89, 163]. Experiments reported in these works show that DP can be used to solve instances with up to $n^{g} = 1,000$ groups in reasonable time under the condition of having sufficient memory resources. A fully polynomial-time approximation scheme, a 2-approximation algorithm and a particle swarm optimization heuristic were also proposed in [89]. Several other population-based metaheuristics have then been proposed to deal with DKP: genetic algorithm [87], differential evolution algorithms [203], multi-strategy monarch butterfly optimization heuristic [58], moth search [56]. Recently, He et al. proposed a new kind of method to design an evolutionary algorithm by using algebraic theory in [86]. The approach used two evolution operators using the addition, multiplication and inverse operation of the direct product of rings. Wu et al. proposed in [195] a discrete hybrid teaching-learning-based optimization algorithm. Very recently, Wilbaut et al. proposed to combine Variable Neighborhood Search (VNS) with DP and showed that all the instances from the literature can be solved in less than 2 seconds thanks to reduction procedures [192].

2.3 The Knapsack Problem with Setup

Another feature which is common to several distinct KP variants is the presence of setup costs [27]. The setup knapsack problem (SKP) originates from (and is named after) a particular machine scheduling problem which involves setup costs [49]. SKP asks for the selection of items from families $\mathcal {F}$, where each item family needs to be set up before usage. Such a condition is modeled through additional variables $z_f$, which indicate whether or not family f corresponding to item $j \in \mathcal {N}_f$ has been set up [27]. A formulation for SKP is given by:

$$\begin{aligned} \max&\quad \sum _{f \in \mathcal {F}} ( u_f z_f + \sum _{j \in \mathcal {N}_f} p_j x_j )&\end{aligned}$$

(4.21)

$$\begin{aligned} \text {s.t.}&\quad \sum _{f \in \mathcal {F}} ( s_f z_f + \sum _{j \in \mathcal {N}_f} w_j x_j) \le c&\end{aligned}$$

(4.22)

$$\begin{aligned}&\quad z_f - x_j \ge 0&\,\forall f \in \mathcal {F}, j \in \mathcal {N}_f \end{aligned}$$

(4.23)

$$\begin{aligned}&\quad z_f - \sum _{j \in \mathcal {N}_f} x_j \le 0&\, \forall f \in \mathcal {F} \end{aligned}$$

(4.24)

$$\begin{aligned}&\quad z_f, x_j \in \{0,1\}&\, \forall f \in \mathcal {F}, j \in \mathcal {N}_f \end{aligned}$$

(4.25)

Note that, in this case, we have $u_f, p_j \in \mathbb {R}$, $s_f, w_j \in \mathbb {Z}^+$ and $N = \bigcup _{f \in \mathcal {F} } \mathcal {N}_f$, with $\mathcal {N}_{f_1} \cap \mathcal {N}_{f_2} = \emptyset$, $\forall f_1, f_2 \in \mathcal {F}$, $f_1 \ne f_2$. Since KP can be reduced to SKP, it is also $\mathcal {NP}$-Hard [70].

A similar SKP variant is called the Multiple-class Integer Knapsack problem with Setups (MIKS), where items are organized in distinct classes with setups and multiplicity constraints [147]. From this perspective, the weight of item at a given class is a multiple of the class weight, while also allowing multiple items to be selected within lower and upper class limits. A more constrained version of MIKS eliminates multiplicity constraints and allows whole integer interval, being called Integer Knapsack Problem with Setups (IKS), that allows the development of more efficient algorithms. In this sense, class weights are restricted to negative factors. A further relaxation of IKS yields the Continuous Knapsack Problem with Setups (CKS), and further adaptations can generate the classic binary knapsack problem. CKS appears as subproblem for capacitated multi-item lot sizing problems, and IKS as subproblem for cutting stock problems. An interesting point is that the relaxation of the binary knapsack with multiple choices is equivalent to CKS [147]. When dealing with numerical experimentation, most success is achieved by hybrid approaches that involve B&B and DP.

Regarding the SKP Khemakhem and Chebil proposed in [114] a tree-search-based combination heuristic which is based on the Filter-and-Fan method. The approach is an iterative local search in which moves are generated according to a tree-search strategy. The main particularity of the method lies in a new technique that makes a bijection between a solution of SKP and an integer index. The algorithm obtains better average results as CPLEX. The same authors proposed in [28] two DP-based algorithms for SKP. The first one considers a stage associated with every item in the problem and computes the optimal values of two auxiliary problems. In the second one authors introduces a space reduction technique to exploit the bijection mentioned above. The DP algorithm considers only the setup variables and a complete solution is obtained by solving a particular KP. This approach is able to solve large correlated instances with up to 10,000 items in reasonable CPU time.

2.4 The Knapsack Problem with Neighbor Constraints

For the 1-Neighbor Knapsack Problem (1-NKP), an item can be selected only if at least one of its neighbours is also selected while items with no neighbors can always be selected. Contrary to that, for the all-neighbours knapsack problem (All-NKP), an item can be selected only if all its neighbors are also selected. Approximation algorithms and hardness results for 1-NKP and All-NKP are provided in [16, 17]. These two NKPs can be generalized as described by the following 0-1 linear program NKP$_k$:

$$\begin{aligned} \max&\quad \sum \limits _{i \in N} p_i x_i&\end{aligned}$$

(4.26)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{i \in N} w_i x_i \le c&\end{aligned}$$

(4.27)

$$\begin{aligned}&\quad \min (k,n_i)x_i \le \sum \limits _{j \in N_i} x_j&\, \forall i \in N, N_i \ne \emptyset \end{aligned}$$

(4.28)

$$\begin{aligned}&\quad x_i \in \{0,1\}&\, \forall i \in N \end{aligned}$$

(4.29)

where $N_i$ is the set of neighbors of vertex i in the graph G and k is an integer less or equal to the maximum degree of vertices in G, i.e. $k \le \Delta = \max \{ \left| N_i\right| : i \in N\}$. Note that $\text {NKP}_1$ is equivalent to 1-NKP and $\text {NKP}_{\Delta }$ is equivalent to All-NKP, while $\text {NKP}_{0}$ corresponds to KP.

The Subset-Union Knapsack Problem (SUKP) is a special case of All-NKP in which the input graph is directed and bipartite and such that the vertex set is partitioned into vertices associated with items and vertices associated with elements and every arc points from an item vertex to an element vertex. The precedence-constrained knapsack problem [15] and the partially ordered knapsack problem [118] are also special cases of All-NKP on directed graph. The general, undirected 1-neighbor knapsack problem generalizes several maximum coverage problems including the budgeted variant considered in [116].

2.5 The Knapsack Constrained Maximum Spanning Tree Problem

The Knapsack Constrained Maximum Spanning Tree problem (KCMST) is a combination of the knapsack problem and the maximum spanning tree problem, introduced in [197]. The weight-constrained Minimum Spanning Tree (MST) problem is to find a spanning tree of total edge weights at most a given capacity and minimum total edge costs. A spanning tree of a graph G is a subgraph connecting all vertices of G. For a spanning tree T of G, we define its profit p(T) and weight w(T), respectively, as the sum of the profits and weights of its constituent edges. A spanning tree T is feasible for KCMST if it satisfies $w(T) \le c$. The problem is to fill the knapsack with a feasible spanning tree such that the tree profit is maximized, which can be formulated as follows:

$$\begin{aligned} \max&\quad p(T) \end{aligned}$$

(4.30)

$$\begin{aligned} \text {s.t.:}&\quad w(T) \le c \end{aligned}$$

(4.31)

$$\begin{aligned}&\quad T \text { is a spanning tree of } G \end{aligned}$$

(4.32)

Based on the connectivity requirements of a tree, four distinct IP formulations for MST are discussed in [55], namely subtour elimination, cut set, single-commodity flow and Martin’s formulation. A subtour elimination formulation is based on the fact that a tree T has no cycles and contains $n-1$ edges [53] and is described as follows:

$$\begin{aligned} \max&\quad \sum \limits _{e \in E} p_e x_e&\end{aligned}$$

(4.33)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{e \in E} w_e x_e \le c&\end{aligned}$$

(4.34)

$$\begin{aligned}&\quad \sum \limits _{e \in E} x_e = n-1&\end{aligned}$$

(4.35)

$$\begin{aligned}&\quad \sum \limits _{e \in E(S)} x_e \le \left| S\right| - 1&\, \forall S \subset N \end{aligned}$$

(4.36)

$$\begin{aligned}&\quad x_e \in \{0,1\}&\, e \in E \end{aligned}$$

(4.37)

Martin’s formulation (see [35, 144]) uses binary variables $y_{ji}^{k}$ if j is the father of i in the tree structure obtained by rooting T at k, 0 otherwise:

$$\begin{aligned} \max&\quad \sum \limits _{e \in E} p_e x_e&\end{aligned}$$

(4.38)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{e \in E} w_e x_e \le c&\end{aligned}$$

(4.39)

$$\begin{aligned}&\quad \sum \limits _{e \in E} x_e = n-1&\end{aligned}$$

(4.40)

$$\begin{aligned}&\quad x_{ij} = y_{ij}^{k} + y_{ji}^{k}&\quad \forall (i,j) \in E, k \in N \end{aligned}$$

(4.41)

$$\begin{aligned}&\quad \sum \limits _{j \in N} y_{ij}^{k} = 1&\quad \forall i \ne k \in N \end{aligned}$$

(4.42)

$$\begin{aligned}&\quad y_{kj}^{k} = y_{ii}^{k} = 0&\quad \forall (i,j) \in E, k \in N \end{aligned}$$

(4.43)

$$\begin{aligned}&\quad x_e \in \{0,1\}&\quad e \in E \end{aligned}$$

(4.44)

The KCMST problem can be extended directly to generalized variants of KP where the MST is replaced by Generalized Maximum Spanning Tree. Pop presented in [158] a survey on different integer programming formulations of the generalized MST problem.

2.6 The Set Union Knapsack Problem

In the Set-Union knapsack Problem (SUKP), introduced in [77], we are given a set N of n elements and a set M of m items. Each item $i \in M$ is characterized by its profit $p_i>0$ and by its set of associated elements $N_i \subseteq N$. For any subset $I \subseteq M$, the profit of I is given by $\sum \limits _{i \in I} p_i$, while the weight of I is $\sum \limits _{j \in \cup _{i\in I} N_i } w_j$, where $w_j$ is the weight of element j. The objective of the SUKP is to select a maximum profit subset of M, while respecting the capacity $c > 0$ of the knapsack. A generic set based formulation of SUKP can be expressed as follows:

$$\begin{aligned} \max&\quad p(I) \end{aligned}$$

(4.45)

$$\begin{aligned} \text {s.t.:}&\quad w(\cup _{i\in I} N_i) \le c \end{aligned}$$

(4.46)

$$\begin{aligned}&\quad I \subseteq N \end{aligned}$$

(4.47)

The graph $G=(M \cup N, E)$, where an edge $(i,j) \in E$ only for $i \in M$ and $j \in N_i$, is a bipartite graph (also known as a bigraph) and sets M and N form a partition of the vertex set. It may be observed that SUKP includes KP as a special case when $N_i \cap N_i^{'} =\emptyset$ $\forall i,i^{'} \in M$ and $\left| N_i\right| = 1$ $\forall i \in M$. Since KP is $\mathcal {NP}$-hard, SUKP is $\mathcal {NP}$-hard as well. SUKP has various domain-specific applications including information security systems, financial decision-making [7, 111], flexible manufacturing machine [77, 116], database partitioning [76], smart city [180] and data stream compression [198]. A mixed-integer programming model can be derived from the previous set-based formulation. It is based on two sets of binary variables. The first one is associated with items whereas the second one is associated with elements. More precisely, we define binary variables $x_i$ and $y_j$ for each item $i \in M$ and for each element $j \in N$, respectively, as:

$${x_{i}=}\left\{ \begin{aligned} 1&\text { if item } i \text { is selected} \\ 0&\text { otherwise} \end{aligned} \right.$$

$${y_{j}=}\left\{ \begin{aligned} 1&\text { if element } j \text { is selected} \\ 0&\text { otherwise.} \end{aligned} \right.$$

Using these variables SUKP can be formulated as:

$$\begin{aligned} \max&\quad \sum \limits _{i \in M} p_i x_i&\end{aligned}$$

(4.48)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{j \in N} w_j y_j \le c&\end{aligned}$$

(4.49)

$$\begin{aligned}&\quad x_i \le y_j&\, \forall i \in M, \forall j \in N \end{aligned}$$

(4.50)

$$\begin{aligned}&\quad x_i, y_j \in \{0,1\}&\, \forall i \in M, \forall j \in N \end{aligned}$$

(4.51)

The objective (4.48) maximizes the total profit associated with the selected items whereas constraint (4.49) is the knapsack constraint. Constraints (4.50) imply that the selection of item i forces the selection of all elements in $N_i$.

Several algorithms have been proposed to solve SUKP. Goldschmidt et al. developed in [77] an exact DP algorithm for SUKP and derived sufficient conditions for having a polynomial run time. Arulsevan showed in [7] that a greedy algorithm for the budgeted maximum coverage problem approximates SUKP within a constant factor. Following the same research direction, Taylor proposed in [175] an approximation algorithm relying on an algorithm for the densest k-subhypergraph problem. Other recent papers dealing with SUKP can be found in the literature. He et al. developed a binary artificial bee colony algorithm and used greedy repairing and optimization to handle infeasibility of a solution in [88], whereas authors in [57] proposed several versions of discrete moth search, while a hybrid approach that combines a genetic algorithm and particle swarm optimization was developed in [151]. Wei and Hao proposed in [184] an iterated two-phase local search (I2PLS) approach for solving SUKP, whereas the same authors proposed in [186] a multistart solution-based tabu search and in [185] a kernel-based tabu search. The last two algorithms conduct to the current best-known solutions for several benchmark instances used in the literature.

2.7 The Precedence Constrained Knapsack Problem

The Precedence Constraint Knapsack Problem (PCKP), also called partially ordered knapsack problem, is a generalization of KP which includes a partial order on items described by an acyclic directed graph $G = (N,A)$ with weights and profits associated to its vertices. An arc $(i,j) \in A$ means that “item i precedes item j”, and implies that if item j is selected then item i must be also selected.

Formally, PCKP can be described by the following 0-1 integer linear program:

$$\begin{aligned} \max&\quad \sum \limits _{i \in N} p_i x_i&\end{aligned}$$

(4.52)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{i \in N} w_i x_i \le c&\end{aligned}$$

(4.53)

$$\begin{aligned}&\quad x_i \ge x_j&\, (i,j) \in A \end{aligned}$$

(4.54)

$$\begin{aligned}&\quad x_i \in \{0,1\}&\, i \in N \end{aligned}$$

(4.55)

PCKP appears in many applications as network design, investment, management problems, scheduling, production planning, see, e.g., [50, 103, 171, 174].

Johnson and Niemi were the first to propose DP algorithms when G is out-tree, called left-right approach in [106]. Then, Samphaiboon and Yamada presented heuristics and DP algorithms for general acyclic graph G in [167].

Beyond the wide range of applications available for PCKP, precedence constraints are of theoretical and computational interest because by themselves they define a polyhedron with integer vertices. More precisely, the convex hull of feasible integer points is the same as the region obtained by relaxing the integrality restrictions. As a consequence, this property allows to solve the Lagrangian relaxation of PCKP associated with the knapsack constraint in polynomial time. Several researchers investigated the polyhedral structure of PCKP by exploiting this property and the rich and large existing results on the knapsack polytope, see e.g., [19, 152].

2.8 The Disjunctively Constrained Knapsack Problem

The knapsack problem with conflicts, also known as the Disjunctively Constrained Knapsack Problem (DCKP), was introduced in [196]. Given a conflict graph $G = (N,E)$ describing incompatibilities between items, DCKP consists in determining a maximum profit set of compatible items to be packed into the knapsack. A compact integer linear programming formulation for DCKP makes use of a set of binary variables $x_i$ associated with every item $i \in N$ and taking value 1 if item i is packed in the knapsack, 0 otherwise, and can be stated as:

$$\begin{aligned} \max&\quad \sum \limits _{i \in N} p_i x_i&\end{aligned}$$

(4.56)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{i \in N} w_i x_i \le c&\end{aligned}$$

(4.57)

$$\begin{aligned}&\quad x_i + x_j \le 1&(i,j) \in E \end{aligned}$$

(4.58)

$$\begin{aligned}&\quad x_i \in \{0,1\}&i \in N \end{aligned}$$

(4.59)

Additional DCKP formulations are found in [92] where an aggregated formulation is proposed, and in [14] where the authors suggest an equivalent MIP based on the determination of a family of cliques in the conflict graph G. Pferschy and Schauer showed in [153] that DCKP is strongly $\mathcal {NP}$-hard and presented pseudo-polynomial algorithms for graphs of bounded tree width and chordal graphs. DCKP is also known as KP with conflicts and is a combination of the Maximum Weighted Independent Set Problem (MWISP) and the KP. When no conflicts are considered, i.e., $E=\emptyset$, the problem reduces to KP whereas when the knapsack constraint is omitted the problem becomes the MWISP.

Several exact and heuristic approaches are considered in the literature. We note in particular the B&B algorithms proposed in [14, 36, 165, 168, 196]. From a heuristic perspective Yamada et al. proposed a local search algorithm [196], whereas more sophisticated approaches based on Tabu Search (TS) were developed in [91] and [168]. The local branching framework was also considered in [2]. Other metaheuristics were considered as scatter search in [94] or the guided neighborhood search in [95], probabilistic tabu search in [164]. Finally we note the memetic algorithms proposed in [164] and very recently in [187].

2.9 The Product Knapsack Problem

The Product Knapsack Problem (PKP) is one of the most recent KP variants. It was introduced in [52] and is defined as we describe next. It aims at determining a subset of items $S \subseteq N$ that maximizes $\prod _{j \in S} p_j$ and such that $\sum \limits _{j\in S} w_j \le c$ holds. With the usual binary variable $x_j$ equal to 1 iff item j is selected, a mixed-integer nonlinear formulation of PKP is described as follows:

$$\begin{aligned} \max&\prod _{j\in N} \max \{1, p_jx_j\} = \prod _{j \in N} (1 + (p_j - 1)x_j) \end{aligned}$$

(4.60)

$$\begin{aligned} \text {s.t.:}&\sum \limits _{j \in N} w_jx_j \le c \end{aligned}$$

(4.61)

$$\begin{aligned}&x \in \{0,1\}^{n} \end{aligned}$$

(4.62)

Denoting by $N^{-} = \{ j \in N : p_j < 0\}$ the sets of items with negative profits and based on the observation that an optimal solution to PKP must include an even number of items $j \in N^{-}$, D’Ambrosio et al. proposed the following mixed-integer linear formulation for the problem:

$$\begin{aligned} \max&\quad \sum \limits _{j \in N} \log (\left| p_j\right| x_j) \end{aligned}$$

(4.63)

$$\begin{aligned} \text {s.t.:}&\quad \sum \limits _{j \in N} w_jx_j \le c \end{aligned}$$

(4.64)

$$\begin{aligned}&\quad \sum \limits _{j \in N^{-}} w_jx_j = 2y \end{aligned}$$

(4.65)

$$\begin{aligned}&\quad (x,y) \in \{0,1\}^{n} \times \mathbb {Z}_{+} \end{aligned}$$

(4.66)

As for solution approaches to PKP, D’Ambrosio et al. proposed a DP algorithm and a mixed-integer linear programming one. Pferschy et al. showed in [154] that PKP is weakly $\mathcal {NP}$-Hard and proposed a fully polynomial-time approximation scheme for the problem.

3 Variants with Multiple Knapsack Constraints

Some KP variants involve more than one knapsack constraints, a requirement that is straightforward to implement directly over the KP formulation. Additionally, they may eventually combine that feature with, among others, different types of objective functions. In this section we consider a few KP variants that fall in such a group, starting with the simplest (from the formulation point of view) of them, the multidimensional knapsack problem.

3.1 The Multidimensional Knapsack Problem

The 0-1 Multidimensional Knapsack Problem (MKP) is the most natural generalization of the KP in which several capacity constraints have to be satisfied. MKP is defined for a set $M = \{1,\ldots ,m\}$ of $m > 1$ capacity constraints. Denoting by $w_{ij}$ the weight of item $j \in N$ in constraint $i\in M$ and by $c_i$ the capacity of knapsack $i\in M$, MKP can be formulated as follows:

$$\begin{aligned} \max&\sum \limits _{j=1}^{n} p_jx_j&\end{aligned}$$

(4.67)

$$\begin{aligned} \text {s.t.}:&\sum \limits _{j=1}^{n} w_{ij}x_j \le {c_i}&i \in M \end{aligned}$$

(4.68)

$$\begin{aligned}&x_j \in \{0,1\}&j \in N \end{aligned}$$

(4.69)

As for KP it is assumed that all coefficients $p_j$, $w_{ij}$ and $c_i$ are non-negative integers values. Some weights can be equal to 0, i.e. $w_{ij} = 0$, as long as $\sum _{i=1}^{m} w_{ij} \ge 1$ holds for all items $j \in N$. In addition, it is generally assumed that $w_{ij} \le c_{i}, \forall j \in N, \forall i \in M$ to guarantee that every item can be selected. Finally, in the same way as (4.4) for KP it is assumed that $\sum _{j=1}^{n} w_{ij} \ge c_{i}, \forall i \in M$. It can be observed that MKP is also known under other names such as m-dimensional KP or multi-constraint KP.

As mentioned in previous sections, many applications of KP and its variants can be listed in the selection and packing area. In most of the cases, real-world applications require more than one constraint. Thus MKP can be considered to deal with these practical problems. In addition, MKP is a particular case of the general 0-1 integer programming problem. The first references dedicated to the MKP include [129, 137, 188]. Cutting stock [73] and loading problems [13] are other classical applications. The MKP was also used in [182] to model the daily management of a satellite like SPOT. In the computer science context, MKP enables to model the resource allocation in distributed data processing [71] and the planning of data-processing programs [176]. Other recent applications can be listed. For instance Mansini and Speranza showed in [133] how the problem of optimally selecting the assets for leasing can be modeled as a MKP. Holte pointed out an equivalence between a multi-unit combinatorial auction and a MKP in [97]. Kelly considered in [112] a variety of auction winner determination problems and their corresponding family of KPs. He also highlighted the fact that existing algorithms dedicated for these problems can be applied effectively to solve the corresponding auction winner determination problems. Finally, Chen et al. considered a stochastic variant of MKP as an allocation resource problem in which the demand may change over time in [30].

Theoretical works demonstrated that MKP is $\mathcal {NP}$-hard and that it has no fully polynomial-time approximation scheme unless $\mathcal {P} = \mathcal {NP}$ (see, e.g., [72]). In fact, despite its simple formulation, the problem remains very difficult to solve at optimality, especially when the number of constraints increases. This is undoubtedly what explains the success of MKP, which is often used to calibrate and evaluate new approaches, in particular metaheuristics and hybrid methods. However, one can observe that the number of papers dedicated to exact methods is comparatively small. It is not possible to present a summary of all interesting publications dealing with the MKP in a few pages. We restrict our presentation to some of the recent approaches leading to the current best-known solutions over the instances of the literature. Interested readers can find surveys dedicated specifically to MKP, see, e.g., [64, 119, 159, 190]. We do not consider either in this section the particular case when $m = 2$ for which many references can also be found in the literature.

Efficient recent approaches dealing with the MKP concern mainly metaheuristics and hybrid methods combining mathematical programming with specific components dedicated to the problem. One of the current best approach to solve hard MKP instances is described in [18]. Authors proposed a multi-level search strategy based on the reduced costs of the non-basic variables of the LP-relaxation solution. In their approach the top-level branches of the search tree were enumerated following resolution search [34], the middle-level branches were enumerated using a B&B and the lower-level branches were enumerated with a depth first search enumeration strategy. Mansini and Speranza proposed in [134] another approach using similar concepts: the exact solving of a sequence of sub-problems, each with a different cardinality constraint, and the use of a reduced-cost constraint based on the objective function of the continuous relaxation. Each sub-problem is built in a first phase through a recursive variable-fixing process up to a predefined size, and is optimally solved in a second phase. Promising results, especially in terms of running time were reported. Defining small-sized sub-problems and considering different branching strategies to solve 0-1 integer programming and mixed-integer programming models have also been considered in other works, as in [85, 189, 191] where authors proposed several iterative schemes where pseudo-cuts are added to strengthen the problem and direct the search. Angelelli et al. applied the kernel search to identify a restricted set of promising items [5]. Starting from an optimal solution of the LP-relaxation, new items are then identified and added in the kernel according to solutions of small to moderate size sub-problems. Della Croce and Grosso proposed in [46] another heuristic closely related to these works and using an LP-based core problem. This heuristic is embedded in a partial enumeration where the branching scheme is based on reduced costs of the corresponding LP-relaxation solution value to fix variables. Very recently, an interesting approach was proposed in [169, 170] in which the aim is to reduce the number of constraints. The method reduces the number of dimensions to be constrained by using new basis vectors to represent the optimal item set with less coordinates. Promising results are reported on the largest instances available in the literature, i.e., when $m=30$ in the OR-Library instances¹ and the instances generated by Glover and Kochenberger in [74]. In particular, the proposed approach provides the optimal or best-known objective values for most instances. It also improves the currently best-known value of one of the Glover and Kochenberger MKP instances and proves the optimality of one other best-known solution.

Concerning metaheuristics we note in particular the scatter search-based algorithm in [84] and the TS-based approach in [115] where authors proposed an hybrid tree-search algorithm that combined TS with a dynamic and adaptive neighborhood search procedure. A two-phase tabu-evolutionary algorithm was also proposed recently in [124]. Authors introduced two solution-based TS methods into the evolutionary framework. They also used a diversity-based population updating rule to keep an efficient population. Computational experiments demonstrated the robustness of the approach since it converged to many best-known solutions and it provided few new best lower bounds. Metaheuristics field is constantly evolving and new approaches are proposed regularly. A very large share of these new methods are tested on MKP. Fingler et al. considered in [60] a parallel implementation of Ant Colony Optimization (ACO) using CUDA and under the GPGPU. They compared the results of this approach with a hybrid DP method, a kernel search and a nested partition and showed that parallel ACO can be an interesting alternative to deal with MKP. Very recently, Lai et al. introduced in [123] a new quantum Particle Swarm Optimization (PSO) that integrates a distance-based diversity preserving strategy and a variable neighborhood descent-based local search method. The results are encouraging and authors showed that the method performs well for instances with a limited number of constraints. It provides better solutions in average than another quantum PSO approach proposed in [81] in very reasonable running time for larger instances. Several other nature-inspired or bio-inspired methods can be identified such as the binary grey wolf optimizer proposed in [130] with some specific components to deal with MKP: an initial elite population generator, a pseudo-utility based repair operator. The results showed that the approach obtained average better results than a few other nature-inspired and bio-inspired methods. Abdel-Basset et al. introduced a modified multi-verse optimization algorithm to solve binary problems [1]. They evaluated this new approach on KP, MKP and MMKP. The results show an interesting behavior of this metaheuristic to tackle different variants of KPs.

To conclude this section it should be observed that in many works dedicated to population-based approaches some of the large instances in the literature are not considered and that authors do not necessarily compare their results with the state-of-the-art, making it difficult objective comparison.

3.2 The Multidimensional Knapsack Problem with Demand Constraints

The 0-1 Multidimensional Knapsack Problem with Demand Constraints (MKPD) is generalization of the MKP in which a set of q greater than constraints, $q \ge 1$, complements its multiple knapsack constraints. Accordingly, MKPD extends the MKP formulation as follows:

$$\begin{aligned} \max&\quad \sum \limits _{j=1}^{n} p_jx_j&\end{aligned}$$

(4.70)

$$\begin{aligned} \text {s.t.}:&\quad \sum \limits _{j=1}^{n} w_{ij}x_j \le {c_i}&\quad i \in \{1, \ldots , m\}&\end{aligned}$$

(4.71)

$$\begin{aligned}&\quad \sum \limits _{j=1}^{n} w_{ij}x_j \ge {c_i}&\quad i \in \{m+1, \ldots , m+q\} \end{aligned}$$

(4.72)

$$\begin{aligned}&\quad x_j \in \{0,1\}&\quad j \in N = \{1,\ldots ,n\} \end{aligned}$$

(4.73)

In this formulation we distinguish the first m classical knapsack constraints from the subsequent q which are the demand constraints. Comparing with MKP and other extensions of KP the MKPD can be viewed as a recent variant if we consider the references to this problem in the literature. Indeed, to the best of our knowledge the MKPD has been formally introduced at the beginning of the twentieth century by Cappanera and Trubian, firstly in [21] and then in the associated paper [22]. Like MKP the MKPD is embedded in the models of many practical applications, in particular in obnoxious and semiobnoxious facility location problems (see, e.g., [20, 162]) and portfolio-selection problems [12]. More recently a possible application in the context of the ideal product mix for a mobile retailer where a resource constraint represents the space of the retailer whereas a demand constraint models the fact the product mix has to meet or exceed a given revenue threshold was considered in [193]. We also noted the work presented in [96] where author considers the constrained problem of multi-robot tasks allocation and compares dedicated algorithms with approaches presented in [6, 102] for solving the more general MKPD. The main conclusion is that a direct application of MKPD dedicated methods does not allow to obtain efficient solutions even for medium-sized instances.

It is interesting to observe that finding a feasible solution of the MKPD is an $\mathcal {NP}$-complete problem [22] due to the presence of conflicting binary constraints. Like for the MKP and other variants a large set of 810 instances is available in the literature to compare the proposed approaches. Most of the proposed approaches dealing with MKPD are based on heuristics and metaheuristics. This can probably be explained by its practical difficulty and the fact that exact methods cannot solve instances with more than 100 items in reasonable running and memory limits. Concerning theoretical works we noted the promising work in [45] in which the author introduced the use of equality rather than inequalities in cutting planes (called equality cuts) in binary programming in general to reduce the linear relaxation space, and the concept of anticover inequality. He applied it on the MKPD and showed that using these equality cuts with CPLEX improved the computational effort by about 7% when considering instances with up to 250 items and $m = 10$ and $q = 10$. Wishon and Villalobos introduced in [194] new efficiency measure calculations and some properties and showed that these measures are applicable to all KP variants with a single linear objective function and linear constraints of any quantity. They validated these measures with three solution algorithms (a fixed-core algorithm, a kernel search algorithm and a Genetic Algorithm (GA)) on instances randomly generated with up to 1,000 items and $m + q \le 25 + 25$.

Among the heuristic and metaheuristic approaches, Cappanera and Trubian proposed in [22] a sophisticated local search algorithm into two phases, which combines a standard attribute-based TS with an oscillation method based on the one proposed for the MKP in [74], but is restricted to the feasible space. The approach was not able to provide a feasible solution to every instance but provided better solutions in general than CPLEX. Arntzen et al. proposed in [6] an adaptive memory search procedure which uses a dynamic TS mechanism and a weighting scheme to manage infeasible solutions. The computational results demonstrated the efficiency of the approach which was able to provide a feasible solution for every instance, except one. Then, Hvattum and Lokketangen conducted in [102] several implementations of Scatter Search (SS) for the MKPD based on some proposals about SS in general [75]. They performed extensive experiments and obtained good results compared with CPLEX and Cappanera and Trubian’s algorithm. Gortázar et al. introduced in [79] a black box SS method for general classes of binary optimization problems. According to its general description three of the five methods used in SS are problem-dependent. Authors considered some diversification generators and combination methods and evaluated the approach on four optimization problems among which is the MKPD. The results showed that the approach was dominated by the one in [6] but converged quickly to good solutions compared with commercial solvers. Hvattum et al. proposed in [101] an alternating control tree-search framework related to the relaxation-based heuristics proposed in [189] for the MKP. The approach is based on three components: the first one solves an LP-relaxation of the current problem; the second one partitions the set of variables and build sub-problems that can be solved efficiently; the third one updates the problem by adding inequalities and ensuring the convergence of the approach. The overall method can be also used as a heuristic. The algorithm is evaluated on the MKPD and the MKP. The results revealed that the method was very effective for the MKPD compared to the TS algorithm proposed in [6] and the SS algorithm proposed in [102]. It was also competitive for the MKP when compared with some of the best solution approaches. Recently, Lai et al. introduced in [125] a two-stage TS-based algorithm for solving MKPD. The TS uses one-flip and swap neighborhoods and a hash-based mechanism to determine the tabu status of neighbor solutions. In the approach the fist stage aimed to identify a promising hyperplane within the whole search space. The second stage is dedicated to the search for an improved solution by examining both feasible and infeasible solutions on the identified hyperplane. The computational results reported on a subset of the available instances show that this approach performs well and provides efficient solutions in reasonable running times. Very recently, Al-Shihabi proposed a core-based optimization framework and evaluate it over the MDMKP [4]. The main idea is to define a new core problem iteratively using a kind of local search where the aim is to find the best neighbouring core problem. The initial core problem  is built from the reduced costs of variables and a probing technique is used to control the number of changes in two consecutive core problems. Author evaluates this framework when using CPLEX and the approach proposed in [125] to solve the core problems. Promising results are presented and the method leads to several new best-known solutions.

3.3 The Multiple Knapsack Problem

The Multiple Knapsack Problem (M-KP) is a generalization of KP in which a set M of $m \ge 2$ knapsacks are available for carrying the items. This problem, one should note, is different from the multidimensional knapsack problem (see Sect. 4.3.1) and the multidimensional multiple-choice knapsack problem (see Sect. 4.2.1) since in the M-KP every item has to be assigned to one knapsack (at most). In the formulation of the M-KP a binary variable $x_{ij}$ is associated with knapsack i and item j and is set to 1 if item $j \in N$ is assigned to knapsack i (0 otherwise). The problem aims at maximizing total profit while respecting the capacity of every individual knapsack and can be formulated as follows:

$$\begin{aligned} \max&\quad \sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n} p_jx_{ij}&\end{aligned}$$

(4.74)

$$\begin{aligned} \text {s.t.}:&\quad \sum \limits _{j=1}^{n} w_{ij}x_{ij} \le {c_i}&\quad i \in M \end{aligned}$$

(4.75)

$$\begin{aligned}&\quad \sum \limits _{i=1}^{m} x_{ij} \le 1&\quad j \in N \end{aligned}$$

(4.76)

$$\begin{aligned}&\quad x_{ij} \in \{0,1\}&\quad i \in M, j \in N \end{aligned}$$

(4.77)

Constraints (4.76) guarantee that every item is placed in at most one knapsack. A special case of the M-KP is obtained if all the knapsacks have an identical capacity c. This variant is generally referred to as the multiple knapsack problem with identical capacities. Additionally, one also finds subset-sum variants for both models, with $p_{j} = w_{j}, \forall j \in N$, thus applying. The M-KP is also related to the classical bin-packing problem (BPP). Three main differences can be listed: (i) items have both a weight and a profit in the M-KP, whereas items only have a weight in BPP; (ii) bins (knapsacks) in the M-KP have varying sizes, while bin capacities are uniform in BPP; (iii) the aim of the M-KP is to maximize the total profits of the items packed in a set of bins (knapsacks), and some items are not assigned, whereas all items must be packed in the BPP. Finally one can observe that the M-KP is a special case of the generalized assignment problem in which a profit $p_{ij}$ is defined if item j is assigned to knapsack i. The M-KP and its variants are strongly $\mathcal {NP}$-Hard problems and it was proved that even when $m = 2$ the subset-sum variants do not admit a fully polynomial-time approximation scheme unless $\mathcal {P} = \mathcal {NP}$ (see, e.g., [111]). Polynomial-time approximation schemes were developed in [29] for the MKP and in [24] for the subset-sum variant.

Eilon and Christofides [54] were among the first to consider the M-KP as a cargo loading problem. Ferreira et al. used in [59] a generalization of the M-KP to solve real-world problems in the design of processors for mainframe computers, in the layout of electronic circuits, and in sugar cane alcohol production in Brazil. Another application can be found in [107] where authors considered the M-KP for task allocation among autonomous agents, continuous double-call auctions. The M-KP was also used to model multiprocessor scheduling and the assignment of files to storage devices in order to maximize the number of files stored in the fastest storage devices in [122]. More recently Laalaoui and M’Hallah [121] addressed a single machine scheduling problem with machine unavailability as a M-KP, whereas Simon et al. modeled problems of maintaining operational capability without external support through M-KPs in [172]. Additional constraints occur among which are demand constraints and some others related to the application.

Some B&B methods were proposed to solve the M-KP as in [140] where Martello and Toth solved at each node a relaxed version of the M-KP where the assignment constraint is omitted. The branching item is chosen among those which had been assigned to $\bar{m} > 1$ knapsacks and the branching operation generates $\bar{m}$ nodes by assigning the item to one of the $\bar{m}-1$ knapsacks or excluding it from all of these. Next year, Martello and Toth [141] proposed one of the most well-known B&B for the M-KP known as MTM. In this algorithm a lower bound is derived at each node of the tree by solving m individual KPs in the following way: the first KP is solved optimally. Then, the chosen items are removed and the next KP can be solved and so on until all the m knapsacks are filled. Upper bounds are computed from a surrogate relaxation. The branching scheme is based on the obtained solution by generating two nodes: the first one assigning the next item of a greedy solution to the chosen knapsack, while the other excluding this item from the knapsack. Pisinger [156] proposed a more efficient procedure starting from MTM. In this approach called Mulknap lower bounds are derived by solving a series of subset-sum problems which are also used for tightening the capacity constraints of the knapsacks. He introduced efficient reduction rules to determine which items cannot be packed into any of the knapsacks and he derived upper bounds through surrogate relaxation. He compared the results of MTM and Mulknap and showed that the latter approach was able to solve very efficiently and optimally large-size instances of the M-KP with up to $n = 100,000$ items and $m = 10$ knapsacks. However, Fukunaga showed in [66] that Mulknap performs less effectively when the ratio of items to knapsacks (n/m) falls between 2 and 5 or when the data are strongly correlated. Fukunaga and Korf [67] introduced a B&B algorithm called bin-completion and based on a bin-oriented branching structure and a powerful dominance criterion. Authors showed that this new method is particularly competitive for solving MKP instances when the ratio of items to knapsacks is small (i.e., $n/m < 4$). This work was extended in [66] by integrating additional techniques from constraint programming like path-symmetry and path-dominance criteria for pruning nodes in the M-KP B&B search space. Experimental results confirmed the competitiveness of the approach for instances with a small ration n/m and the integration of Mulknap algorithm significantly improved the results for higher ratios. Very recently, Dell’Amico et al. presented in [47] two pseudo-polynomial formulations for the M-KP based on arc-flow and reflect models. Authors proposed a new effective hybrid method combining B&B, Master/Slave decomposition, Benders’s cuts and constraint programming. This approach outperforms other exact methods and is able to solve optimally 1,988 instances over the 2,100 instances considered in the paper in reasonable running time.

Papers related to heuristics for the M-KP can also be found in the literature, especially the well-known MTHM polynomial-time heuristic based on greedy algorithm and local search procedure proposed in [142], which was tested on instances with up to $n = 10,000$ and $m = 40$ in [143]. More recently, Lalami et al. proposed a heuristic based on the core concept [126]. The approach recursively solves the core of different KPs through DP. The method is tested on randomly generated instances with up to 100,000 items and $m = 100$ and compared with MTHM. The results showed that the approach provided good solutions in very short time. Laalaoui [120] proposed two simple extensions of the MTHM. It consists in applying a local search starting from the solution of MTHM and considering two swap moves: the replacement of one item currently assigned to a knapsack by one or two others currently not assigned; or the replacement of two items currently assigned by one item currently not assigned. The results demonstrates that this method improves by around 15% the solution value provided by MTHM with a reasonably increased execution time. Final solutions were at less than 1% in average of the solutions obtained by GAs proposed in [68]. Laalaoui and M’Hallah considered in [121] a single machine scheduling problem with machine unavailability periods corresponding to maintenance periods and modeled it as a M-KP. They proposed a VNS that helps to yield better results than MTHM and other heuristics on scheduling instances with up to 4,800 items and 2,400 knapsacks.

To conclude this section we would like to underline another variant of the M-KP in the literature introduced in [109] and named the multiple knapsack assignment problem. In this variant items are partitioned into subsets and additional constraints impose that a knapsack can only contain items of the same class. This interesting problem which has managerial applications in transportation logistics was considered very recently in [139] where authors proposed some upper bounds derived from Lagrangian and surrogate relaxation and a heuristic procedure.

3.4 The Compartmentalized Knapsack Problem

The Compartmentalized Knapsack Problem (CKP) is a variant of KP where items are classified under some criteria or affinities and divided into several classes, like for instance in the MCKP. However, in the CKP items of different classes cannot be mixed in the knapsack. To select items some compartments have to be built. The compartments are not predetermined and have to be added inside the knapsack such that each compartment contains items of the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to find the compartments while maximizing the total value of the items loaded in the overall knapsack minus the cost of the compartments. Like in KP each item has a weight and an utility value.

CKP takes its origin from cutting application where it models a particular two-stage cutting process where items are grouped into classes and only items of the same class can be cut from an intermediate roll. It arises for instance in the case of cutting steel coils in two phases in the metallurgical industry [160]. Items are associated to ribbon coils (corresponding to the classes of items) that are grouped by their thickness. The ribbons are obtained by cutting the steel coils available in stock, which correspond to the knapsack to be filled. Another example in the literature is steel roll cutting where items are grouped according to their thickness [127]. In that case the first cut on the original roll generates different intermediate rolls (corresponding to the compartments in the knapsack), which have the same thicknesses as the original roll. In these applications items are modeled by integer variables. Hoto was among the first to introduce and to define the CKP in his Ph.D. thesis [98]. He distinguished the restricted (or constrained) version where the number of copies for an item is bounded and the unrestricted (or unconstrained) case where this bound does not exist. He provided an integer nonlinear optimization model for the unrestricted CKP and he proposed a B&B algorithm to solve it. Then, Marques and Arenales proposed in [138] three new heuristics and a model for the restricted case. Hoto et al. considered the cutting stock problem where each cutting pattern is restricted to be compartmentalized [99]. They presented a concise formulation of CKP and proposed heuristic and exact methods for the unrestricted case. They also presented an integer nonlinear programming formulation of the restricted CKP and proposed a two-phase heuristic which obtained better results than the heuristic proposed in [138]. Later, Hoto et al. [100] introduced techniques based on column generation for the restricted CKP, whereas Leão et al. proposed a linear treatment for the restricted CKP and a hybrid heuristic to solve it in [127]. The natural formulation of CKP is nonlinear and some works in the literature were devoted to propose a linear formulation like in [104] where author extended previous works in [39, 100] by proposing new linearity studies of CKP together with a new exact algorithm, called the exhaustive decomposition algorithm, to solve it. More recently, Inarejos et al. [105] proposed an integer linear optimization model for the restricted CKP and proved its linearity. This model was strengthened in [160]. It can be observed from the literature that several variants of the restricted CKP exist. The main difference among these variants is the objective function which is considered. Very recently, Baazaoui et al. proposed in [8] a new variant of CKP with a formulation involving only binary variables. This formulation is related to the one presented in [105] and is introduced below to illustrate CKP. Let c be the capacity of the knapsack and N the set of items which is partitioned into a set M of $n^g$ classes: $N = \cup _{k\in M} N_k$ with $N_k \cap N_{k'} = \emptyset$, $k \ne k' \in M$. Each item j in class k is characterized by a utility and a weight denoted by $p_{j}^{k}$ and $w_{j}^{k}$, $j \in N_{k}, k \in M$, respectively. In addition, for each class $k \in M$ there is a maximum and a minimum capacity to be consumed by a compartment, namely $c_{max}^{k}$ and $c_{min}^{k}$, respectively, whereas building a compartment involves a fixed loss cost $f_k$. In the formulation a set $P_k$ of all the possible compartments associated with group k is used to define the set of variables (one can observe that the size of $P_k$ can be simply bounded by the number of items in $N_k$). Binary variable $x_{j}^{k}$ is introduced to know if item j in set $N_k$ is selected, whereas binary variable $y_{ij}^{k}$ is used to know if item $j \in N_k$ is assigned to compartment $i \in P_k$. Finally, binary variable $z_{i}^k$ is equaled to 1 if compartment $i \in P_k$ is built. Then, a binary variant of CKP can be stated as follows:

$$\begin{aligned} \max&\quad \sum \limits _{k \in M}\left( \sum \limits _{j \in N_{k}} p_{j}^{k} x_{j}^{k} - \sum \limits _{i \in P_{k}} f_k z_{i}^{k}\right)&\end{aligned}$$

(4.78)

$$\begin{aligned} \text {s.t.}:&\quad \sum \limits _{k \in M}\sum \limits _{j \in N_{k}} w_{j}^{k} x_{j}^{k} \le c&\end{aligned}$$

(4.79)

$$\begin{aligned}&\quad c_{min}^{k} \le \sum \limits _{j \in N_{k}} w_{j}^{k} y_{ij}^{k} \le c_{max}^{k}&\quad \forall k \in M, j \in P_k \end{aligned}$$

(4.80)

$$\begin{aligned}&\quad \sum \limits _{j \in P_k} y_{ij}^{k} = x_{i}^{k}&\quad k \in M, i \in N_k \end{aligned}$$

(4.81)

$$\begin{aligned}&\quad x_{j}^{k}, y_{ij}^{k}, z_i^k \in \{0,1\}&\quad k \in M, j \in N_{k}, i \in P_k \end{aligned}$$

(4.82)

Interested readers are invited to consult [105, 160] for other linear formulations with integer variables.

3.5 The Multiple Knapsack Problem with Color Constraints

The Multiple Knapsack Problem with Color constraints (MKPC) is another generalization of KP in which: (i) a new attribute, called color, is associated with every item ; (ii) assignment restrictions are introduced regarding the compatibility of items in a given knapsack. MKPC can also be formulated in different ways. The problem was first introduced with this name in [42] motivated by a real application in the steel industry called the surplus inventory matching problem. Here the orders correspond to items and the slabs correspond to knapsacks. The goal of the problem is to maximize the total weight of the surplus used to fulfill orders in the order book. Other objectives can be considered as the minimization of the leftover weight of each used slab. To introduce more formally the problem we have to provide some details about the correspondence between MKPC and the related application [42]. For each item (order) $j \in N$ characterized by a weight $w_j$, a set $M_j$ of applicable knapsacks (slabs) from the surplus inventory can be identified. These assignment restrictions are based on quality and physical dimension considerations. In addition only knapsacks that are of the same quality or better can be applied for any given item. Then, for each slab (knapsack) $i \in M$ with a weight $b_i$ a set $N_i$ of applicable orders (items) is defined. The thickness and width requirements for each item need to be compatible with those of the applicable knapsacks. Another important notion in MKPC is the color associated with each item. Color constraints restrict the sets of items that can be matched to the same knapsack in the surplus inventory. In fact not all items assignable to a given knapsack can be packed together on that knapsack, due to processing considerations in the finishing line of a steel mill. A route associated with each item that specifies the set of process operations that need to be applied is given. A unique color is associated with each route and the number of colors on a knapsack is restricted (in practice to two). The color can be introduced with parameter $k_j$ to denote the color of order $j \in N$ and with $\mathcal {K}_i$ to denote the set of colors incident on slab $i \in M$. Forrest et al. proved in [63] that the problem of applying orders against an existing surplus inventory is the surplus inventory matching problem and can be formulated as a multiple knapsack problem with color and assignment constraints considering only one objective. This is achieved by introducing the following binary variables: $x_{ij}, \forall i\in M, j\in N$ which is set to 1 if item j is assigned to knapsack i; $y_{ki}, \forall i \in M, k \in \mathcal {K}_i$ which has value 1 if items of color k obtain material from knapsack i; and $z_{i}, \forall i \in M$ which is set to 1 if any item is incident to knapsack i. Then, MKPC can be modeled as follows [63]:

$$\begin{aligned} \max&\quad \sum \limits _{j \in N}\sum \limits _{i \in M_{j}} w_j x_{ij} - \sum \limits _{i \in M} (b_i - \sum \limits _{j \in N_{i}}w_j x_{ij}) z_{i}&\end{aligned}$$

(4.83)

$$\begin{aligned} \text {s.t.}:&\quad \sum \limits _{j \in N_{i}}w_j x_{ij} \le b_{i}z_{i}&i \in M \end{aligned}$$

(4.84)

$$\begin{aligned}&\quad \sum \limits _{i \in M_{j}} x_{ij} \le 1&j \in N \end{aligned}$$

(4.85)

$$\begin{aligned}&\quad \sum \limits _{c \in \mathcal {K}_{i}} y_{ci} \le 2&i \in M \end{aligned}$$

(4.86)

$$\begin{aligned}&\quad x_{ij} \le y_{c_{j},i}&i \in M, j \in N \end{aligned}$$

(4.87)

$$\begin{aligned}&\quad x_{ij} \in \{0,1\}&i \in M, j \in N \end{aligned}$$

(4.88)

$$\begin{aligned}&\quad y_{ci} \in \{0,1\}&c \in \mathcal {K}_{i}, i \in M \end{aligned}$$

(4.89)

$$\begin{aligned}&\quad z_{i} \in \{0,1\}&i \in M \end{aligned}$$

(4.90)

As mentioned by [63] nonlinear objective function (4.83) can be rewritten as

$$\begin{aligned} \sum \limits _{j \in N}\sum \limits _{i \in M_j} 2w_jx_{ij} - \sum \limits _{j\in N} b_iz_i \end{aligned}$$

(4.91)

since $z_i = 0$ implies $x_{ij} = 0$, $\forall i \in N_{j}$, whereas $z_i = 1$ implies $x_{ij}z_{i} = x_{ij}$ for all feasible solutions.

Some variants and formulations of MKPC can be found in the literature. Dawande and Kalagnanam [42] proposed two integer linear programming formulations, one by separating the set of variables for modeling the color constraints and another where these color constraints are implicitly modeled without introducing new variables. They presented a polyhedral study of the problem and showed that the color constraints significantly change the classical multiple knapsack integer polytope. In addition they demonstrated that under certain sufficient conditions color constraints define the facets of the integer polytope. Kalagnanam et al. considered a bi-objective version in [108] where the second objective minimizes the unused weight of the slabs that are matched with orders. Authors proposed a mathematical formulation of the problem as well as a network flow-based heuristic. Experiments performed on real instances proved the efficiency of the heuristic approach to provide near-optimal solutions within a reasonable amount of time. Forrest et al. proposed in [63] a branch-and-price algorithm to deal with the previous formulation that helps in solving a real-life instance of MKPC, called mkc. However, the method could not solve a larger real-life instance, called mkc7 (mkc and mkc7 are two well-known instances in the MIPLIB²).

MKPC is also related to the variable-sized bin packing problem with color constraints which consists in assigning to each used bin a capacity from a set of available capacities. Each item is also characterized by a weight and a color among a set of colors. The objective is to minimize the residual capacity in the used bins such that: (i) each item is assigned to exactly one type of the bins, (ii) the total weights of items assigned to each bin do not exceed its capacity and (iii) no more than two colors appear in each used bin. This variant was introduced in [42] where authors presented an asymptotic polynomial approximation scheme that serves to classify the complexity of the problem. Later, Dawande et al. [44] proposed several approximation algorithms. They first considered the case where the maximum number of colors is set to two and then the general case. Then, Dawande et al. [43] developed an efficient heuristic algorithm which is used in a real context and the steel plant savings achieved $2.5 million per year. In a recent work, Kochetov and Kondakov [117] applied a VNS-based matheuristic to a special case where each item has zero weight and arbitrary number of colors with the objective of minimizing the number of bin used. VNS is used for the pricing problem as well as for approaching near-optimal solutions for randomly generated instances. Crévits et al. [37] considered another special case where each color is assigned to only one item. They considered several different linear formulations for that special case of the problem, including some standard ones. Out of the computational experiments reported by the authors, the one that appears to be the most promising is called the matching formulation. Experiments provided promising results for this formulation when it is compared to other classical ones. This work was extended in [82] where authors showed that for that special case instances with up to 20 bin sizes can be solved in less than 2 seconds.

Finally the constraint programming community also considered MKPC as a bin-packing problem with color constraints. The corresponding problem is problem number 38 in the CSPLIB³ and consists of 380 benchmark instances. Frisch et al. proposed in [65] a constraint-based model for the problem and added symmetry-breaking techniques as well as efficient implied constraints that help reducing significantly the search space. Heinz et al. solved all the 380 instances of CSPLIB using a column generation-based algorithm in [90]. The approach also solved the mkc instance but was not able to solve the mkc7 one. The problem was also efficiently solved in [181] where authors used constraint programming with an improved symmetry breaking scheme.

4 Conclusion and Suggestions

In this chapter we review a few variants of KP which are associated with recently introduced interesting applications. Our choice of variants is obviously personal and is restricted by writing space limitations. Accordingly, numerous existing KP variants are not addressed here. For each KP variant we consider, at least one formulation is provided, together with a list of existing applications for it. Then, we focused on the most recent and the most effective approaches for solving the problem. Quite clearly, we could have considered many other KP variants including quadratic knapsack problems or multi-objective knapsack problems for instance. Likewise, stochastic and robust versions of KPs have also been considered in the literature. For instance Caserta and Voß  introduced in [26] a robust version of the MMCKP and studied the relation between the deterministic and the robust problems. They showed that a given nonlinear model arising from the use of robust optimization can be transformed into an equivalent linear model and thus that the complexity of the deterministic version can be preserved. Online or bilevel knapsack problems are other examples of interesting variants (see., e.g., [23, 149]).

In our opinion the number of publications dealing with KP variants is not about to decrease, for the following reasons: (i) many of KP variants remain extremely challenging problems, even when considering very simple versions of them; (ii) as shown in this chapter and in the literature several recent works identify KP variants as sub-problems within even more difficult problems. Thus, the need of very effective approaches to solve KPs is still relevant; (iii) we can imagine that other new variants will emerge in the next few years, in particular by combining the characteristics of existing KPs. For instance Mansini et al. introduced recently the multiple multidimensional knapsack with family-split penalties which combines the M-KP and the MKP in [131]. In this problem the profit is not associated with each single item but with the family as a whole and to earn this profit it is necessary to select all the items of the family. A splitting penalty incurs when items from the same family are assigned to different knapsacks. The problem arises in distributed computing resource management items that are grouped into families. As noted by the authors efficiently handling large instances can be an interesting challenge. Thus, we encourage interested readers to consider both theoretical and more practicable works to help resolve the more emerging and difficult knapsack problems.