Network Design by Christian Klaus

Christian completed his PhD at NPS in March 2014.  His thesis relates to designing networks that are resilient and reliable.

Thesis Presentation

Complete Thesis

Klaus, C. (2014).  Network Design for Reliability and Resilience to Attack(PhD Thesis).  Naval Postgraduate School.

Executive Summary

This dissertation explores two network-design problems. The rst problem, which has several variants, concerns the design of a transportation network that is resilient to worst-case attacks. The second problem concerns the design of a reliable logistics network, that can cope with random link failures.

Designing a Transportation Network That Is Resilient to Attack

The Path-Portfolio-Selection problem is a three-stage sequential game. In this game a defender selects a number of paths from a network, such that the shortest of those paths has minimum length under an optimal attack for a given attack budget. This dissertation begins with a detailed study on the Path-Portfolio-Selection-m-n problem (PPS-m-n), where the attacker destroys n arcs in the defender's portfolio of m paths from source to sink. An attacked arc in PPS-m-n is unusable for the defender. Under that assumption, we show that one can always construct an optimal portfolio in which only the longest path remains non-interdicted under the worst-case attack.

An example application for PPS-m-n is transportation of hazardous material, for which one wishes to have multiple shipping options in case of disruptions. The transportation requires time-consuming route preparation and clearance, which makes it almost impossible to deviate abruptly from the initial planning. A solution to an equivalent PPS-m-n model provides a set of paths that guarantee shipment under the worst-case disruption. A trivial solution is a set of independent, edge-disjoint, paths. The optimal solution, however, is not necessarily independent, i.e., paths can share a certain amount of edges, resulting in shorter post-attack responses than the trivial disjoint solution.

We formulate a single-level mixed integer linear program (MIP) that returns an optimal portfolio for PPS-m-n. The number of constraints for this MIP grows exponentially with size of the network because of the exponentially increasing number of possible attacks to consider. The MIP becomes impractical for large networks. We use a dynamic row-and-column generation approach that generates constraints and variables simultaneously to solve PPS-m-n for large networks. As the row-and-column generation procedure progresses, we solve smaller models that consider only subsets of all possible attacks against the network. Efficiency of solving such smaller models is improved by adding supervalid inequalities. Supervalid inequalities remove suboptimal candidate solutions from the solution space, and can thereby decease the solution time. Further savings in solution time are achieved by removing superuous parts from the network.

Any feasible solution for the PPS-m-n model provides an upper bound for the maximum path length in the portfolio. Such an upper bound is used to remove unnecessary nodes and arcs from the network, that is, nodes and arcs that cannot appear in an optimal portfolio. The dissertation proposes a sequence of models, each model increasing in complexity, but also providing a tighter bound than the previous. Starting with the computationally cheapest model, we alternate solving a bounding model and shrinking the network based on the resulting bounding information. We develop a case study with a road network from Germany that consists of 2,971 nodes and 8,824 arcs, and solve PPS- 5-2 in about two hours, after identifying as unnecessary more than 85% of nodes and arcs in the network. Here, the sequence of bounding models produces solutions within 1% of optimality in under seven minutes.

The dissertation denes and explores several variants of PPS-m-n. A probabilistic version, Pr-PPS-m-n, incorporates uncertainty in the attacker's capability. That uncertainty is expressed by a probability distribution on the number of attacked arcs. The solution to Pr-PPS-m-n is a portfolio with minimum expected length of the defender's response path. To compute the expected path length, one must identify the shortest non-interdicted path after an attack, requiring many additional constraints in the model. However, with a few modications, the row-and-column generation approach and the network-simplication sequence apply to solve Pr-PPS-m-n to optimality. In addition to a computationally intensive method to nd the optimal solution, we provide a simpler model that produces a near-optimal solution with a performance guarantee in a shorter amount of time.

An attacked arc in PPS-m-n or Pr-PPS-m-n is destroyed and unusable for the defender's post-attack operation. However, an attacked arc could still be usable, just less eciently than if the arc is not attacked. Such ineciency is modeled in D-PPS-m-n, where an attacked arc is lengthened rather than destroyed. Similar ideas and methods encountered while solving Pr-PPS-m-n guide us to formulate and solve D-PPS-m-n. The solution could be a portfolio of paths, all of which can be interdicted simultaneously. In the continuous relaxation of D-PPS-m-n, C-PPS-m-n, the attacker can smear the attack budget continuously across the arcs in the network. The continuous relaxation of the attack variables enables a two-step reformulation of the inner optimization problem, leading to a single-level optimization model. The solution for C-PPS-m-n is a portfolio, containing disjoint paths with a minimum total length.

A closely related problem to PPS-m-n is the tri-level Sub-Network-Selection-m-n problem, SNS-m-n. The defender in SNS-m-n selects a sub-network containing no more than m arcs, such that the shortest path in the sub-network after the worst-case attack on n arcs has minimum length. Selecting a sub-network rather than a portfolio of paths gives the defender more exibility, resulting in better responses than the one for an analogous instance of PPS-m-n. We provide models for SNS-m-n and its variations Pr-SNS-m-n, DSNS- m-n, and C-SNS-m-n. Solving methods for PPS-m-n are adapted to solve SNS-m-n, returning optimal solutions that show similarities to the respective PPS-m-n optimal solutions. However, the SNS-m-n models can be extended to other models of network operations, such as minimum cost ow problems, which makes them particularly interesting.

Augmenting a Stochastic Logistics Network with Warehouses to Optimize Reliability

The second problem studied in this dissertations considers a stochastic logistics network, where arcs can fail randomly and independently. In this network, one wishes to ship cargo from a source to a destination. Because the network does not provide storage capacity in transshipment nodes, shipment must be delayed until the network provides a complete path from source to sink. In the presence of storage capacity (warehouses), cargo can be shipped partway, that is, from source to a warehouse and later to the sink. TheWarehouse Location Network Reliability problem (WLNR) identies the optimal storage locations that minimize the cargo's expected waiting time for shipment, and denes the associated optimal shipping policy. Actual transit time is negligible compared to the waiting time and is ignored.

WLNR is motivated by the current procedure used to ship humanitarian assistance cargo, using uncertain space available on recurring, scheduled military transportation routes. The uncertainty about space available renders the transportation network stochastic. The Department of Defense (DOD) cannot store humanitarian assistance cargo at intermediate airports, unless a warehouse is created. The decision where to create and maintain warehouses is subject to budget constraints.

The solution for WLNR consists of two parts, the optimal location for the warehouses and the optimal shipping policy. The shipping policy species where to ship the cargo, in particular, it ships to the reachable node with storage capacity, a warehouse or sink, from which one expects the smallest shipping time to the sink. We demonstrate a connection between WLNR and a Markov Decision Process with Design (MDPD), which provides both the optimal warehouse location and the optimal shipping policy. For large networks, a MDPD is intractable, because of a large state space. However, the results from the MDPD reveals the structure for the optimal shipping policy. For xed warehouse locations, the MDPD with pre-dened shipping policy behaves like a Markov chain. We use such a Markov chain to compute the expected shipping time for one or two warehouses. The resulting equations involve several s-t-reliabilities. The s-t-reliability is the probability that a path exists between two nodes, s and t, in a stochastic network. Computing s-t-reliability is known to be #P-complete, and impracticable for large networks.

We provide methods to nd the optimal warehouse locations for one and two warehouses. Estimating reliability by Monte Carlo simulation, which is very time-consuming, lies at the core of the methods to solve WLNR. We show theoretical results that allow the elimination of suboptimal solutions from the solution space, resulting in a signicant saving of computational eort. We create a case study from the DOD's humanitarian assistance transportation network with 95 nodes and 1096 arcs. There are more than 8000 possible ways to place two warehouses in that network. We identify up to 95% of these combinations as being suboptimal without computing the associated shipping times, which saves on simulation eort. We achieve further savings of simulation time by customizing the sampling method. A typical procedure to estimate s-t-reliability draws a sample of the stochastic network, and then veries whether s and t are connected in that sample. We use a technique that only samples arcs as needed while searching for a path from s to t. In the case study, we sample less than 20% of all arcs when applying this technique. We also provide a theoretical bound on the best possible expected waiting time. The bound shows on the case study example that adding more than two warehouses will improve results only fractionally.

© Copyright 2004-2019 - Ned Dimitrov