RECOVERY ACT - Robust Optimization for Connectivity and Flows in Dynamic Complex Networks

[摘要] The goal of this project was to study robust connectivity and flow patterns of complex multi-scale systems modeled as networks. Networks provide effective ways to study global, system level properties, as well as local, multi-scale interactions at a component level. Numerous applications from power systems, telecommunication, transportation, biology, social science, and other areas have benefited from novel network-based models and their analysis. Modeling and optimization techniques that employ appropriate measures of risk for identifying robust clusters and resilient network designs in networks subject to uncertain failures were investigated in this collaborative multi-university project. In many practical situations one has to deal with uncertainties associated with possible failures of network components, thereby affecting the overall efficiency and performance of the system (e.g., every node/connection has a probability of partial or complete failure). Some extreme examples include power grid component failures, airline hub failures due to weather, or freeway closures due to emergencies. These are also situations in which people, materials, or other resources need to be managed efficiently. Important practical examples include rerouting flow through power grids, adjusting flight plans, and identifying routes for emergency services and supplies, in the event network elements fail unexpectedly. Solutions that are robust under uncertainty, in addition to being economically efficient, are needed. This project has led to the development of novel models and methodologies that can tackle the optimization problems arising in such situations. A number of new concepts, which have not been previously applied in this setting, were investigated in the framework of the project. The results can potentially help decision-makers to better control and identify robust or risk-averse decisions in such situations. Formulations and optimal solutions of the considered problems need to capture uncertainty and risk using appropriate probabilistic, statistical and optimization concepts. The main difficulty arising in addressing these issues is the dramatic increase in the computational complexity of the resulting optimization problems. This project studied novel models and methodologies for risk-averse network optimization- specifically, network design, network flows and cluster detection problems under uncertainty. The approach taken was to incorporate a quantitative risk measure known as conditional value-at-risk that is widely used in financial applications. This approach presents a viable alternate modeling and optimization framework to chance-constrained optimization and mean-variance optimization, one that also facilitates the detection of risk-averse solutions.

[发布日期] 2013-12-25

[学科分类] 数学（综合）

[关键词] Combinatorial Optimization;Risk Analysis;Conditional Value-at-risk