Robust Network Flows


Vipin Ravindran Vijayalakshmi


+49 241 80 97942


  Grid Copyright: Mario Irrmischer

The primary goal of my work in the Research Training Group UnRAVeL is focused towards the analysis and development of algorithms and complexity results for mathematical optimization problems, particularly with regard to their stability and robustness under uncertainty in input data. The classical methods of optimization in many practical applications are often susceptible to errors and noise in the input information, resulting in poor generalization performance. Therefore, it is imperative to devise optimization techniques that could assuage if not preclude the performance issues in optimization arising due to unreliability in the input data. Robust optimization is one such technique that allows for analyzing a solution to an optimization problem with respect to its worst-case performance given a list of scenarios. In this project we analyze network flow problems which are affected by uncertainty, either due to insufficient information or perturbation in the input data. The objective is that the outcome of this study can be applied towards solving many of the real-world problems such as in railway networks which are extremely susceptible to disruptions due to insufficient and unreliable information. One of the classical approaches in handling uncertainty is the \gamma-robustness model first introduced by Bertsimas and Sim. In this model, robustness is sought against a set of scenarios in which the input deviates from the nominal input data in at most \gamma many parameters simultaneously. In a network flow problem this would correspond to failure of \gamma many edges in the network. Therefore, the idea is to study network flow problems under the robustness framework in order to develop algorithms that are oblivious to certain degree of failure in the network and may be also allow for good re-optimization.