An OR practitioner’s solution approach to the multidimensional knapsack problem
- 1 January 2020
- journal article
- research article
- Published by Growing Science in International Journal of Industrial Engineering Computations
- Vol. 11 (1), 73-82
- https://doi.org/10.5267/j.ijiec.2019.6.004
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. (C) 2020 by the authors; licensee Growing Science, CanadaKeywords
This publication has 13 references indexed in Scilit:
- Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimizationExpert Systems with Applications, 2017
- An improved fruit fly optimization algorithm for solving the multidimensional knapsack problemApplied Soft Computing, 2017
- Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithmComputers & Operations Research, 2015
- A Shuffled Complex Evolution Algorithm For the Multidimensional Knapsack ProblemPublished by Springer Science and Business Media LLC ,2015
- Teaching–learning-based optimization: A novel method for constrained mechanical design optimization problemsComputer-Aided Design, 2011
- Heuristics for the 0–1 multidimensional knapsack problemEuropean Journal of Operational Research, 2009
- Greedy algorithm for the general multidimensional knapsack problemAnnals of Operations Research, 2006
- Coal blending models for optimum cokemaking and blast furnace operationJournal of the Operational Research Society, 2005
- Meta-RaPS approach for the 0-1 Multidimensional Knapsack ProblemComputers & Industrial Engineering, 2005
- The multidimensional 0–1 knapsack problem: An overviewEuropean Journal of Operational Research, 2004