« Back to top page

Combinatorial Optimization

Combinatorial Optimization

Multi-dimensional Knapsack Problem

Abstract The Multi-dimensional Knapsack Problem (MKP) is a fundamental combinatorial optimization problem that generalizes the classic knapsack problem to multiple dimensions. In this problem, each item has multiple attributes (e.g., weight, volume, size) and the goal is to maximize the total value of selected items while satisfying constraints on each attribute. Despite its conceptual simplicity, the MKP is NP-hard and appears frequently in real-world applications, such as resource allocation, capital budgeting, and project selection, as remarked in recent surveys e.