An Integer Programming Model for Binary Knapsack Problem with Value-Related Dependencies among Elements
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The {0,1}-knapsack problem with qualitative levels
A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We define a dominance relation over the feasible subsets of the given item set an…
RelationFit The Right NP-Hard Problem: End-to-end Learning of Integer Programming Constraints
Bridging logical and algorithmic reasoning with modern machine learning techniques is a fundamental challenge with potentially transformative impact. On the algorithmic side, many NP-Hard problems can be expressed as int…
Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neu…
Combinatorial OptimizationQuantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent…
Multi-Armed BanditsAdvances in Bayesian Network Learning using Integer Programming
We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allo…