Optimization problems with uncertain objective coefficients using capacities

Tuan-Anh Vu (), Sohaib Afifi (), Eric Lefèvre () and Frédéric Pichon ()
Additional contact information
Tuan-Anh Vu: Artois University
Sohaib Afifi: Artois University
Eric Lefèvre: Artois University
Frédéric Pichon: Artois University

Annals of Operations Research, 2025, vol. 344, issue 1, No 13, 383-412

Abstract: 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.

Keywords: 2-Monotone capacities; Coherent lower probabilities; Decision making; Combinatorial optimization; Convex optimization; Multi-objective optimization (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06331-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:344:y:2025:i:1:d:10.1007_s10479-024-06331-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06331-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().