Multipolar robust optimization (Q1731824)

Considered is the following linear problem \[ \min \ \mathbf{c}^{T}\mathbf{x} \quad \text{ s.t. }\mathbf{Ax}\leq \mathbf{b} \] involving uncertain parameters. To deal with uncertainty, there are mainly two approaches: stochastic optimization and robust optimization. Robust optimization is a more recent approach dealing with uncertainty. It does not require specifications of the exact distribution of the problem's parameters as in stochastic programming. Uncertain data are assumed to belong to a known compact set, called uncertainty set, and the problem is to find a solution that is immunized against all possible realizations in the uncertainty set. In this paper, the authors propose a new tractable robust counterpart which contains and generalizes several other models including the existing affinely ajustable robust counterpart and the fully adjustable robust counterpart. It consists in selecting a set of poles whose convex hull contains some projection of the uncertainty set, and computing a recourse strategy for each data scenario as a convex combination of some optimized recourses (one for each pole). The authors show that the proposed multipolar robust counterpart is tractable and its complexity is controllable. Further, they show that, under some mild assumptions, two sequences of upper and lower bounds converge to the optimal value of the fully adjustable robust counterpart. Finally, the authors assess the computational performance of the multipolar robust approach proposed on two problems: the lobbing problem and the temporal network example.