An OR practitioner’s solution approach to the multidimensional knapsack problem

Abstract: The 0-1 Multidimensional Knapsack Problem (MKP) is an NP-Hard problem that has many important applications in business and industry. However, business and industrial applications typically involve large problem instances that can be time consuming to solve for a guaranteed optimal solution. There are many approximate solution approaches, heuristics and metaheuristics, for the MKP published in the literature, but these typically require the fine-tuning of several parameters. Fine-tuning parameters is not only time-consuming (especially for operations research (OR) practitioners), but also implies that solution quality can be compromised if the problem instances being solved change in nature. In this paper, we demonstrate an efficient and effective implementation of a robust population-based metaheuristic that does not require parameter fine-tuning and can easily be used by OR practitioners to solve industrial size problems. Specifically, to solve the MKP, we provide an efficient adaptation of the two-phase Teaching-Learning Based Optimization (TLBO) approach that was originally designed to solve continuous nonlinear engineering design optimization problems. Empirical results using the 270 MKP test problems available in Beasley’s OR-Library demonstrate that our implementation of TLBO for the MKP is competitive with published solution approaches without the need for time-consuming parameter fine-tuning.

How to cite this paper

 Kern, Z., Lu, Y & Vasko, F. (2020). An OR practitioner’s solution approach to the multidimensional knapsack problem.International Journal of Industrial Engineering Computations , 11(1), 73-82.

Refrences

Akçay, Y., Li, H., & Xu, S. H. (2007). Greedy algorithm for the general multidimensional knapsack problem. Annals of Operations Research, 150(1), 17.
Baroni, M. D. V., & Varejão, F. M. (2015, November). A shuffled complex evolution algorithm for the multidimensional knapsack problem. In Iberoamerican Congress on Pattern Recognition (pp. 768-775). Springer, Cham.
Boyer, V., Elkihel, M., & El Baz, D. (2009). Heuristics for the 0–1 multidimensional knapsack problem. European Journal of Operational Research, 199(3), 658-664.
Chu, P. C., & Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4(1), 63-86.
Fréville, A. (2004). The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research, 155(1), 1-21.
Frieze, A. M., & Clarke, M. R. B. (1984). Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses. European Journal of Operational Research, 15(1), 100-109.
Baghel, M., Agrawal, S., & Silakari, S. (2012). Survey of metaheuristic algorithms for combinatorial optimization. International Journal of Computer Applications, 58(19), 2709-2716.
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Multidimensional Knapsack Problems. In Knapsack problems(pp. 235-283). Springer, Berlin, Heidelberg.
Kong, X., Gao, L., Ouyang, H., & Li, S. (2015). Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm. Computers & Operations Research, 63, 7-22.
Laabadi, S., Naimi, M., El Amri, H., & Achchab, B. (2018). The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches. American Journal of Operations Research, 8(05), 395.
Labed, S., Gherboudj, A.,& Chikhi, S. (2011) A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem, International Journal of Computer Applications, 34(2), 11-16.
Lanza-Gutierrez, J. M., Crawford, B., Soto, R., Berrios, N., Gomez-Pulido, J. A., & Paredes, F. (2017). Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization. Expert Systems with Applications, 70, 67-82.
Meng, T., & Pan, Q. K. (2017). An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem. Applied Soft Computing, 50, 79-93.
Moraga, R. J., DePuy, G. W., & Whitehouse, G. E. (2005). Meta-RaPS approach for the 0-1 multidimensional knapsack problem. Computers & Industrial Engineering, 48(1), 83-96.
Newhart, D. D., Stott, K. L., & Vasko, F. J. (1993). Consolidating product sizes to minimize inventory levels for a multi-stage production and distribution system. Journal of the operational Research Society, 44(7), 637-644.
Rao, R. V., Savsani, V. J., & Vakharia, D. P. (2011). Teaching–learning-based optimization: a novel method for constrained mechanical design optimization problems. Computer-Aided Design, 43(3), 303-315.
Rezoug, A., & Boughaci, D. (2016). A self-adaptive harmony search combined with a stochastic local search for the 0-1 multidimensional knapsack problem. International Journal of Bio-Inspired Computation, 8(4), 234-239.
Rezoug A, Bader-El-Den M., & Boughaci D. (2018) Guided genetic algorithm for the multidimensional knapsack problem, Memetic Computing, 10, 29-42.
Vasko, F. J., Wolf, F. E., & Stott, K. L. (1989). A practical solution to a fuzzy two-dimensional cutting stock problem. Fuzzy Sets and Systems, 29(3), 259-275.
Vasko, F. J., Wolf, F. E., & Pflugrad, J. A. (1991). An efficient heuristic for planning mother plate requirements at Bethlehem Steel. Interfaces, 21(2), 1-7.
Vasko, F. J., Wolf, F. E., Stott, K. L., & Woodyatt, L. R. (1993). Adapting branch-and-bound for real-world scheduling problems. Journal of the Operational Research Society, 44(5), 483-490.
Vasko, F. J., Newhart, D. D., & Strauss, A. D. (2005). Coal blending models for optimum cokemaking and blast furnace operation. Journal of the Operational Research Society, 56(3), 235-243.
Vasko, F. J., & Stott, K. L. (2008). Strategic Planning: OR to the Rescue. OR Insight, 21(3), 26-32.
Vasko, F.J., Lu, Y., & Zyma, K. (2016). An empirical study of population-based metaheuristics for the multiple-choice multidimensional knapsack problem, International Journal of Metaheuristics, 5(3-4), 193-225.
Vasko, F.J., & Y. Lu, Y.(2017). Binarization of continuous metaheuristics to solve the set covering problem: Simpler is better. invited talk, 21st Triennial Conference of The International Federation of Operational Research Societies (IFORS), Quebec, Canada, July 17-21, 2017.
Zyma, K., Lu, Y., & Vasko, F.J. (2015). Teacher training enhances the teaching-learning-based optimization metaheuristic when used to solve multiple-choice multidimensional knapsack problems, International Journal of Metaheuristics, 4(3-4), 268-293.