Polynomial-time identification of robust network flows under uncertain arc failures |
| |
| Authors: | Vladimir L Boginski Clayton W Commander Timofey Turko |
| |
| Institution: | (1) Department of Industrial and Systems Engineering, Research and Engineering Education Facility (REEF), University of Florida, Shalimar, FL, USA;(2) Air Force Research Laboratory, Munitions Directorate, Eglin Air Force Base, Niceville, FL, USA;(3) Risk Management and Financial Engineering Lab, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA |
| |
| Abstract: | We propose Linear Programming (LP)-based solution methods for network flow problems subject to multiple uncertain arc failures,
which allow finding robust optimal solutions in polynomial time under certain conditions. We justify this fact by proving
that for the considered class of problems under uncertainty with linear loss functions, the number of entities in the corresponding
LP formulations is polynomial with respect to the number of arcs in the network. The proposed formulation is efficient for
sparse networks, as well as for time-critical networked systems, where quick and robust decisions play a crucial role. |
| |
| Keywords: | Network flows Minimum Cost Flow problems Linear programming Robust optimization Quantitative risk measures Conditional Value-at-Risk |
| 本文献已被 SpringerLink 等数据库收录！ |
|
