IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v289y2021i2p508-514.html
   My bibliography  Save this article

The binary knapsack problem with qualitative levels

Author

Listed:
  • Schäfer, Luca E.
  • Dietz, Tobias
  • Barbati, Maria
  • Figueira, José Rui
  • Greco, Salvatore
  • Ruzika, Stefan

Abstract

A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We define a dominance relation over the feasible subsets of the given item set and show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors and we state two greedy algorithms, which efficiently compute a single efficient solution.

Suggested Citation

  • Schäfer, Luca E. & Dietz, Tobias & Barbati, Maria & Figueira, José Rui & Greco, Salvatore & Ruzika, Stefan, 2021. "The binary knapsack problem with qualitative levels," European Journal of Operational Research, Elsevier, vol. 289(2), pages 508-514.
    • Handle: RePEc:eee:ejores:v:289:y:2021:i:2:p:508-514
    DOI: 10.1016/j.ejor.2020.07.040
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720306664
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.07.040?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Schäfer, Luca E. & Dietz, Tobias & Fröhlich, Nicolas & Ruzika, Stefan & Figueira, José R., 2020. "Shortest paths with ordinal weights," European Journal of Operational Research, Elsevier, vol. 280(3), pages 1160-1170.
    2. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    3. Liesiö, Juuso & Mild, Pekka & Salo, Ahti, 2008. "Robust portfolio modeling with incomplete cost information and project interdependencies," European Journal of Operational Research, Elsevier, vol. 190(3), pages 679-695, November.
    4. Lin, Feng-Tse, 2008. "Solving the knapsack problem with imprecise weight coefficients using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 185(1), pages 133-145, February.
    5. Liesio, Juuso & Mild, Pekka & Salo, Ahti, 2007. "Preference programming for robust portfolio modeling and project selection," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1488-1505, September.
    6. Julie Stal-Le Cardinal & Vincent Mousseau & Jun Zheng, 2011. "An Application of Constrained Multicriteria Sorting to Student Selection," International Series in Operations Research & Management Science, in: Ahti Salo & Jeffrey Keisler & Alec Morton (ed.), Portfolio Decision Analysis, chapter 0, pages 213-240, Springer.
    7. Lin, Feng-Tse & Yao, Jing-Shing, 2001. "Using fuzzy numbers in knapsack problems," European Journal of Operational Research, Elsevier, vol. 135(1), pages 158-176, November.
    8. Lahdelma, Risto & Miettinen, Kaisa & Salminen, Pekka, 2003. "Ordinal criteria in stochastic multicriteria acceptability analysis (SMAA)," European Journal of Operational Research, Elsevier, vol. 147(1), pages 117-127, May.
    9. Wang, Jue & Xu, Wei & Ma, Jian & Wang, Shouyang, 2013. "A vague set based decision support approach for evaluating research funding programs," European Journal of Operational Research, Elsevier, vol. 230(3), pages 656-665.
    10. Kasperski, Adam & Zielinski, Pawel, 2010. "Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights," European Journal of Operational Research, Elsevier, vol. 200(3), pages 680-687, February.
    11. Barbati, Maria & Greco, Salvatore & Kadziński, Miłosz & Słowiński, Roman, 2018. "Optimization of multiple satisfaction levels in portfolio decision analysis," Omega, Elsevier, vol. 78(C), pages 192-204.
    12. Ralph L. Keeney & Timothy L. McDaniels, 1999. "Identifying and Structuring Values to Guide Integrated Resource Planning at BC Gas," Operations Research, INFORMS, vol. 47(5), pages 651-662, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Beliakov, Gleb, 2022. "Knapsack problems with dependencies through non-additive measures and Choquet integral," European Journal of Operational Research, Elsevier, vol. 301(1), pages 277-286.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mavrotas, George & Makryvelios, Evangelos, 2021. "Combining multiple criteria analysis, mathematical programming and Monte Carlo simulation to tackle uncertainty in Research and Development project portfolio selection: A case study from Greece," European Journal of Operational Research, Elsevier, vol. 291(2), pages 794-806.
    2. Salo, Ahti & Doumpos, Michalis & Liesiö, Juuso & Zopounidis, Constantin, 2024. "Fifty years of portfolio optimization," European Journal of Operational Research, Elsevier, vol. 318(1), pages 1-18.
    3. Zhang, Xinwei & Yan, Yong & Wang, Lilin & Wang, Yang, 2024. "A ranking approach for robust portfolio decision analysis based on multilinear portfolio utility functions and incomplete preference information," Omega, Elsevier, vol. 122(C).
    4. Tom Pape, 2020. "Value of agreement in decision analysis: Concept, measures and application," Papers 2012.13816, arXiv.org.
    5. Pape, Tom, 2017. "Value of agreement in decision analysis: concept, measures and application," LSE Research Online Documents on Economics 68682, London School of Economics and Political Science, LSE Library.
    6. Barbati, Maria & Corrente, Salvatore & Greco, Salvatore, 2020. "A general space-time model for combinatorial optimization problems (and not only)," Omega, Elsevier, vol. 96(C).
    7. Brunelli, Matteo & Corrente, Salvatore, 2024. "Modeling criteria and project interactions in portfolio decision analysis with the Choquet integral," Omega, Elsevier, vol. 126(C).
    8. Marques, Adriana Cavalcante & Frej, Eduarda Asfora & de Almeida, Adiel Teixeira, 2022. "Multicriteria decision support for project portfolio selection with the FITradeoff method," Omega, Elsevier, vol. 111(C).
    9. Selin Özpeynirci & Özgür Özpeynirci & Vincent Mousseau, 2021. "An interactive algorithm for resource allocation with balance concerns," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 983-1005, December.
    10. Vilkkumaa, Eeva & Liesiö, Juuso & Salo, Ahti, 2014. "Optimal strategies for selecting project portfolios using uncertain value estimates," European Journal of Operational Research, Elsevier, vol. 233(3), pages 772-783.
    11. Panos Xidonas & Haris Doukas & George Mavrotas & Olena Pechak, 2016. "Environmental corporate responsibility for investments evaluation: an alternative multi-objective programming model," Annals of Operations Research, Springer, vol. 247(2), pages 395-413, December.
    12. Baker, Erin & Bosetti, Valentina & Salo, Ahti, 2016. "Finding Common Ground when Experts Disagree: Belief Dominance over Portfolios of Alternatives," MITP: Mitigation, Innovation and Transformation Pathways 243147, Fondazione Eni Enrico Mattei (FEEM).
    13. Marttunen, Mika & Haara, Arto & Hjerppe, Turo & Kurttila, Mikko & Liesiö, Juuso & Mustajoki, Jyri & Saarikoski, Heli & Tolvanen, Anne, 2023. "Parallel and comparative use of three multicriteria decision support methods in an environmental portfolio problem," European Journal of Operational Research, Elsevier, vol. 307(2), pages 842-859.
    14. Liesiö, Juuso & Andelmin, Juho & Salo, Ahti, 2020. "Efficient allocation of resources to a portfolio of decision making units," European Journal of Operational Research, Elsevier, vol. 286(2), pages 619-636.
    15. Toppila, Antti & Salo, Ahti, 2017. "Binary decision diagrams for generating and storing non-dominated project portfolios with interval-valued project scores," European Journal of Operational Research, Elsevier, vol. 260(1), pages 244-254.
    16. Harju, Mikko & Liesiö, Juuso & Virtanen, Kai, 2019. "Spatial multi-attribute decision analysis: Axiomatic foundations and incomplete preference information," European Journal of Operational Research, Elsevier, vol. 275(1), pages 167-181.
    17. Javier Panadero & Jana Doering & Renatas Kizys & Angel A. Juan & Angels Fito, 2020. "A variable neighborhood search simheuristic for project portfolio selection under uncertainty," Journal of Heuristics, Springer, vol. 26(3), pages 353-375, June.
    18. Feng Yang & Shiling Song & Wei Huang & Qiong Xia, 2015. "SMAA-PO: project portfolio optimization problems based on stochastic multicriteria acceptability analysis," Annals of Operations Research, Springer, vol. 233(1), pages 535-547, October.
    19. Antti Punkka & Ahti Salo, 2014. "Scale Dependence and Ranking Intervals in Additive Value Models Under Incomplete Preference Information," Decision Analysis, INFORMS, vol. 11(2), pages 83-104, June.
    20. Pekka Mild & Ahti Salo, 2009. "Combining a Multiattribute Value Function with an Optimization Model: An Application to Dynamic Resource Allocation for Infrastructure Maintenance," Decision Analysis, INFORMS, vol. 6(3), pages 139-152, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:289:y:2021:i:2:p:508-514. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.