Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method

Abstract

An adaptive memory projection (referred as AMP) method is developed for multidimensional knapsack problems (referred as the MKP) with generalized upper bound constraints. All the variables are divided into several generalized upper bound (referred as GUB) sets and at most one variable can be chosen from each of the GUB sets. The MKP with GUBs (referred as the GUBMKP) can be applied to many real-world problems, such as capital budgeting, resource allocation, cargo loading, and project selection. Due to the complexity of the GUBMKP, good metaheuristics are sought to tackle this problem.

The AMP method keeps track of components of good solutions during the search and creates provisional solution by combining components of better solutions. The projection method, which can free the selected variables while fixing the others, is very useful for metaheuristics, especially when tackling large-scale combinatorial optimization. In this paper, the AMP method is implemented by iteratively using critical event tabu search as a search routine, and CPLEX in the referent optimization stage. Variables that are strongly determined, consistent, or attractive, are identified in the search process. Selected variables from this pool are fed into CPLEX as a small subproblem. In addition to the diversification effect within critical event tabu search, the pseudo-cut inequalities and an adjusted frequency penalty scalar are also applied to increase opportunities of exploring new regions.

This study conducts a comprehensive sensitivity analysis on the parameters and strategies used in the proposed AMP method. The computational results show several variants of the AMP method outperforms the tight oscillation method in the literature of GUBMKP. On average, consistent variables tend to perform best as a pure strategy. A pure strategy equipped with local search can lead into even better results. Last but not least, testing different types of variables in the referent optimization stage before selecting just one of the pure strategies is found to be very helpful.

Introduction

This paper considers the multidimensional knapsack problem (commonly known as the MKP) with generalized upper bound (referred to GUB hereafter) constraints as shown in the following formulation: a set of n items, $N\equiv \{1,\dots ,n\}$, should be packed to maximize the overall profit where item j can contribute c_j (Eq. (1)), such that the capacity limitation $b_i,i\in M\equiv \{1,\dots ,m\}$, of each of the m knapsack constraints will be met as selecting item j will use a_ij units of resource i (Eq. (2)). Items performing the same function are grouped into one category although the contribution of each of them are different generally. All the items are partitioned into g mutually exclusive subsets and at most one item qcan be chosen from each of these subsets (Eqs. (3), (5), (6)). If an item j is chosen, then the associated variable x_j equals 1; otherwise it equals 0 (Eq. (4)). All the parameters of the objective function and the constraints are assumed to be nonnegative (Eq. (7)).

Formulation 1 GUBMKP

$$\mathrm{Maximize}\sum _{j\in N}{c}_j{x}_j$$

$$\mathrm{Subject}\mathrm{to}\sum _{j\in N}{a}_{\mathit{ij}}{x}_j\le b_i,\forall i\in M\equiv \{1,\dots ,m\},$$

$$\sum _{j\in N_h}{x}_j\le 1,\forall h\in G\equiv \{1,\dots ,g\},$$

$$x_j\in \{\mathrm{0,1}\},\forall j\in N\equiv \{1,\dots ,n\},$$

$$\mathrm{where}\bigcup _{h=1}^g{N}_h=N,$$

$$N_p\cap N_q=\varnothing \forall p,q\in G,p\ne q,$$

$$a_{\mathit{ij}},c_j,b_i\ge 0\forall i\in M,j\in N.$$

The formulation of the MKP consists of Eqs. (1), (2), (4), (7). The GUBMKP model can be obtained by adding the GUB constraints (Eq. (3)) with the properties stated in Eqs. (5), (6). Following the first application on capital budgeting [1], the MKP has been used to model various application such as project selection, cutting stock, cargo loading, and combinatorial auctions [2], [3], [4], [5]. The GUBMKP can be transformed to the multiple-choice multidimensional knapsack problem (referred to the MMKP) by adding a slack variable in each of the GUB constraints (Eq. (3)) and making it an equality constraint. In fact, the MMKP is a combination of the MKP and the multiple-choice knapsack problem (MCKP). The MCKP has many applications such as menu planning and capital budgeting where there is only one resource constraint and candidates to be chosen fall into disjoint subsets (e.g., [6], [7]). With this transformation, an active slack variable (i.e., it equals 1) indicates that the corresponding GUB constraint is not tight. Therefore, the GUBMKP can be seen as a relaxation of the MMKP. The MMKP has been used to model configuration problems that involve options [8] (e.g., modeling real-time multimedia domain [9] and building a utility model for a multisession adaptive multimedia system [10], [11]), whereas the GUBMKP formulation has been used to model a striking asset allocation problem [12] and a surveillance system for port and waterway security [13].

The MKP is NP-Hard [14], so is its close variant GUBMKP. Polynomial algorithms to solve it to optimality cannot be found unless P=NP [15]. Metaheuristics have been shown effective in approximating optimal solutions for many difficult large-scale optimization problems. This paper utilizes the idea of adaptive memory projection proposed by Glover [16], where collections of important variables are identified by the underlying search heuristic, and the corresponding subproblem is solved by CPLEX, iteratively.

The remainder of this paper is organized as follows. Section 2 reviews the literature most relevant to the GUBMKP. Section 3 discusses the AMP methodology and the details of implementation. Computational results are shown in Section 4. Conclusions and future directions are discussed in Section 5.