A Frank-Wolfe Based Algorithm for Robust Discrete Optimization under Uncertainty

This paper addresses a class of robust optimization problems whose inputs are correlated and belong to an ellipsoidal uncertainty set, which is known to be NP-Hard. For that, we propose an efficient heuristic scalable approach based on the iterative Frank-Wolfe (FW) algorithm. In our approach, we take a radically different perspective on FW by looking at the exploration power of the integer inner iterates of the method. Our main discovery is that, for small dimensional instances, our method is able to provide the same optimal integer solution as an exact method provided by CPLEX, after no more than a few hundred iterations. Moreover, as opposed to the exact method, our FW-guided integer exploration approach applies to large scale problems as well. Our findings are illustrated by comprehensive numerical experiments. We focus on two target applications, the robust shortest path problem as a first test case, and the robust clustering as a real application in a PHM context and data analysis.