In this work we propose a novel polyhedral uncertainty set for robust optimization: the smooth uncertainty set. This set imposes bounds on the difference of pairs of uncertain parameters. Smooth uncertainty sets arise naturally in applications where there is a strong connection between the generation of these parameters due to vicinity in space/time, or due to physical constraints. Thus,  for such applications, smooth uncertainty sets can be constructed based on expert estimation or existing data. 

Under probabilistic assumptions on the uncertain parameters' correlations, we derive a construction of the uncertainty set that provides probabilistic guarantees for the resulting solution of the robust problem. We show that the size of this set decreases as the correlation between the parameters increases.

In terms of tractability, for specially structured problems, we prove the robust counterpart can be reformulated in a compact way, with no additional variables and few additional constraints. For a more general problem structure, we construct a column generation algorithm tailored for the smooth uncertainty set for solving the robust problem.

Joint work with Michael Poss (CNRS, LIRMM) and Noam Goldberg (Bar-Ilan University)

Shimrit Shtern is a senior lecturer in the Faculty of Data and Decision Sciences at the Technion - Israel Institute of Technology. She received a Ph.D. in Optimization and an MSc in Operations Research, both from the Technion, and was a post-doctoral fellow at the Operation Research Center at MIT. Her research focuses on theory and applications of optimization under uncertainty as well as development and convergence analysis of first order methods for structured optimization problems. She is a recipient of research grants from both the Israeli Science Foundation (ISF) and The Deutsche Forschungsgemeinschaft (DFG, German Research Foundation).