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

Knapsack problems with dependencies through non-additive measures and Choquet integral

Author

Listed:
  • Beliakov, Gleb

Abstract

In portfolio selection problems the items often depend on each other, and their synergies and redundancies need to be taken into account. We consider the knapsack problem in which the objective is modelled as the Choquet integral with respect to a supermodular capacity which quantifies possible synergies. We provide various formulations which lead to the standard linear mixed integer programs, applicable to small and large portfolios. We also study scalability of the solution methods and compare large problems defined with respect to 2-additive capacities which model pairwise interactions, and linear knapsack with respect to the Shapley values of these capacities.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:301:y:2022:i:1:p:277-286
    DOI: 10.1016/j.ejor.2021.11.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721009334
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.11.004?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. Mayag, Brice & Bouyssou, Denis, 2020. "Necessary and possible interaction between criteria in a 2-additive Choquet integral model," European Journal of Operational Research, Elsevier, vol. 283(1), pages 308-320.
    2. Brice Mayag & Michel Grabisch & Christophe Labreuche, 2009. "A characterization of the 2-additive Choquet integral through cardinal information," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-00445132, HAL.
    3. Corrente, Salvatore & Greco, Salvatore & Ishizaka, Alessio, 2016. "Combining analytical hierarchy process and Choquet integral within non-additive robust ordinal regression," Omega, Elsevier, vol. 61(C), pages 2-18.
    4. Fujimoto, Katsushige & Kojadinovic, Ivan & Marichal, Jean-Luc, 2006. "Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction indices," Games and Economic Behavior, Elsevier, vol. 55(1), pages 72-99, April.
    5. Brice Mayag & Michel Grabisch & Christophe Labreuche, 2011. "A representation of preferences by the Choquet integral with respect to a 2-additive capacity," Theory and Decision, Springer, vol. 71(3), pages 297-324, September.
    6. Greco, Salvatore & Mousseau, Vincent & Słowiński, Roman, 2014. "Robust ordinal regression for value functions handling interacting criteria," European Journal of Operational Research, Elsevier, vol. 239(3), pages 711-730.
    7. Grabisch, Michel & Kojadinovic, Ivan & Meyer, Patrick, 2008. "A review of methods for capacity identification in Choquet integral based multi-attribute utility theory: Applications of the Kappalab R package," European Journal of Operational Research, Elsevier, vol. 186(2), pages 766-785, April.
    8. Marichal, Jean-Luc & Mathonet, Pierre, 2011. "Weighted Banzhaf power and interaction indexes through weighted approximations of games," European Journal of Operational Research, Elsevier, vol. 211(2), pages 352-358, June.
    9. Michel Grabisch & Christophe Labreuche, 2010. "A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid," Annals of Operations Research, Springer, vol. 175(1), pages 247-286, March.
    10. Michel Grabisch & Guilherme Dean Pelegrina & Leonardo Tomazeli Duarte & Joao Marcos T. Romano, 2020. "An unsupervised capacity identification approach based on Sobol’ indices," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03220895, HAL.
    11. Galli, Laura & Martello, Silvano & Rey, Carlos & Toth, Paolo, 2021. "Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 291(3), pages 871-882.
    12. Alberto Caprara & David Pisinger & Paolo Toth, 1999. "Exact Solution of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 125-137, May.
    13. Chateauneuf, Alain & Jaffray, Jean-Yves, 1989. "Some characterizations of lower probabilities and other monotone capacities through the use of Mobius inversion," Mathematical Social Sciences, Elsevier, vol. 17(3), pages 263-283, June.
    14. Pelegrina, Guilherme Dean & Duarte, Leonardo Tomazeli & Grabisch, Michel & Romano, João Marcos Travassos, 2020. "The multilinear model in multicriteria decision making: The case of 2-additive capacities and contributions to parameter identification," European Journal of Operational Research, Elsevier, vol. 282(3), pages 945-956.
    15. Mikhail Timonin, 2012. "Maximization of the Choquet integral over a convex set and its application to resource allocation problems," Annals of Operations Research, Springer, vol. 196(1), pages 543-579, July.
    16. Arcidiacono, Sally Giuseppe & Corrente, Salvatore & Greco, Salvatore, 2021. "Robust stochastic sorting with interacting criteria hierarchically structured," European Journal of Operational Research, Elsevier, vol. 292(2), pages 735-754.
    17. Lucie Galand & Patrice Perny & Olivier Spanjaard, 2010. "A Branch and Bound Algorithm for Choquet Optimization in Multicriteria Problems," Lecture Notes in Economics and Mathematical Systems, in: Matthias Ehrgott & Boris Naujoks & Theodor J. Stewart & Jyrki Wallenius (ed.), Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems, pages 355-365, Springer.
    18. 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.
    19. Michel Grabisch & Agnieszka Rusinowska, 2020. "k -additive upper approximation of TU-games," Post-Print halshs-02860802, HAL.
    20. Bottero, M. & Ferretti, V. & Figueira, J.R. & Greco, S. & Roy, B., 2018. "On the Choquet multiple criteria preference aggregation model: Theoretical and practical insights from a real-world application," European Journal of Operational Research, Elsevier, vol. 271(1), pages 120-140.
    21. Guillermo Owen, 1972. "Multilinear Extensions of Games," Management Science, INFORMS, vol. 18(5-Part-2), pages 64-79, January.
    22. Galand, Lucie & Perny, Patrice & Spanjaard, Olivier, 2010. "Choquet-based optimisation in multiobjective shortest path and spanning tree problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 303-315, July.
    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. Torra, Vicenç, 2023. "The transport problem for non-additive measures," European Journal of Operational Research, Elsevier, vol. 311(2), pages 679-689.

    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. Mayag, Brice & Bouyssou, Denis, 2020. "Necessary and possible interaction between criteria in a 2-additive Choquet integral model," European Journal of Operational Research, Elsevier, vol. 283(1), pages 308-320.
    2. Sébastien Courtin & Rodrigue Tido Takeng & Frédéric Chantreuil, 2020. "Decomposition of interaction indices: alternative interpretations of cardinal-probabilistic interaction indices ," Working Papers hal-02952516, HAL.
    3. Silvia Bortot & Ricardo Alberto Marques Pereira, 2011. "Inconsistency and non-additive Choquet integration in the Analytic Hierarchy Process," DISA Working Papers 2011/06, Department of Computer and Management Sciences, University of Trento, Italy, revised 29 Jul 2011.
    4. Mikhail Timonin, 2012. "Maximization of the Choquet integral over a convex set and its application to resource allocation problems," Annals of Operations Research, Springer, vol. 196(1), pages 543-579, July.
    5. Corrente, Salvatore & Greco, Salvatore & Ishizaka, Alessio, 2016. "Combining analytical hierarchy process and Choquet integral within non-additive robust ordinal regression," Omega, Elsevier, vol. 61(C), pages 2-18.
    6. Siskos, Eleftherios & Burgherr, Peter, 2022. "Multicriteria decision support for the evaluation of electricity supply resilience: Exploration of interacting criteria," European Journal of Operational Research, Elsevier, vol. 298(2), pages 611-626.
    7. Paul Alain Kaldjob Kaldjob & Brice Mayag & Denis Bouyssou, 2023. "On the interpretation of the interaction index between criteria in a Choquet integral model," Post-Print hal-03766372, HAL.
    8. Alessio Bonetti & Silvia Bortot & Mario Fedrizzi & Silvio Giove & Ricardo Alberto Marques Pereira & Andrea Molinari, 2011. "Modelling group processes and effort estimation in Project Management using the Choquet integral: an MCDM approach," DISA Working Papers 2011/12, Department of Computer and Management Sciences, University of Trento, Italy, revised Sep 2011.
    9. Jian-Zhang Wu & Yi-Ping Zhou & Li Huang & Jun-Jie Dong, 2019. "Multicriteria Correlation Preference Information (MCCPI)-Based Ordinary Capacity Identification Method," Mathematics, MDPI, vol. 7(3), pages 1-13, March.
    10. Silvia Bortot & Ricardo Alberto Marques Pereira & Thuy H. Nguyen, 2015. "Welfare functions and inequality indices in the binomial decomposition of OWA functions," DEM Discussion Papers 2015/08, Department of Economics and Management.
    11. Silvia Angilella & Marta Bottero & Salvatore Corrente & Valentina Ferretti & Salvatore Greco & Isabella M. Lami, 2016. "Non Additive Robust Ordinal Regression for urban and territorial planning: an application for siting an urban waste landfill," Annals of Operations Research, Springer, vol. 245(1), pages 427-456, October.
    12. Grabisch, Michel & Labreuche, Christophe, 2018. "Monotone decomposition of 2-additive Generalized Additive Independence models," Mathematical Social Sciences, Elsevier, vol. 92(C), pages 64-73.
    13. Khaled Belahcène & Vincent Mousseau & Wassila Ouerdane & Marc Pirlot & Olivier Sobrie, 2023. "Multiple criteria sorting models and methods—Part I: survey of the literature," 4OR, Springer, vol. 21(1), pages 1-46, March.
    14. Pelegrina, Guilherme Dean & Duarte, Leonardo Tomazeli & Grabisch, Michel & Romano, João Marcos Travassos, 2020. "The multilinear model in multicriteria decision making: The case of 2-additive capacities and contributions to parameter identification," European Journal of Operational Research, Elsevier, vol. 282(3), pages 945-956.
    15. Mikhail Timonin, 2016. "Choquet integral in decision analysis - lessons from the axiomatization," Papers 1611.09926, arXiv.org.
    16. Kadaifci, Cigdem & Asan, Umut & Bozdag, Erhan, 2020. "A new 2-additive Choquet integral based approach to qualitative cross-impact analysis considering interaction effects," Technological Forecasting and Social Change, Elsevier, vol. 158(C).
    17. Michel Grabisch & Christophe Labreuche, 2010. "A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid," Annals of Operations Research, Springer, vol. 175(1), pages 247-286, March.
    18. Volker Kuppelwieser & Fouad Ben Abdelaziz & Olfa Meddeb, 2020. "Unstable interactions in customers’ decision making: an experimental proof," Annals of Operations Research, Springer, vol. 294(1), pages 479-499, November.
    19. F. Beaudouin, 2015. "Implementing a Multiple Criteria Model to Debate About Nuclear Power Plants Safety Choices," Group Decision and Negotiation, Springer, vol. 24(6), pages 1035-1063, November.
    20. Li, Jianping & Yao, Xiaoyang & Sun, Xiaolei & Wu, Dengsheng, 2018. "Determining the fuzzy measures in multiple criteria decision aiding from the tolerance perspective," European Journal of Operational Research, Elsevier, vol. 264(2), pages 428-439.

    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:301:y:2022:i:1:p:277-286. 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.