A Binary differential search algorithm for the 0-1 multidimensional knapsack problem
Embargo Lift Date
MetadataShow full item record
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.
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 well-known NP-hard optimization problem. Various meta-heuristic methods are dedicated to solve this problem in literature. Recently a new meta-heuristic algorithm, called ...