Minimizing recovery cost of network optimization problems

Abstract We propose a two‐stage recoverable robustness approach that minimizes the recovery cost. In many applications, once the uncertainty is revealed, it can be more important to recover a solution which is as similar as possible to the nominal solution than to minimize the nominal objective value of . This for example occurs when the nominal solution is implemented on a regular basis or when the uncertainty is revealed late. We define the proactive problem which minimizes the weighted recovery costs over a discrete set of scenarios while ensuring optimality of the nominal objective value of . We model the recovery cost of a scenario by a distance between the first‐stage nominal solution and the second‐stage solution recovered for this scenario. We show for two different solution distances and that the proactive problem is ‐hard for both the integer min‐cost flow problem with uncertain arc demands and for the integer max‐flow problem with uncertain arc capacities. For these two problems, we prove that once uncertainty is revealed, even identifying a reactive solution with a minimal distance to a given solution is ‐hard for , and is polynomial for . We highlight the benefits of the proactive approach in a case study on a railroad planning problem. First, we compare it to the anchored and the ‐distance approaches. Then, we show the efficiency of the proactive solution over reactive solutions. Finally, we illustrate the recovery cost reduction when relaxing the optimality constraint on the nominal objective of the proactive solution . We also consider the min–max version of the proactive problem where we minimize the maximal recovery cost over all scenarios. We show that the same complexity results hold for this version. We also exhibit a class of problems for which the set of extreme points of the convex hull of a discrete uncertainty set always contain a worst‐case scenario. We show that this result does not hold for three distinct classes deduced from the first one.