Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17031 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912343890329600 |
|---|---|
| author | Klyuchikov, Artyom Hildebrand, Roland Protasov, Sergei Rogozin, Alexander Chernov, Alexei |
| author_facet | Klyuchikov, Artyom Hildebrand, Roland Protasov, Sergei Rogozin, Alexander Chernov, Alexei |
| contents | We consider the robust version of a multi-commodity network flow problem. The robustness is defined with respect to the deletion, or failure, of edges. While the flow problem itself is a polynomially-sized linear program, its robust version is a saddle-point problem with discrete variables. We present two approaches for the solution of the robust network flow problem. One way is to formulate the problem as a bigger linear program. The other is to solve a multi-level optimization problem, where the linear programs appearing at the lower level can be solved by the dual simplex method with a warm start. We then consider the problem of robustifying the network. This is accomplished by optimally using a fixed budget for strengthening certain edges, i.e., increasing their capacity. This problem is solved by a sequence of linear programs at the upper level, while at the lower levels the mentioned dual simplex algorithm is employed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17031 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Robustifying networks for flow problems against edge failure Klyuchikov, Artyom Hildebrand, Roland Protasov, Sergei Rogozin, Alexander Chernov, Alexei Optimization and Control We consider the robust version of a multi-commodity network flow problem. The robustness is defined with respect to the deletion, or failure, of edges. While the flow problem itself is a polynomially-sized linear program, its robust version is a saddle-point problem with discrete variables. We present two approaches for the solution of the robust network flow problem. One way is to formulate the problem as a bigger linear program. The other is to solve a multi-level optimization problem, where the linear programs appearing at the lower level can be solved by the dual simplex method with a warm start. We then consider the problem of robustifying the network. This is accomplished by optimally using a fixed budget for strengthening certain edges, i.e., increasing their capacity. This problem is solved by a sequence of linear programs at the upper level, while at the lower levels the mentioned dual simplex algorithm is employed. |
| title | Robustifying networks for flow problems against edge failure |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.17031 |