A Binary differential search algorithm for the 01 multidimensional knapsack problem
Abstract
The multidimensional knapsack problem (MKP) is known to be NPhard 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 01 MKPs where the stochastic search is guided by a Brownian motionlike random walk. Our proposed method comprises two main operations: discrete solution generation and feasible solution production. Discrete solutions are generated by integrating Brownian motionlike random search with an integerrounding 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 01 MKPs using our proposed algorithm as well as some existing metaheuristic methods. The numerical results obtained demonstrated that our algorithm performs better than existing metaheuristic methods. Furthermore, our algorithm has the capacity to solve largescale 01 MKPs.
Citation
Source Title
ISSN
School
Collection
Related items
Showing items related by title, author, creator and subject.

Woon, Siew Fang (2009)Optimal control problems arise in many applications, such as in economics, finance, process engineering, and robotics. Some optimal control problems involve a control which takes values from a discrete set. These problems ...

Chong, Yen N. (2001)General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution ...

Zhang, X.; Wu, Changzhi; Li, J.; Wang, X.; Yang, Z.; Lee, J.; Jung, K. (2016)The multidimensional knapsack problem (MKP) is a wellknown NPhard optimization problem. Various metaheuristic methods are dedicated to solve this problem in literature. Recently a new metaheuristic algorithm, called ...