An integer linear programming model for binary knapsack problem with dependent item values
Paper
Paper/Presentation Title | An integer linear programming model for binary knapsack problem with dependent item values |
---|---|
Presentation Type | Paper |
Authors | Mougouei, Davoud (Author), Powers, David M.W. (Author) and Moeini, Ashgar (Author) |
Editors | Peng, Wei, Alahakoon, Damminda and Li, Xiaodong |
Journal or Proceedings Title | AI 2017: Advances in Artificial Intelligence |
Number of Pages | 11 |
Year | 2017 |
Place of Publication | Switzerland |
ISBN | 9783319630038 |
9783319630045 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-319-63004-5_12 |
Web Address (URL) of Paper | https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12 |
Web Address (URL) of Conference Proceedings | https://link.springer.com/book/10.1007/978-3-319-63004-5 |
Conference/Event | 30th Australasian Joint Conference on Artificial Intelligence (AI 2017) |
Event Details | Rank B B B B B |
Event Details | 30th Australasian Joint Conference on Artificial Intelligence (AI 2017) Event Date 19 to end of 20 Aug 2017 Event Location Melbourne, Australia |
Abstract | Binary Knapsack Problem (BKP) is to select a subset of items with the highest value while keeping the size within the capacity of the knapsack. This paper presents an Integer Linear Programming (ILP) model for a variation of BKP where the value of an item may depend on presence or absence of other items in the knapsack. 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. We have demonstrated through simulations that our proposed ILP model is scalable to large number of items. |
Keywords | binary knapsack problem; integer linear programming; dependency; value; fuzzy graph |
Contains Sensitive Content | Does not contain sensitive content |
ANZSRC Field of Research 2020 | 461299. Software engineering not elsewhere classified |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Flinders University |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q6yzv/an-integer-linear-programming-model-for-binary-knapsack-problem-with-dependent-item-values
122
total views9
total downloads1
views this month0
downloads this month