Updating Network Flows Given Multiple, Heterogeneous Arc Attribute Changes

Abstract

A dual ascent reoptimization technique is proposed for updating optimal flows for the minimum cost network flow problem (MCNFP) given any number of simultaneous, heterogeneous changes to the network attributes (i.e. supply at nodes, arc costs and arc capacities) and the optimal solutions to the prior primal and dual problems. Significant savings in computation time can be achieved through the use of reoptimization in place of solving a new MCNFP from scratch as each new problem instance (i.e. set of network attribute updates) arises. The proposed technique can be implemented with polynomial worst-case computational complexity. Extensive numerical experiments were designed and conducted to assess the computational benefits of employing the proposed reoptimization technique as compared with solution from scratch using comparable classic implementations of the original algorithms. This work was motivated by the need for the real-time provision of evacuation instructions to people seeking quick egress from a large sensor-equipped building that has come under attack by natural or terrorist forces, but has broad applicability.

Appendix

Results of a subset of the numerical experiments are provided in this appendix. Specifically, all results of runs on the 500 node network are given, with the exception of additional runs conducted to assess the impact of the cost and capacity bounds employed in the creation of the problem instances. No additional insight was gained about the relative performance of the SSP and CS algorithms or the related reoptimization implementations as a result of those runs. The results are given in Tables 1, 2, 3, 4, 5, 6 and 7. Numerical values in the tables are rounded to the nearest decimal place or two decimal places if the value is below one. The run-time for CPLEX was most often 0.03 seconds, 0.02 seconds in all other instances. Column and row heading definitions are defined next.

CS:

Run time of the CS algorithm

CS-R:

Run time of CS-R

SSP:

Run time of the SSP algorithm

SSP-R:

Run time of SSP-R

y/z:

Run-time of algorithm y divided by run-time of algorithm z

x/x/x/x:

Fraction of arcs with cost changes/fraction of arcs with capacity changes/ whether or not the cost changes are increasing (1), decreasing (− 1) or split (0)/whether or not the capacity changes are increasing (1), decreasing (− 1) or split (0)

Table 1 Average run time (in c.p.u. seconds) for 500 node network with 1 source-sink pair, 10 supply units at source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Table 2 Average run time (in c.p.u. seconds) for 500 node network with 5 source-sink pairs, 5 supply units at each source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Table 3 Average run time (c.p.u. seconds) for 500 node network with 5 source-sink pairs, 10 supply units at each source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Table 4 Average run time (in c.p.u. seconds) for 500 node network with 5 source-sink pairs, 20 supply units at each source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Table 5 Average run time (in c.p.u. seconds) for 500 node network with 10 source-sink pairs, 10 supply units at each source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Table 6 Average run time (in c.p.u. seconds) for 500 node network with 20 source-sink pairs, 10 supply units at each source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Table 7 Average run time (in c.p.u. seconds) for 500 node network with 50 source-sink pairs, 10 supply units at each source, 23 unit cost upper bound, 3 and 50 capacity lower and upper bound

Additional experiments were run to assess the impact of changes in supply on the relative performance of the tested algorithms. Results of these runs are presented in Table 8. The values in the first column are defined as follows.

y/y/y/y:

Supply units at each source/fraction of source nodes with change to supply/ upperbound on change in supply/whether or not changes in supply are increasing (1), decreasing (− 1) or split (0)

Table 8 Average run time (in c.p.u. seconds) for 500 node network with 23 unit cost upper bound, 3 and 50 capacity lower and upper bound to assess affects of supply changes