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.

+More

constraints rounded discrete variables binary differential search method metaheuristic methods discrete solution generation operations research integerrounding operation largescale 01 mkps feasible solution production strategy algorithm engineering and multidimensional knapsack problem mkp stochastic search brownian motionlike random search

Changzhi Wu,Jianjun Liu, Jiang Cao, Xiangyu Wang, Kok Lay Teo,.A Binary differential search algorithm for the 0–1 multidimensional knapsack problem. 40 (23–24),9788-9805.

Changzhi Wu, et al."A Binary differential search algorithm for the 0–1 multidimensional knapsack problem" 40

Changzhi Wu,Jianjun Liu, Jiang Cao, Xiangyu Wang, Kok Lay Teo,"A Binary differential search algorithm for the 0–1 multidimensional knapsack problem"