Anytime Algorithms for Adaptive Robust Optimization with OWA and WOWA
We consider optimization problems in graphs where the utilities of solutions depend on different scenarios. In this context, we study incremental approaches for the determination of robust solutions, i.e. solutions yielding good outcomes in all scenarios.
- PDF / 599,500 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 101 Downloads / 185 Views
Abstract. We consider optimization problems in graphs where the utilities of solutions depend on different scenarios. In this context, we study incremental approaches for the determination of robust solutions, i.e. solutions yielding good outcomes in all scenarios. Our approach consists in interleaving adaptive preference elicitation methods aiming to assess the attitude of the Decision Maker towards robustness or risk with combinatorial optimization algorithms aiming to determine a robust solution. Our work focuses on the use of ordered weighted average (OWA) and weighted ordered weighted average (WOWA) to respectively model preferences under uncertainty and risk while accounting for the idea of robustness. These models are parameterized by weighting coefficients or weighting functions that must be fitted to the value system of the Decision Maker. We introduce and justify anytime algorithms for the adaptive elicitation of these parameters until a robust solution can be determined. We also test these algorithms on the robust assignment problem. Keywords: Robust optimization · Preference elicitation WOWA · Ranking algorithms · Assignment problem
1
·
OWA
·
Introduction
The practice of decision support in complex environments has shown the importance of developing new models and algorithms for optimization under partial information. Uncertainty is pervasive in discrete optimization and various contributions concern robust optimization problems [11] in which multiple instances of the same problem must be considered simultaneously. These instances correspond to possible scenarios and the goal is to determine a feasible solution that remains as good as possible in all scenarios. In graph optimization, several problems have been revisited under this perspective. For example, assuming that uncertainty only impacts the valuation of the graph (and not on its structure), several contributions address the discrete scenario case, and propose various reformulations of shortest-path problems, assignment problems, minimum spanning tree problems, as a min-max or minmax regret optimization problems, see [1,5,11,15,28,29]. For the same problems, c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 93–107, 2017. DOI: 10.1007/978-3-319-67504-6 7
94
N. Bourdache and P. Perny
a similar work has been carried out in the case of graphs valued with interval data, which corresponds to an infinity of possible scenarios [1,2,11,14,24,27]. In this paper we consider the discrete scenario case and propose new (interactive) approaches for robust optimization, with an implementation on the assignment problem. Let us introduce an instance of the robust assignment problem, for illustrative purpose: Example 1. We consider a problem with 4 items that must be assigned to 4 agents (one item per agent and one agent per item). The utility of every item for every agent depends on the context which remains unknown. Three scenarios {s1 , s2 , s3 } are considered leading to the following three utility matrices: ⎛
10 ⎜ 10
Data Loading...
