An OR practitioner’s solution approach to the multidimensional knapsack problem
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 ar...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Growing Science
2019-01-01
|
| Series: | International Journal of Industrial Engineering Computations |
| Subjects: | |
| Online Access: | http://www.growingscience.com/ijiec/Vol11/IJIEC_2019_18.pdf |
| _version_ | 1819128599687462912 |
|---|---|
| author | Zachary Kern Yun Lu Francis J. Vasko |
| author_facet | Zachary Kern Yun Lu Francis J. Vasko |
| author_sort | Zachary Kern |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-22T08:30:23Z |
| format | Article |
| id | doaj.art-ef894b199aa3460f942ec0bf2a764fdf |
| institution | Directory Open Access Journal |
| issn | 1923-2926 1923-2934 |
| language | English |
| last_indexed | 2024-12-22T08:30:23Z |
| publishDate | 2019-01-01 |
| publisher | Growing Science |
| record_format | Article |
| series | International Journal of Industrial Engineering Computations |
| spelling | doaj.art-ef894b199aa3460f942ec0bf2a764fdf2022-12-21T18:32:31ZengGrowing ScienceInternational Journal of Industrial Engineering Computations1923-29261923-29342019-01-01111738210.5267/j.ijiec.2019.6.004An OR practitioner’s solution approach to the multidimensional knapsack problemZachary KernYun LuFrancis J. Vasko 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.http://www.growingscience.com/ijiec/Vol11/IJIEC_2019_18.pdfMixed-integer programmingPayment termTrade creditLogisticsQuantity flexible contractFactoring |
| spellingShingle | Zachary Kern Yun Lu Francis J. Vasko An OR practitioner’s solution approach to the multidimensional knapsack problem International Journal of Industrial Engineering Computations Mixed-integer programming Payment term Trade credit Logistics Quantity flexible contract Factoring |
| title | An OR practitioner’s solution approach to the multidimensional knapsack problem |
| title_full | An OR practitioner’s solution approach to the multidimensional knapsack problem |
| title_fullStr | An OR practitioner’s solution approach to the multidimensional knapsack problem |
| title_full_unstemmed | An OR practitioner’s solution approach to the multidimensional knapsack problem |
| title_short | An OR practitioner’s solution approach to the multidimensional knapsack problem |
| title_sort | or practitioner s solution approach to the multidimensional knapsack problem |
| topic | Mixed-integer programming Payment term Trade credit Logistics Quantity flexible contract Factoring |
| url | http://www.growingscience.com/ijiec/Vol11/IJIEC_2019_18.pdf |
| work_keys_str_mv | AT zacharykern anorpractitionerssolutionapproachtothemultidimensionalknapsackproblem AT yunlu anorpractitionerssolutionapproachtothemultidimensionalknapsackproblem AT francisjvasko anorpractitionerssolutionapproachtothemultidimensionalknapsackproblem AT zacharykern orpractitionerssolutionapproachtothemultidimensionalknapsackproblem AT yunlu orpractitionerssolutionapproachtothemultidimensionalknapsackproblem AT francisjvasko orpractitionerssolutionapproachtothemultidimensionalknapsackproblem |