An integer linear programming model for binary knapsack problem with dependent item values

Paper


Mougouei, Davoud, Powers, David M.W. and Moeini, Ashgar. 2017. "An integer linear programming model for binary knapsack problem with dependent item values." Peng, Wei, Alahakoon, Damminda and Li, Xiaodong (ed.) 30th Australasian Joint Conference on Artificial Intelligence (AI 2017). Melbourne, Australia 19 - 20 Aug 2017 Switzerland. https://doi.org/10.1007/978-3-319-63004-5_12
Paper/Presentation Title

An integer linear programming model for binary knapsack problem with dependent item values

Presentation TypePaper
AuthorsMougouei, Davoud (Author), Powers, David M.W. (Author) and Moeini, Ashgar (Author)
EditorsPeng, Wei, Alahakoon, Damminda and Li, Xiaodong
Journal or Proceedings TitleAI 2017: Advances in Artificial Intelligence
Number of Pages11
Year2017
Place of PublicationSwitzerland
ISBN9783319630038
9783319630045
Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-319-63004-5_12
Web Address (URL) of Paperhttps://link.springer.com/chapter/10.1007/978-3-319-63004-5_12
Web Address (URL) of Conference Proceedingshttps://link.springer.com/book/10.1007/978-3-319-63004-5
Conference/Event30th 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.

Keywordsbinary knapsack problem; integer linear programming; dependency; value; fuzzy graph
Contains Sensitive ContentDoes not contain sensitive content
ANZSRC Field of Research 2020461299. Software engineering not elsewhere classified
Public Notes

Files associated with this item cannot be displayed due to copyright restrictions.

Byline AffiliationsFlinders University
Institution of OriginUniversity of Southern Queensland
Permalink -

https://research.usq.edu.au/item/q6yzv/an-integer-linear-programming-model-for-binary-knapsack-problem-with-dependent-item-values

  • 122
    total views
  • 9
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Dependency-aware software requirements selection using fuzzy graphs and integer programming
Mougouei, Davoud and Powers, David M.W.. 2021. "Dependency-aware software requirements selection using fuzzy graphs and integer programming." Expert Systems with Applications. 167, pp. 1-23. https://doi.org/10.1016/j.eswa.2020.113748
Dependency-aware release planning for software projects using fuzzy graphs and integer programming
Mougouei, Davoud and Powers, David M. W.. 2019. "Dependency-aware release planning for software projects using fuzzy graphs and integer programming." Journal of Intelligent and Fuzzy Systems. 37 (3), pp. 3693-3707. https://doi.org/10.3233/JIFS-182810
A fuzzy framework for prioritization and partial selection of security requirements in software projects
Mougouei, Davoud, Powers, David M.W. and Mougouei, Elahe. 2019. "A fuzzy framework for prioritization and partial selection of security requirements in software projects." Journal of Intelligent and Fuzzy Systems. 37 (2), pp. 2671-2686. https://doi.org/10.3233/JIFS-182907
Dependency-aware software release planning through mining user preferences
Mougouei, Davoud and Powers, David M. W.. 2020. "Dependency-aware software release planning through mining user preferences." Soft Computing. 24 (15), pp. 11673-11693. https://doi.org/10.1007/s00500-019-04630-y
A model-driven approach to reengineering processes in cloud computing
Fahmideh, Mahdi, Grundy, John, Beydoun, Ghassan, Zowghi, Didar, Susilo, Willy and Mougouei, Davoud. 2022. "A model-driven approach to reengineering processes in cloud computing." Information and Software Technology. 144. https://doi.org/10.1016/j.infsof.2021.106795
Investigating the Emotional Response to COVID-19 News on Twitter: A Topic Modeling and Emotion Classification Approach
Oliveira, Francisco Braulio, Haque, Amanul, Mougouei, Davoud, Evans, Simon, Sichman, Jaime Simao and Singh, Munindar P.. 2022. "Investigating the Emotional Response to COVID-19 News on Twitter: A Topic Modeling and Emotion Classification Approach." IEEE Access. 10, pp. 16883-16897. https://doi.org/10.1109/ACCESS.2022.3150329
Understanding the emotional response to COVID-19 information in news and social media: A mental health perspective
Jones, Rosalind, Mougouei, Davoud and Evans, Simon L.. 2021. "Understanding the emotional response to COVID-19 information in news and social media: A mental health perspective." Human Behavior and Emerging Technologies. 3 (5), pp. 832-842. https://doi.org/10.1002/hbe2.304
Operationalizing human values in software: A research roadmap
Mougouei, Davoud, Perera, Harsha, Hussain, Waqar, Shams, Rifat and Whittle, Jon. 2018. "Operationalizing human values in software: A research roadmap." Leavens, Gary T., Garcia, Alessandro and Pasareanu, Corina S. (ed.) 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018). Lake Buena Vista, United States 04 - 09 Nov 2018 United States. https://doi.org/10.1145/3236024.3264843
Integrating Social Values into Software Design Patterns
Hussain, Waqar, Mougouei, Davoud and Whittle, Jon. 2018. "Integrating Social Values into Software Design Patterns." 2018 ACM/IEEE International Workshop on Software Fairness: Fairware (ACM 2018). Gothenburg, Sweden 29 May 2018 United States. https://doi.org/10.1145/3194770.3194777
Modeling and Selection of Interdependent Software Requirements Using Fuzzy Graphs
Mougouei, Davoud and Powers, David M. W.. 2017. "Modeling and Selection of Interdependent Software Requirements Using Fuzzy Graphs." International Journal of Fuzzy Systems. 19 (6), pp. 1812-1828. https://doi.org/10.1007/s40815-017-0364-4
Towards Integrating Human Values into Software: Mapping Principles and Rights of GDPR to Values
Perera, Harsha, Hussain, Waqar, Mougouei, Davoud, Shams, Rifat Ara, Nurwidyantoro, Arif and Whittle, Jon. 2019. "Towards Integrating Human Values into Software: Mapping Principles and Rights of GDPR to Values." Damian, Daniela, Perini, Anna and Lee, Seok-Won (ed.) IEEE 27th International Requirements Engineering Conference (RE 2019). Jeju Island, Korea United States. https://doi.org/10.1109/RE.2019.00053
Engineering human values in software through value programming
Mougouei, Davoud. 2020. "Engineering human values in software through value programming." 42nd IEEE/ACM International Conference on Software Engineering Workshops (ICSEW 2020). Seoul, South Korea 27 Jun - 19 Jul 2020 United States. https://doi.org/10.1145/3387940.3392242
A study on the prevalence of human values in software engineering publications, 2015 - 2018
Perera, Harsha, Hussain, Waqar, Whittle, Jon, Nurwidyantoro, Arif, Mougouei, David, Shams, Rifat Ara and Oliver, Gillian. 2020. "A study on the prevalence of human values in software engineering publications, 2015 - 2018." 42nd IEEE/ACM International Conference on Software Engineering Workshops (ICSEW 2020). Seoul, South Korea 27 Jun - 19 Jul 2020 United States. https://doi.org/10.1145/3377811.3380393
A fuzzy-based requirement selection method for considering value dependencies in software release planning
Mougouei, Davoud, Ghose, Aditya, Dam, Hoa, Fahmideh, Mahdi and Powers, David. 2021. "A fuzzy-based requirement selection method for considering value dependencies in software release planning." 30th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2021). Luxembourg 11 - 14 Jul 2021 United States. https://doi.org/10.1109/FUZZ45933.2021.9494422
Partial Selection of Software Requirements: A Fuzzy Method
Mougouei, Davoud, Mougouei, Elahe and Powers, David M. W.. 2021. "Partial Selection of Software Requirements: A Fuzzy Method." International Journal of Fuzzy Systems. 23 (7), pp. 2067-2079. https://doi.org/10.1007/s40815-021-01093-y
Dependency-Aware Software Release Planning
Mougouei, Davoud, Powers, David M. W. and Moeini, Asghar. 2017. "Dependency-Aware Software Release Planning." 39th IEEE/ACM International Conference on Software Engineering Companion (ICSE-C 2017). Buenos Aires, Argentina 20 - 28 May 2017 United States. IEEE (Institute of Electrical and Electronics Engineers). pp. 198-200 https://doi.org/10.1109/ICSE-C.2017.74
Factoring Requirement Dependencies in Software Requirement Selection using Graphs and Integer Programming
Mougouei, Davoud. 2016. "Factoring Requirement Dependencies in Software Requirement Selection using Graphs and Integer Programming." 31st IEEE/ACM International Conference on Automated Software Engineering (ASE 2016). Singapore 03 - 07 Sep 2016 United States. IEEE (Institute of Electrical and Electronics Engineers). pp. 884-887 https://doi.org/10.1145/2970276.2975936
Partial selection of agile software requirements
Mougouei, Davoud, Shen, Haifeng and Babar, Muhammad Ali. 2015. "Partial selection of agile software requirements." International Journal of Software Engineering and Its Applications. 9 (1), pp. 113-126. https://doi.org/10.14257/ijseia.2015.9.1.10
Visibility Requirements Engineering for Commercial Websites
Mougouei, Davoud and Yeung, Man Kwan. 2014. "Visibility Requirements Engineering for Commercial Websites." International Journal of Software Engineering and Its Applications. 8 (8), pp. 11-18. https://doi.org/10.14257/ijseia.2014.8.8,02
A Fuzzy-Based Technique for Describing Security Requirements of Intrusion Tolerant Systems
Mougouei, Davoud and Ab. Rahman, Wan Nurhayati Wan. 2013. "A Fuzzy-Based Technique for Describing Security Requirements of Intrusion Tolerant Systems." International Journal of Software Engineering and Its Applications. 7 (2), pp. 99-112.
Goal-Based Requirement Engineering for Fault Tolerant Security-Critical Systems
Mougouei, Davoud. 2013. "Goal-Based Requirement Engineering for Fault Tolerant Security-Critical Systems." International Journal of Software Engineering and Its Applications. 7 (5), pp. 1-14. https://doi.org/10.14257/ijseia.2013.7.5.01
Evaluating Fault Tolerance in Security Requirements of Web Services
Mougouei, Davoud, Ab. Rahman, Wan Nurhayati Wan and Almasi, Mohammad Moein. 2012. "Evaluating Fault Tolerance in Security Requirements of Web Services." 2012 International Conference on Cyber Security, Cyber Warfare and Digital Forensic (CyberSec 2012). Kuala Lumpur, Malaysia 26 - 28 Jun 2012 United States. IEEE (Institute of Electrical and Electronics Engineers). pp. 111-116 https://doi.org/10.1109/CyberSec.2012.6246125
A Goal-Based Modeling Approach to Develop Security Requirements of Fault Tolerant Security-Critical Systems
Mougouei, Davoud, Moghtadaei, Mohammad and Moradmand, Somayeh. 2012. "A Goal-Based Modeling Approach to Develop Security Requirements of Fault Tolerant Security-Critical Systems." 2012 International Conference on Computer and Communication Engineering (ICCCE 2012). Kuala Lumpur, Malaysia 03 - 05 Jul 2012 United States. IEEE (Institute of Electrical and Electronics Engineers). pp. 200-205 https://doi.org/10.1109/ICCCE.2012.6271180
Methods for the blind signal separation problem
Li, Yan, Wen, Peng and Powers, David. 2003. "Methods for the blind signal separation problem." ICNNSP 2003: International Conference on Neural Networks and Signal Processing. Nanjing, China 14 - 17 Dec 2003 Piscataway, NJ. United States. https://doi.org/10.1109/ICNNSP.2003.1281131
Comparison of blind source separation algorithms
Li, Yan, Powers, David and Peach, James. 2001. "Comparison of blind source separation algorithms." Mastorakis, Nikos E. (ed.) WSES International Conference on Neural Networks and Applications 2001. Tenerife, Spain 11 - 15 Feb 2001 Greece.