An Integer Programming Model for Binary Knapsack Problem with Value-Related Dependencies among Elements
This addresses a specific optimization problem for researchers in operations research or AI, but it is incremental as it extends existing knapsack models with fuzzy dependencies.
The paper tackles the binary knapsack problem with imprecise value-related dependencies among items by proposing an integer programming model that uses fuzzy graphs to capture these dependencies, resulting in a method to handle such uncertainties in optimization.
Binary Knapsack Problem (BKP) is to select a subset of an element (item) set with the highest value while keeping the total weight within the capacity of the knapsack. This paper presents an integer programming model for a variation of BKP where the value of each element may depend on selecting or ignoring other elements. Strengths of such Value-Related Dependencies are assumed to be imprecise and hard to specify. To capture this imprecision, we have proposed modeling value-related dependencies using fuzzy graphs and their algebraic structure.