Minimizing recovery cost of network optimization problems

We propose a two-stage recoverable robustness approach that minimizes the recovery cost. In many applications, once the uncertainty (Formula presented.) is revealed, it can be more important to recover a solution (Formula presented.) which is as similar as possible to the nominal solution (Formula presented.) than to minimize the nominal objective value of (Formula presented.). 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 (Formula presented.). 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 (Formula presented.) and (Formula presented.) that the proactive problem is (Formula presented.) -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 (Formula presented.) with a minimal distance to a given solution (Formula presented.) is (Formula presented.) -hard for (Formula presented.), and is polynomial for (Formula presented.). 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 (Formula presented.) -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 (Formula presented.). 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.