A heuristic framework for a class of robust optimization problems is proposed. The heuristic framework explores dual information. The heuristic is successfully applied to solve two robust optimization problems. The heuristic is able to outperform a widely used 2-approximation procedure. A robust optimization version of the restricted shortest path problem is introduced.