IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v344y2025i1d10.1007_s10479-024-06331-8.html
   My bibliography  Save this article

Optimization problems with uncertain objective coefficients using capacities

Author

Listed:
  • Tuan-Anh Vu

    (Artois University)

  • Sohaib Afifi

    (Artois University)

  • Eric Lefèvre

    (Artois University)

  • Frédéric Pichon

    (Artois University)

Abstract

We study a general optimization problem in which coefficients in the objective are uncertain. We use capacities (lower probabilities) to model such uncertainty. Two popular criteria in imprecise probability, namely maximality and E-admissibility, are employed to compare solutions. We characterize non-dominated solutions with respect to these criteria in terms of well-known notions in multi-objective optimization. These characterizations are novel and make it possible to derive several interesting results. Specially, for convex problems, maximality and E-admissibility are equivalent for any capacities even though the set of associated acts is not convex, and in case of 2-monotone capacities, finding an arbitrary non-dominated solution and checking if a given solution is non-dominated are both tractable. For combinatorial problems, we show a general result: in case of 2-monotone capacities, if the deterministic version of the problem can be solved in polynomial time, checking E-admissibility can also be done in polynomial time. Lastly, for the matroid optimization problem, more refined results are also obtained thanks to these characterizations, namely the connectedness of E-admissible solutions and an outer approximation based on the greedy algorithm for non-dominated solutions with respect to maximality.

Suggested Citation

  • Tuan-Anh Vu & Sohaib Afifi & Eric Lefèvre & Frédéric Pichon, 2025. "Optimization problems with uncertain objective coefficients using capacities," Annals of Operations Research, Springer, vol. 344(1), pages 383-412, January.
    • Handle: RePEc:spr:annopr:v:344:y:2025:i:1:d:10.1007_s10479-024-06331-8
    DOI: 10.1007/s10479-024-06331-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-024-06331-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-024-06331-8?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. Itzhak Gilboa & David Schmeidler, 1992. "Additive Representation of Non-Additive Measures and the Choquet Integral," Discussion Papers 985, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    2. Adam Kasperski & Paweł Zieliński, 2016. "Robust Discrete Optimization Under Discrete and Interval Uncertainty: A Survey," International Series in Operations Research & Management Science, in: Michael Doumpos & Constantin Zopounidis & Evangelos Grigoroudis (ed.), Robustness Analysis in Decision Aiding, Optimization, and Analytics, chapter 0, pages 113-143, Springer.
    3. 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.
    4. Michel Grabisch, 2016. "Set Functions, Games and Capacities in Decision Making," Theory and Decision Library C, Springer, number 978-3-319-30690-2, December.
    5. 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.
    6. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    7. repec:spr:thdchp:978-3-319-30690-2_2 is not listed on IDEAS
    8. Inuiguchi, Masahiro & Sakawa, Masatoshi, 1995. "Minimax regret solution to linear programming problems with an interval objective function," European Journal of Operational Research, Elsevier, vol. 86(3), pages 526-536, November.
    Full references (including those not matched with items on IDEAS)

    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. Andrea Cinfrignini & Davide Petturiti & Barbara Vantaggi, 2023. "Envelopes of equivalent martingale measures and a generalized no-arbitrage principle in a finite setting," Annals of Operations Research, Springer, vol. 321(1), pages 103-137, February.
    2. Giulianella Coletti & Davide Petturiti & Barbara Vantaggi, 2019. "Dutch book rationality conditions for conditional preferences under ambiguity," Annals of Operations Research, Springer, vol. 279(1), pages 115-150, August.
    3. Eichberger, Jürgen & Pasichnichenko, Illia, 2021. "Decision-making with partial information," Journal of Economic Theory, Elsevier, vol. 198(C).
    4. Takao Asano & Hiroyuki Kojima, 2022. "Choquet Integrals and Belief Functions," KIER Working Papers 1077, Kyoto University, Institute of Economic Research.
    5. Cinfrignini, Andrea & Petturiti, Davide & Vantaggi, Barbara, 2023. "Dynamic bid–ask pricing under Dempster-Shafer uncertainty," Journal of Mathematical Economics, Elsevier, vol. 107(C).
    6. Angilella, Silvia & Greco, Salvatore & Matarazzo, Benedetto, 2010. "Non-additive robust ordinal regression: A multiple criteria decision model based on the Choquet integral," European Journal of Operational Research, Elsevier, vol. 201(1), pages 277-288, February.
    7. Ronald Stauber, 2019. "A strategic product for belief functions," ANU Working Papers in Economics and Econometrics 2019-668, Australian National University, College of Business and Economics, School of Economics.
    8. 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.
    9. Enrique Miranda & Ignacio Montes, 2023. "Centroids of the core of exact capacities: a comparative study," Annals of Operations Research, Springer, vol. 321(1), pages 409-449, February.
    10. Daniel Li Li & Erfang Shan, 2020. "Marginal contributions and derivatives for set functions in cooperative games," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 849-858, April.
    11. Ghirardato, Paolo, 1997. "On Independence for Non-Additive Measures, with a Fubini Theorem," Journal of Economic Theory, Elsevier, vol. 73(2), pages 261-291, April.
    12. Mikhail Timonin, 2016. "Choquet integral in decision analysis - lessons from the axiomatization," Papers 1611.09926, arXiv.org.
    13. Angilella, Silvia & Greco, Salvatore & Lamantia, Fabio & Matarazzo, Benedetto, 2004. "Assessing non-additive utility for multicriteria decision aid," European Journal of Operational Research, Elsevier, vol. 158(3), pages 734-744, November.
    14. Gianluca Cassese, 2020. "Semilattices, canonical embeddings and representing measures," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 43(1), pages 55-74, June.
    15. Vassili Vergopoulos, 2011. "Dynamic consistency for non-expected utility preferences," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 48(2), pages 493-518, October.
    16. Yaron Azrieli & John Rehbeck, 2022. "Marginal stochastic choice," Papers 2208.08492, arXiv.org.
    17. 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.
    18. Stauber, Ronald, 2019. "A strategic product for belief functions," Games and Economic Behavior, Elsevier, vol. 116(C), pages 38-64.
    19. Dominiak, Adam & Eichberger, Jürgen, 2021. "Games in context: Equilibrium under ambiguity for belief functions," Games and Economic Behavior, Elsevier, vol. 128(C), pages 125-159.
    20. Silvia Angilella & Sally Giuseppe Arcidiacono & Salvatore Corrente & Salvatore Greco & Benedetto Matarazzo, 2020. "An application of the SMAA–Choquet method to evaluate the performance of sailboats in offshore regattas," Operational Research, Springer, vol. 20(2), pages 771-793, June.

    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:spr:annopr:v:344:y:2025:i:1:d:10.1007_s10479-024-06331-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.