A Binary differential search algorithm for the 0-1 multidimensional knapsack problem
The multidimensional knapsack problem (MKP) is known to be NP-hard in operations research and it has a wide range of applications in engineering and management. In this study, we propose a binary differential search method to solve 0-1 MKPs where the stochastic search is guided by a Brownian motion-...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2014
|
| Online Access: | http://purl.org/au-research/grants/arc/LP140100873 http://hdl.handle.net/20.500.11937/27975 |
| _version_ | 1848752411947040768 |
|---|---|
| author | Liu, J. Wu, Changzhi Cao, J. Wang, X. Teo, K. |
| author_facet | Liu, J. Wu, Changzhi Cao, J. Wang, X. Teo, K. |
| author_sort | Liu, J. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | The multidimensional knapsack problem (MKP) is known to be NP-hard in operations research and it has a wide range of applications in engineering and management. In this study, we propose a binary differential search method to solve 0-1 MKPs where the stochastic search is guided by a Brownian motion-like random walk. Our proposed method comprises two main operations: discrete solution generation and feasible solution production. Discrete solutions are generated by integrating Brownian motion-like random search with an integer-rounding operation. However, the rounded discrete variables may violate the constraints. Thus, a feasible solution production strategy is used to maintain the feasibility of the rounded discrete variables. To demonstrate the efficiency of our proposed algorithm, we solved various 0-1 MKPs using our proposed algorithm as well as some existing meta-heuristic methods. The numerical results obtained demonstrated that our algorithm performs better than existing meta-heuristic methods. Furthermore, our algorithm has the capacity to solve large-scale 0-1 MKPs. |
| first_indexed | 2025-11-14T08:08:12Z |
| format | Journal Article |
| id | curtin-20.500.11937-27975 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:08:12Z |
| publishDate | 2014 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-279752022-11-23T03:27:38Z A Binary differential search algorithm for the 0-1 multidimensional knapsack problem Liu, J. Wu, Changzhi Cao, J. Wang, X. Teo, K. The multidimensional knapsack problem (MKP) is known to be NP-hard in operations research and it has a wide range of applications in engineering and management. In this study, we propose a binary differential search method to solve 0-1 MKPs where the stochastic search is guided by a Brownian motion-like random walk. Our proposed method comprises two main operations: discrete solution generation and feasible solution production. Discrete solutions are generated by integrating Brownian motion-like random search with an integer-rounding operation. However, the rounded discrete variables may violate the constraints. Thus, a feasible solution production strategy is used to maintain the feasibility of the rounded discrete variables. To demonstrate the efficiency of our proposed algorithm, we solved various 0-1 MKPs using our proposed algorithm as well as some existing meta-heuristic methods. The numerical results obtained demonstrated that our algorithm performs better than existing meta-heuristic methods. Furthermore, our algorithm has the capacity to solve large-scale 0-1 MKPs. 2014 Journal Article http://hdl.handle.net/20.500.11937/27975 10.1016/j.apm.2016.06.002 http://purl.org/au-research/grants/arc/LP140100873 Elsevier fulltext |
| spellingShingle | Liu, J. Wu, Changzhi Cao, J. Wang, X. Teo, K. A Binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| title | A Binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| title_full | A Binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| title_fullStr | A Binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| title_full_unstemmed | A Binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| title_short | A Binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| title_sort | binary differential search algorithm for the 0-1 multidimensional knapsack problem |
| url | http://purl.org/au-research/grants/arc/LP140100873 http://hdl.handle.net/20.500.11937/27975 |