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 proceedingConference contribution

    7 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 languageEnglish
    Title of host publicationAI 2017
    Subtitle of host publicationAdvances in Artificial Intelligence - 30th Australasian Joint Conference, Proceedings
    EditorsWei Peng, Damminda Alahakoon, Xiaodong Li
    PublisherSpringer-Verlag
    Pages144-154
    Number of pages11
    ISBN (Print)9783319630038
    DOIs
    Publication statusPublished - 9 Jul 2017
    Event30th Australasian Joint Conference on Artificial Intelligence, AI 2017 - Melbourne, Australia
    Duration: 19 Aug 201720 Aug 2017

    Publication series

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

    Conference

    Conference30th Australasian Joint Conference on Artificial Intelligence, AI 2017
    CountryAustralia
    CityMelbourne
    Period19/08/1720/08/17

    Keywords

    • Binary knapsack problem
    • Dependency
    • Fuzzy graph
    • Integer linear programming
    • Value

    Fingerprint Dive into the research topics of 'An integer linear programming model for binary knapsack problem with dependent item values'. Together they form a unique fingerprint.

  • 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