These instances are either test problems collected from the literature or test instances solved in Chu & Beasley (1998). The widely used benchmark instances in the literature can be found at the online OR-Library with a complete explanation about the format and content of each benchmark set.
The number of variables is m while the number of constraints is n. Where c is the profit-per-item vector, b is the right hand side vector or the capacity of each knapsack, x is a vector of binary variables indicating whether an item is selected, and A is the constraints’ coefficients matrix. The mathematical formulation of the MKP is: Here we will only limit our scope to the binary MKP. Avid readers interested in the various versions of knapsack problems are referred to the book Knapsack Problems by Kellerer, Pferschy and Pisinger for more details.
The goal is the same to find a subset of items that maximizes the total profit/gain (objective function), however, the difference is that instead of having a single knapsack or resource, there are multiple knapsacks/resources (each is a separate constraint) and the subset of items should not violate the capacity of any of these knapsacks. The MKP is an NP-hard extension to the standard binary knapsack selection problem. Photo by Lukas Robertson on Unsplash The Multidimensional Knapsack Problem ‘MKP’
0 kommentar(er)
