Abstract
The K-Constraint Multiple Knapsack Problem (K-MKP) is a generalization of the multiple knapsack problem, which is one of the representative combinatorial optimization problems known to be NP-hard. In K-MKP, each item has K types of weights and each knapsack has K types of capacity. In this paper, we propose several very large-scale neighborhood search (VLSN) algorithms to solve K-MKP. One of the VLSN algorithms incorporates a novel approach that consists of randomly perturbing the current solution in order to efficiently produce a set of simultaneous non-profitable moves. These moves would allow several items to be transferred from their current knapsacks and assigned to new knapsacks, which makes room for new items to be inserted through multi-exchange movements and allows for improved solutions. Computational results presented show that the method is effective, and provides better solutions compared to exact algorithms run for the same amount of time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. (1993). Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice Hall.
Ahuja, R.K., J.B. Orlin, and A. Tiwari. (2000). “A Greedy Genetic Algorithm for the Quadratic Assignment Problem.” Computers and Operations Research 27, 917–934.
Ahuja, R.K., J.B. Orlin, and D. Sharma. (2001). “Multi-Exchange Neighborhood Search Algorithms for the Capacitated Minimum Spanning Tree Problem.” Mathematical Programming 91, 71–97.
Ahuja, R.K., O. Ergun, J.B. Orlin, and A.P. Punnen. (2002a). “A Survey of Very Large Scale Neighborhood Search Techniques.” Discrete Applied Mathematics 123, 75–102.
Ahuja, R.K., K.C. Jha, J.B. Orlin, and D. Sharma. (2002b). “Very Large-Scale Neighborhood Search Algorithms for the Quadratic Assignment Problem.” INFORMS Journal on Computing (to appear).
Ahuja, R.K., A. Kumar, K.C. Jha, and J.B. Orlin. (2003a). “Exact and Heuristic Methods for the Weapon Target Assignment Problem.” Submitted to Operations Research.
Ahuja, R.K., J.B. Orlin, and D. Sharma. (2003b). “A Composite Neighborhood Search Algorithm for the Capacitated Minimum Spanning Tree Problem,” Operations Research Letters 31, 185–194.
Ahuja, R.K., J.B. Orlin, S. Pallotino, M.P. Scaparra, and M.G Scutellà. (2003c). “A Multi-Exchange Heuristic for the Capacitated Facility Location Problem.” Management Science (to appear).
Barceló, J. and J. Casanovas. (1984). ”A Heuristic Lagrangean Algorithm for the Capacitated Plant Location Problem.” European Journal of Operational Research15, 212–226.
Chu, P.C. and J.E. Beasley. (1998). “A Genetic Algorithm for the Multidimensional Knapsack Problem.” Journal of Heuristics 4, 63–88.
Cord, J. (1964). “A Method for Allocating Funds to Investment Projects When Returns are Subject to Uncertainty.” Management Science10(2), 335–341.
Drexl, A. (1988). “A Simulated Annealing Approach for the Multiconstraint Zero-One Knapsack Problem.” Computing 40, 1–8.
Gabrel, V. and M. Minoux. (2002). “A Scheme for Exact Separation of Extended Cover Inequalities and Application to Multidimensional Knapsack Problems.” Operations Research Letters 30, 252–264.
Gavish, B. and H. Pirkul. (1985). “Efficient Algorithms for Solving Multi-Constraint Zero-One Knapsack Problems to Optimality.” Mathematical Programming 31, 78–105.
Gearing, C.E., W.W. Swart, and T. Var. (1973). “Determining the Optimal Investment Policy for the Tourism Sector of a Developing Country.” Management Science 20, 487–497.
Glover, F. and M. Laguna. (1997). Tabu Search. Norwell, MA: Kluwer Academic Publishers.
Lokkentagen, A. and F. Glover. (1996). “Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems.” In I.H. Osman nd K.P. Kelly (eds.), Meta-Heuristics: Theory and Applications. Kluwer Academic Publishers, pp. 467-487.
Martello, S. and P. Toth. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester, UK.
Martello, S. and P. Toth. (2003). “An Exact Algorithm for the Two-Constraint 0-1 Knapsack Problem.” Operations Research 51(5), 826–835.
Petersen, C.C. (1967). “Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R&D Projects.” Management Science13(9), 736–750.
Pesch, E. and F. Glover. (1997). “TSP Ejection Chains.” Discrete Applied Mathematics 76, 165–181.
Pisinger, D. (1999). An Exact Algorithm for Large Multiple Knapsack Problems. European Journal of Operational Research 114, 528–541.
Sinha, K.C, T. Kaji, and C.C. Liu. (1981). “Optimal Allocation of Funds for Highway Safety Improvement Projects.” Transportation Research Record 808, 24–30.
Thompson, P.M. and J.B. Orlin. (1989). “The Theory of Cyclic Transfers”. MIT Operations Research Report 200–89, Cambridge, MA.
Thompson, P.M. and H.N. Psaraftis. (1993). “Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems.” Operations Research 41, 935–946.
Weingartner, H.M. and D.N. Ness. (1967). “Methods for the Solution of the Multidimensional 0/1 Knapsack Problem.” Operations Research 15, 83–103.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper was written during Dr. Cunha's sabbatical at the Industrial and Systems Engineering Department at the University of Florida, Gainesville as a visiting faculty
Rights and permissions
About this article
Cite this article
Ahuja, R.K., Cunha, C.B. Very Large-Scale Neighborhood Search for the K-Constraint Multiple Knapsack Problem. J Heuristics 11, 465–481 (2005). https://doi.org/10.1007/s10732-005-2634-9
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10732-005-2634-9