آمیخته شدن بهینه سازی کلونی مورچه ها با آرام سازی لاگرانژ برای مسئله چند انتخابی و چند بعدی کوله پشتی

The multiple-choice multidimensional knapsack problem (MMKP) concerns a wide variety of practical problems. It is strongly constrained and NP-hard; thus searching for an efficient heuristic approach for MMKP is of great significance. In this study, we attempt to solve MMKP by fusing ant colony optimization (ACO) with Lagrangian relaxation (LR). The algorithm used here follows the algorithmic scheme of max–min ant system for its outstanding performance in solving many other combinatorial optimization problems. The Lagrangian value of the item in MMKP, obtained from LR, is used as the heuristic factor in ACO since it performs best among the six domain-based heuristic factors we define. Furthermore, a novel infeasibility index is proposed for the development of a new repair operator, which converts possibly infeasible solutions into feasible ones. The proposed algorithm was compared with four existing algorithms by applying them to three groups of instances. Computational results demonstrate that the proposed algorithm is capable of producing competitive solutions.

The multiple-choice multidimensional knapsack problem (MMKP) is a variant of the classical 0-1 knapsack problem (KP). Given a set of knapsacks with limited resources and some disjoint groups of items, where each item has a profit value and requires a certain amount of resources, MMKP aims to fill the knapsacks by picking exactly one item from each group, such that the total profit value of the collected items is maximized and no resource constraint of the knapsacks is violated. MMKP concerns a wide variety of practical problems, such as quality adaptation and admission control in multimedia services [17] and [18] and service level agreement management [29]. Large numbers of other resource allocation problems can also be directly mapped to MMKP. The reader can refer to [16] and [21] and the references therein for more details. MMKP is known to be NP-hard in the strong sense [20]; therefore, it is difficult, but of great significance, to develop efficient algorithms for MMKP. Due to its practical values, MMKP has attracted increasing attention from the research community since the mid-1990s. The algorithms, developed for solving MMKP, can be divided into two classes, namely, exact algorithms and heuristics. Exact algorithms, mainly based on Branch-and-Bound (B&B), strive to produce the optimal solution for MMKP. Two B&B algorithms were proposed by Khan [17] and Sbihi [24], respectively. They both use the best-first search strategy. Khan’s algorithm employs the solution to the linear programming relaxation (LPR) of MMKP as the upper bound at different levels of the search tree, while Sbilhi’s algorithm achieves an upper bound by solving an auxiliary multiple-choice knapsack problem (MCKP) related to the original MMKP. More recently, Razzazi and Ghasemi [23] developed a new B&B algorithm for MMKP based on the core concept, a concept widely applied to other KPs [16]. In their algorithm, the search tree is arranged according to the defined orderings in the core, and is navigated in a depth-first manner. However, all these exact algorithms can only be used to solve instances of limited size due to the NP-hardness of MMKP. Therefore, many research efforts have been devoted to the development of heuristics that can find good or near optimal solutions within an acceptable computation time. The first heuristic, proposed by Moser et al. [20], adopts the concept of graceful degradation from the most valuable item defined based on Lagrangian multipliers. Based on Toyoda’s concept of aggregate resource [28], Khan et al. [17] and [18] designed a heuristic named HEU, which finds a solution by only upgrading the selected item of a group. A modified version of HEU, M-HEU, was presented by Akbar et al. in [1]. It improves the total value of a solution with an upgrade operation, followed by one or more downgrade operations. To shorten its runtime, M-HEU was further parallelized on multiple processors [25]. Akbar et al. [2] also proposed a convex hull based method, which maps the multidimensional resource constraints to a single dimension with a penalty vector, and reduces the search space by constructing convex hulls. Based on surrogate relaxation, Parra-Hernandez and Dimopoulos [21] proposed a heuristic named HMMKP. It uses the Lagrangian multipliers, obtained by solving the LPR of the multidimensional knapsack problem (MDKP) reduced from the original MMKP, as the surrogate multipliers. For a review of the existing heuristics for MMKP, the reader may refer to [14]. It is a common practice to apply metaheuristics to combinatorial optimization problems (COPs). Compared with the general heuristic, the metaheuristic searches the solution space in a systematic way, and usually achieves considerably high performance in relatively long computation time. So far, only a small number of metaheuristics directly deal with MMKP. The two algorithms proposed by Hifi et al. [12] and [13] can be considered as this type. The first one, based on guided local search [12], uses memory to guide the search to the promising regions of the solution space by penalizing the bad features of previously visited solutions. The other one, based on reactive local search (RLS) [13], performs explicit checking for the repetition of configurations, deblocking to escape from local maxima, and degrading to introduce diversification. Moreover, Hiremath [14] developed three tabu search approaches and obtained decent results. The column generation method designed by Cherfi and Hifi [5] for MMKP is also in the spirit of the metaheuristic. In this paper, we present a hybrid algorithm, which solves MMKP by fusing ant colony optimization (ACO) [7], [9] and [10] with Lagrangian relaxation (LR) [30]. For the convenience of description, we name it AL-MMKP. ACO is a population-based metaheuristic proposed by Dorigo et al. [7] in the early 1990s from the inspiration of the foraging behavior of the real ant colony. The idea of applying ACO to MMKP is motivated by the following three factors. First, ACO has attracted many research efforts since its debut. Several excellent ACO variants have been developed and applied to a great variety of hard COPs [10], including some types of KPs [15] and [19] and some resource-constrained scheduling problems [4]. To the best of our knowledge, ACO has never been used to solve MMKP so far. Second, it has been found that the domain-based heuristic factor is useful in solving most COPs. LR can provide efficient heuristic factors for constrained problems, and ACO supports the use of such factor to improve its performance. Third, ACO is amenable to parallel implementation, which makes it possible that some real-time MMKPs, such as the admission control problem in the adaptive multimedia server system, can be solved more quickly. AL-MMKP follows the algorithmic scheme of max–min ant system (MMAS) [27], one of the most outstanding ACO variants. AL-MMKP also fully takes into account the characteristics of MMKP. When constructing solutions, it uses a single-group-oriented method, which allows artificial ants to generate solutions efficiently. Six domain-based heuristic factors are defined for MMKP. The Lagrangian value of the item in MMKP is integrated into ACO since it performs best among these six heuristic factors. The solutions directly produced by ACO may be infeasible due to the strong constraints in MMKP. To solve this problem, we propose a novel infeasibility index and develop a repair operator based on it. Compared with the existing repair operators, the new operator can produce a feasible solution with low computation cost. The remainder of this paper is organized as follows. In Section 2, we formally describe the MMKP and one of its LR forms. In Section 3, we present the detailed strategies used in AL-MMKP. The computational experiments and results are given in Section 4. Finally, conclusions are drawn in Section 5.

In this paper, a hybrid algorithm named AL-MMKP is presented. It solves the multiple-choice multidimensional knapsack problem by fusing ant colony optimization (ACO) with Lagrangian relaxation (LR). Two solution construction methods, the single-group-oriented method and the multiple-group-oriented method, are designed for ACO, and it is found that the single-group-oriented method can generate solutions more efficiently. AL-MMKP employs the Lagrangian value of the item obtained from LR as the default heuristic factor, since the Lagrangian value implicates the information from both optimization objective and constraints, and performs best among the six domain-based heuristic factors we define. In addition, an effective repair operator is developed to tackle possible infeasible solutions generated by ants. We compared AL-MMKP with four existing algorithms. Computational results indicate that AL-MMKP performs better than the existing algorithms, excluding MRLS. The key feature that makes MRLS competitive is its tabu list management mechanism. We may attempt to include such a mechanism in AL-MMKP in our future research. The work done in this study also demonstrates the feasibility of fusing ACO with LR, and their high potential in solving hard, strongly constrained combinatorial optimization problems.