An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values
| Autor: | Asghar Moeini, David M. W. Powers, Davoud Mougouei |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
Branch and price Continuous knapsack problem Binary number 020207 software engineering 02 engineering and technology Cutting stock problem Knapsack problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Change-making problem Integer programming Generalized assignment problem Mathematics |
| Zdroj: | AI 2017: Advances in Artificial Intelligence ISBN: 9783319630038 Australasian Conference on Artificial Intelligence |
| DOI: | 10.1007/978-3-319-63004-5_12 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|