A hybrid optimization algorithm that integrates ant colony optimization(ACO) with Lagrangian relaxation(LR) is proposed for solving NP-hard and strongly constrained multidimensional knapsack problems(MKP). This algorithm takes ACO as the basic framework and defines a novel utility index for MKP based on LR dual information. ACO endows the algorithm with global search ability, and the designed utility index organically combines the optimization object and the constraint conditions of MKP together. Benefiting from this characteristic, the utility index is used to define the core problem for MKP on the one hand, with the aim of reducing the problem scale. On the other hand, it can be used as the heuristic factor of ACO, directing the algorithm to intensively search those promising solution areas. Simulation results on a large number of benchmark instances show that the proposed algorithm is of strong robustness. Compared with existing algorithms, it is also highly competitive in terms of solution quality and efficiency.