A Hybrid Lagrangian Search Ant Colony Optimization Algorithm for the Multidimensional Knapsack Problem

AbstractMultidimensional knapsack problem (MKP) is an NP-hard problem, the goal of which is to find a subset of objects that maximizes a given objective function while satisfying some resource constraints. To be solved in a relatively short time an approximate method that returns near-optimal solutions can or, often, should be used, especially for large and hard instances. In this paper, an approximate method combining Ant Colony Optimization (ACO) metaheuristic and Lagrangian heuristic is proposed to solve MKP. The idea is to use the solutions obtained by the Lagrangian heuristic to guide ants in their search of good paths by laying pheromone trails. Experiments on large benchmark instances on MKP show that the hybrid algorithm performs better than the ACO algorithm and the Lagrangian heuristic when tested separately