  Solution robustness focuses on structural similarities between the nominal
solution and the scenario solutions. Most other robust optimization approaches
focus on the quality robustness and only evaluate the relevance of their
solutions through the objective function value. However, it can be more
important to optimize the solution robustness and, once the uncertainty is
revealed, find an alternative scenario solution $x^s$ which is as similar as
possible to the nominal solution $x^{nom}$. This for example occurs when the
robust solution is implemented on a regular basis or when the uncertainty is
revealed late. We call this distance between $x^{nom}$ and $x^s$ the solution
cost. We consider the proactive problem which minimizes the average solution
cost over a discrete set of scenarios while ensuring the optimality of the
nominal objective of $x^{nom}$. We show for two different solution distances
$d_{val}$ and $d_{struct}$ that the proactive problem is NP-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 the uncertainty is revealed, even identifying a reactive
solution $x^r$ with a minimal distance to a given solution $x^{nom}$ is NP-hard
for $d_{struct}$, and that it is polynomial for $d_{val}$. We highlight the
benefits of solution robustness in a case study on a railroad planning problem.
First, we compare our proactive approach to the anchored and the $k$-distance
approaches. Then, we show the efficiency of the proactive solution over
reactive solutions. Finally, we illustrate the solution cost reduction when
relaxing the optimality constraint on the nominal objective of the proactive
solution $x^{nom}$.
