.png){kind=icon}
.png){kind=icon}
Return
Optimization problems with uncertain objective coefficients using capacities
.png){kind=icon}
OA
AI
DOI：10.1007/s10479-024-06331-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W