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

摘要

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.