Advances and Applications in Statistics
Volume 49, Issue 4, Pages 267 - 285
(October 2016) http://dx.doi.org/10.17654/AS049040267 |
|
A SOLUTION TO THE INVERSE MINIMUM CUT PROBLEM IN DYNAMIC NETWORK FLOWS
Hajar Banikhademi and Hasan Salehi Fathabadi
|
Abstract: We study the problem of inverse minimum dynamic cut (IMDC), which changes a capacity vector u in such a way that a given dynamic cut and the applied changes are minimum, using the Euclidean norm to measure these changes. Our aim is to solve an inverse minimum dynamic cut, by finding a maximum dynamic flow in a time-expanded network flow and, having calculated the appropriate algorithm, analyzing the relationships between the time-expanded networks, the maximum flow, and the minimum cut. First, we show a specified dynamic cut, to be optimized; the capacity of arcs should be reduced. This study is useful in cases where the network should be divided into two parts by cutting such that this cut has the minimum weight. It is applicable in physics, chemistry, computer networks and electrical circuits, etc. The advantage of this method is the use of time-expanded network to be static corresponding to a dynamic network and algorithm is easily displayed on this network. Finally, the algorithm is implemented on a numerical example of dynamic network flow. |
Keywords and phrases: dynamic network flow, inverse optimization, minimum dynamic cut, time-expanded network. |
|
Number of Downloads: 407 | Number of Views: 1893 |
|