An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values

Davoud Mougouei; David M.W. Powers; Asghar Moeini

doi:10.1007/978-3-319-63004-5_12

An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values

Davoud Mougouei, David M.W. Powers, Asghar Moeini

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

13 Citations (Scopus)

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.

Original language	English
Title of host publication	AI 2017
Subtitle of host publication	Advances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings
Editors	Wei Peng, Damminda Alahakoon, Xiaodong Li
Place of Publication	Switzerland
Publisher	Springer-Verlag
Pages	144-154
Number of pages	11
ISBN (Electronic)	9783319630045
ISBN (Print)	9783319630038
DOIs	https://doi.org/10.1007/978-3-319-63004-5_12
Publication status	Published - 9 Jul 2017
Event	30th Australasian Joint Conference on Artificial Intelligence, AI 2017 - Melbourne, Australia Duration: 19 Aug 2017 → 20 Aug 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10400 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	30th Australasian Joint Conference on Artificial Intelligence, AI 2017
Country/Territory	Australia
City	Melbourne
Period	19/08/17 → 20/08/17

Keywords

Binary knapsack problem
Dependency
Fuzzy graph
Integer linear programming
Value

Access to Document

10.1007/978-3-319-63004-5_12Licence: In Copyright

https://rdcu.be/dd54LLicence: In Copyright

Cite this

Mougouei, D., Powers, D. M. W., & Moeini, A. (2017). An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values. In W. Peng, D. Alahakoon, & X. Li (Eds.), AI 2017: Advances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings (pp. 144-154). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10400 LNAI). Springer-Verlag. https://doi.org/10.1007/978-3-319-63004-5_12

Mougouei, Davoud ; Powers, David M.W. ; Moeini, Asghar. / An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values. AI 2017: Advances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings. editor / Wei Peng ; Damminda Alahakoon ; Xiaodong Li. Switzerland : Springer-Verlag, 2017. pp. 144-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1aa6c7ac58584c2f9117c8d37e20a317,

title = "An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values",

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, Dependency, Fuzzy graph, Integer linear programming, Value",

author = "Davoud Mougouei and Powers, {David M.W.} and Asghar Moeini",

year = "2017",

month = jul,

day = "9",

doi = "10.1007/978-3-319-63004-5_12",

language = "English",

isbn = "9783319630038",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "144--154",

editor = "Wei Peng and Damminda Alahakoon and Xiaodong Li",

booktitle = "AI 2017",

note = "30th Australasian Joint Conference on Artificial Intelligence, AI 2017 ; Conference date: 19-08-2017 Through 20-08-2017",

}

Mougouei, D, Powers, DMW & Moeini, A 2017, An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values. in W Peng, D Alahakoon & X Li (eds), AI 2017: Advances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10400 LNAI, Springer-Verlag, Switzerland, pp. 144-154, 30th Australasian Joint Conference on Artificial Intelligence, AI 2017, Melbourne, Australia, 19/08/17. https://doi.org/10.1007/978-3-319-63004-5_12

An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values. / Mougouei, Davoud; Powers, David M.W.; Moeini, Asghar.
AI 2017: Advances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings. ed. / Wei Peng; Damminda Alahakoon; Xiaodong Li. Switzerland: Springer-Verlag, 2017. p. 144-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10400 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values

AU - Mougouei, Davoud

AU - Powers, David M.W.

AU - Moeini, Asghar

PY - 2017/7/9

Y1 - 2017/7/9

N2 - 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.

AB - 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.

KW - Binary knapsack problem

KW - Dependency

KW - Fuzzy graph

KW - Integer linear programming

KW - Value

UR - http://www.scopus.com/inward/record.url?scp=85026769140&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-63004-5_12

DO - 10.1007/978-3-319-63004-5_12

M3 - Conference contribution

AN - SCOPUS:85026769140

SN - 9783319630038

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 144

EP - 154

BT - AI 2017

A2 - Peng, Wei

A2 - Alahakoon, Damminda

A2 - Li, Xiaodong

PB - Springer-Verlag

CY - Switzerland

T2 - 30th Australasian Joint Conference on Artificial Intelligence, AI 2017

Y2 - 19 August 2017 through 20 August 2017

ER -

Mougouei D, Powers DMW, Moeini A. An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values. In Peng W, Alahakoon D, Li X, editors, AI 2017: Advances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings. Switzerland: Springer-Verlag. 2017. p. 144-154. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-63004-5_12

An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this